Homework

Homework will usually be assigned every lecture day and will usually be due at the beginning of the next lecture day. The due date for each assignment will be listed, so there should never be any confusion. Your homework will always be graded for completion and usually some portion of your work will be graded for correctness. You are allowed and encouraged to work together on homework. However, each student is expected to turn in their own work. Each assignment will be worth 5-10 points depending on the level of difficulty and/or amount of time required to complete an assignment (generally, more time consuming homework will be worth more). There will be approximately 20-25 homework assignments. Three (possibly more) of your lowest homework scores will be dropped. You are allowed to turn in up to three homework assignments late with no questions asked. Unless you have made arrangements in advance with me, homework turned in after class will be considered late. Occasionally, you may be required to submit your homework via Moodle or Sage. Your overall homework grade will be worth 25% of your final grade.

Here is the collection of assignments for the semester. This list will be updated as we progress through the course. I reserve the right to modify the homework assignments as I see necessary.

• Homework 1: Send me an email at and tell me something interesting about yourself. For example, something interesting about me is that in the summer of 2003, I was struck by lightning while doing a technical ridge traverse in the Indian Peaks Wilderness in Colorado. The purpose of this assignment is to: (1) make sure you have my email address, and (2) make sure you know that I want you to feel free comfortable contacting me. (Due Tuesday, September 6 by 5PM)
• Homework 2: Stop by my office (Hyde 356) and say hello. If I'm not there, leave a note under the door. The purpose of this assignment is to: (1) make sure you know where my office is, and (2) make sure you know that I want you to feel free comfortable stopping by to get assistance with this course or any other for that matter. (Due Friday, September 9)
• Homework 3: Formalize the "Traffic Jam" problem that we encountered in class. That is, try to come up with precise language and notation for describing the rules of the game, the objective, and the solution. Feel free to invent your own definitions and notation, but be as explicit as possible. A short description isn't necessarily the goal. This assignment is intentionally vague and it may be frustrating to not understand exactly what it is I'm looking for. Do the best you can. (Due Tuesday, September 6)
• Homework 4: Type a one-page response to the following questions. (Due Thursday, September 8)
  1. What is mathematics?
  2. Is mathematics invented or discovered? Why?
  3. Should everyone study mathematics? Why? How much?
• Homework 5: Using the axiomatic system for Traffic Jam developed in class, for each statement below either prove the statement or explain why the statement cannot be proven. (Due Thursday, September 15)
  1. $\bullet~\circ~\bullet~\circ~\underline{\ \ }~\circ~\bullet~\circ~\bullet$
  2. $\bullet~\circ~\bullet~\circ~\underline{\ \ }~\bullet~\circ~\bullet~\circ$
  Also, find 2 more statements in Traffic Jam that you can prove and two more that you can't.
• Homework 6: Finish proving the theorems on the Circle-Dot Handout. (Due Tuesday, September 20)
• Homework 7: Imagine you have 25 pebbles, each occupying one square on a 5 by 5 chess board. Tackle each of the following variations of a puzzle. (Due Thursday, September 22)
  1. Variation 1: Suppose that each pebble must move to an adjacent square by only moving up, down, left, or right. If this is possible, describe a solution. If this is impossible, explain why.
  2. Variation 2: Suppose that all but one pebble (your choice which one) must move to an adjacent square by only moving up, down, left, or right. If this is possible, describe a solution. If this is impossible, explain why.
  3. Variation 3: Consider Variation 1 again, but this time also allow diagonal moves to adjacent squares. If this is possible, describe a solution. If this is impossible, explain why.
• Homework 8: Consider the following problem. An overfull prison has decided to terminate some prisoners. The jailer comes up with a game for selecting who gets terminated. Here is his scheme. 10 prisoners are to be lined up all facing the same direction. On the back of each prisoner's head, the jailer places either a black or a red dot. Each prisoner can only see the color of the dot for all of the prisoners in front of them and the prisoners do not know how many of each color there are. The jailer may use all black dots, or perhaps he uses 3 red and 7 black, but the prisoners do not know. The jailer tells the prisoners that if a prisoner can guess the color of the dot on the back of their head, they will live, but if they guess incorrectly, they will be terminated. The jailer will call on them in order starting at the back of the line. Before lining up the prisoners and placing the dots, the jailer allows the prisoners 5 minutes to come up with a plan that will maximize their survival. What plan can the prisoners devise that will maximize the number of prisoners that survive? Some more info: each prisoner can hear the answer of the prisoner behind them and they will know whether the prisoner behind them has lived or died. Also, each prisoner can only respond with the word "black'' or "red.'' (Due Tuesday, September 27)
• Homework 9: Complete problems 27, 28, 29 from the set of calendar problems that Dr. Donovan handed out. You can find a copy of the calendar problems here. (Due Thursday, September 29)
• Homework 10: Consider the following statements. If a statement is true, prove it. If a statement is false, provide a counterexample. (Due Tuesday, October 5)
  1. The sum of any two odd integers is even.
  2. The square of any integer is even.
  3. The product of an even integer times any other integer is even.
  4. If $n$ is an integer, then $n^2-n+3$ is odd.
• Homework 11: Consider the following statements. If a statement is true, prove it. If a statement is false, provide a counterexample. (Due Thursday, October 7)
  1. Suppose $a,b,c\in\mathbb{Z}$. If $a$ divides $b$ and $a$ divides $c$, then $a$ divides $b+c$.
  2. For all $x\in \mathbb{Z}$, if 3 divides $x$, then 2 divides $x+1$.
  3. Let $x$ and $y$ be integers. If $x$ and $y$ are even, then $xy$ is divisible by 4.
• Homework 12: Complete the following exercises. (Due Thursday, October 13)
  1. Consider the abstract statement $P\implies Q$. Use truth tables to show that the inverse and converse are not equivalent to $P\implies Q$.
  2. Provide an example of a true statement of the form $P\implies Q$ such that the converse and inverse of the statement are false.
  3. Prove the following statement in two different ways: (i) direct proof, and (ii) proof by contrapositive.
     • If $x$ and $y$ are odd integers, then $xy$ is odd.
  4. Prove the following statement by proving the contrapositive.
     • Let $x\in\mathbb{Z}$. If 8 does not divide $x^{2}-1$, then $x$ is even.
     Why would it be difficult to prove this statement directly?
• Homework 13: Proof each of the following statements via a direct proof or a proof by contrapositive. In each case, assume that $x,y\in \mathbb{Z}$. (Due Tuesday, October 18)
  1. If $x^{2}$ is not divisible by 4, then $x$ is odd.
  2. If $xy$ is even, then either $x$ is even or $y$ is even.
  3. If $xy$ is odd, then both $x$ and $y$ are odd.
• Homework 14: Take 15 balls/chips/coins (or whatever), divide into any number of piles with any number of chips in each pile. Arrange piles in adjacent columns. Take the top chip off every column and make a new column to the left. Repeat forever. What happens? Why? For what numbers will this happen? (Due Thursday, October 20)
• Homework 15: Complete the following exercises. (Due Tuesday, October 25)
  1. Prove the following statement two ways: (i) direct proof, and (ii) proof by contradiction.
     • If $x$ and $y$ are odd integers, then $xy$ is odd.
  2. Prove each of the following statements using a proof by contradiction.
     • Suppose that $a$ and $b$ are positive integers. If $a-b$ is odd, then $a+b$ is odd.
     • If $n$ is a natural number, then $\displaystyle \frac{n}{n+1}>\frac{n}{n+2}$.
• Homework 16: Prove the following statements (Due Thursday, October 27).
  1. Prove that $\sqrt{5}$ is irrational.
  2. Complete the proof that there are infinitely many primes.
• Homework 17: Prove the following statements (Due Tuesday, November 1).
  1. Let $a,b,c\in \mathbb{N}$. Then $ac$ divides $bc$ if and only if $a$ divides $b$.
  2. Let $a,b,c\in \mathbb{N}$. Then $a+1$ divides $b$ and $b$ divides $b+3$ if and only if $a=2$ and $b=3$.
• Homework 18: Complete the following exercises (Due Thursday, November 3).
  1. Prove that or all $n\in\mathbb{N}$, $\displaystyle \sum_{i=1}^n i^3=1^3+2^3+\cdots + n^3=\left(\frac{n(n+1)}{2}\right)^2$.
  2. For $n\in \mathbb{N}$, define $\displaystyle a_n=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots +\frac{1}{n(n+1)}$. Conjecture a formula for $a_n$ and then prove that your conjecture is correct for all $n\in \mathbb{N}$.
• Homework 19: Complete the following exercises (Due Tuesday, November 8).
  1. Prove that for all $n\in\mathbb{N}$, 6 divides $n^3-n$. (Use weak induction.)
  2. Prove that every natural number can be written as the sum of distinct powers of two. (Use strong induction.)
• Homework 20: Complete the following exercises (Due Thursday, November 10).
  1. Let $\alpha$ be the positive solution to $x^2=x+1$. Prove that for all $n\in\mathbb{N}$, $f_n\leq \alpha^{n-1}$. (Use strong induction.)
  2. Which complete graphs have the property that all the edges can be drawn without lifting your pencil and without retracing any edges? Briefly justify your answer as best you can.
  3. Find a visual proof for the following theorem. For all $n\in \mathbb{N}$ , $1+3+5+\cdots +(2n-1)=n^2$.
• Homework 21: Complete the following exercises. (Due Thursday, November 17).
  1. Prove that for all $a,b\in \mathbb{N}$, $t_{a+b}=t_a+t_b+ab$, where $t_n$ is the $n$th triangular number.
  2. Prove that for all $a,b\in \mathbb{N}$, $t_{ab}=t_a t_b+t_{a-1}t_{b-1}$, where $t_n$ is the $n$th triangular number.
  To prove these, you can come up with a visual proof or an algebraic proof. Your choice.
• Homework 22: Complete the exercises given in class. (Due Thursday, December 1).
• Homework 23: Complete the following exercises. (Due Thursday, December 8).
  1. For the weighted graph given in class, approximate the optimal Hamilton circuit using (i) the Nearest Neighbor algorithm starting at vertex $A$, and (ii) the Cheapest Link algorithm.
  2. Are either of $K_{3,3}$ or $K_{5}$ planar on a sphere or torus (i.e., donut)? Explain your answer as best you can.
  3. Consider the Mandelbrot set.
     • Find 2 (new) points (with distance less than 2 from origin) that are not in Mandelbrot set.
     • Find 2 (new) points that are in Mandelbrot set.