Discrete Math Puzzles - First Set. June 24, 2003
Instructor: László Babai         e-mail: laci@cs.uchicago.edu

This sheet describes some exercises and projects for independent work. If you are stuck, feel free to send me email, describe your attempt at the problem, ask for a hint.

1. The Fibonacci numbers $F_n$ are defined by the recurence $F_n=F_{n-1}+F_{n-2}$ and the initial values $F_0=0$, $F_1=1$. Prove: g.c.d. $(F_k, F_{\ell})=F_d$, where $d=$g.c.d.$(k,\ell)$.
2. (Dominoes.) Prove: if we remove two opposite corners from the chessboard, the board cannot be covered by dominoes. (Each dominoe covers two neighboring cells of the chessboard.) Look for an ``Ah-ha'' proof: clear, convincing, no cases to distinguish.
3. (Triominoes.) Remove a corner from a $101\times 101$ chessboard. Prove that the rest cannot be covered by triominoes. A triomino is like a domino except it consists of three squares in a row; each cell can cover one cell on a chessboard. Each triomino can either ``stand'' or ``lie.'' Find an ``Ah-ha'' proof.
4. Knight's trail. Consider a knight moving around on a $4\times 4$ chessboard. We let the knight start at any cell of our choosing, and we wish to guide it through 15 moves so it never steps on a previously visited cell. So, after the 15 moves, the knight will have visited each cell. Prove that this is impossible. Find an ``Ah-ha'' proof.
   
   Graph of knight moves on a $4\times 4$ chessboard.
   Hint. Show that from any trail of the knight's moves, if you delete 4 cells, the trail splits into no more than 5 connected parts. (A set $S$ of cells is connected from the knight's point of view if the knight can move from any cell of $S$ to any other cell of $S$ without leaving $S$.)
5. A mouse finds a $3\times 3\times 3$ chunk of cheese, cut into 27 blocks (cubes), and wishes to eat one block per day, always moving from a block to an adjacent block (a block that touches the previous block along a face). Moreover, the mouse wants to leave the center cube last. Prove that this is impossible. Find two ``Ah-ha!'' proofs; one along the lines of the solution of knight's trail problem, the other inspired by the solution of the dominoes problem.
6. 96 kids wait for us to split an $8\times 12$ chocolate bar along the grooves into 96 small rectangles. It is up to us in what order we do the splitting; we can start, for instance, by breaking the 7 long grooves and then split each of the 8 long ( $1\times 12$) pieces; or we can start with the short grooves, or halve the bar each time, or any other way. The one thing we are not permitted to do is stack the pieces. At any one time, we have to pick up one piece and break it into two.

   Each break takes us 1 second. Find the fastest method. (This is another ``Ah-ha'' problem.)

7. $n$ teams play a straight-elimination tournament; there are no ties. How many matches do they need to play before the winner is declared? (An ``Ah-ha'' problem again.)
8. Let $S$ be a set of $n+1$ integers from $\{1,2,\dots,2n\}$. Prove that one of them divides another. First show that this can be avoided if $S$ has only $n$ numbers. (Yes, ``Ah-ha'' again. Which is not to say that the proof is easy to find. But it is very easy to understand.)
9. Prove: if $0\le x<1$ then $1+x+\dots+x^n < \frac{1}{1-x}$.
10. Prove: for any prime $p$,
    $$\frac{1}{\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\lef... ...-\frac{1}{p}\right)} > 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots+\frac{1}{p}.$$
    Note that the variable in the product on the left hand side ranges through prime numbers only; but the variable in the sum on the right hand side ranges through all integers from 1 to $p$.
11. Prove: $1/2+1/3+1/5+1/7+\dots =\infty.$ Hint. Use the previous exercise and the fact that for small $x$, the value of $\ln(1-x)$ is close to $-x$. (You will also use the fact that $1+1/2+1/3+1/4+\dots = \infty.$)