Directions: Solve the following problems. All written work must be your own. See the course syllabus for detailed rules.

[2.1.6] You have a $3 \times 3$ -square, and you throw 10 darts at it. Show that no matter where the darts land, there are two darts whose distance is at most $\sqrt{2}$ .
[2.1.22] I have 51 rectangular pieces of cardboard, each of which has an integer length and width in the set ${1, \dots, 100}$ . (Note that squares are allowed.) Prove that there are two rectangles such that one can fully cover the other when placed on top.
Let $a_{0} = 4$ , $a_{1} = 10$ , $a_{2} = 88$ , and $a_{n} = a_{n - 1} + 21 a_{n - 2} - 45 a_{n - 3}$ for $n \geq 3$ . Use the characteristic equation method to solve the recurrence.
For positive $m$ and $n$ , a domino tiling of an $m \times n$ grid is rigid if every horizontal and vertical cut crosses a domino. In this problem, we characterize the grids with even dimensions that have rigid domino tilings.
1. Prove that if $m = 2 r$ , $n = 2 s$ , and the $m \times n$ grid has a rigid domino tiling, then $(r - 2) (s - 2) \geq 2$ . (Hint: generalize our argument in class that the $6 \times 6$ grid has no rigid domino tiling.)
2. Construct a rigid domino tiling of the $6 \times 8$ grid.
3. Prove that if $m \geq 3$ and the $m \times n$ grid has a rigid domino tiling, then the $m \times (n + 2)$ grid also has a rigid domino tiling. (Hint: show how to modify an arbitrary rigid domino tiling of the $m \times n$ grid to obtain a rigid domino tiling of the $m \times (n + 2)$ grid.)
4. Let $m$ and $n$ be positive, even integers with $m \leq n$ . Prove that the $m \times n$ grid has a rigid domino tiling if and only if $m \geq 6$ and $n \geq 8$ . (Hint: for the forward direction, use part (a) to give a direct proof. For the backward direction, use parts (b) and (c) to give an inductive proof.)