[ [geometry on graph paper ]

a) In how many ways can a rectangle $8 \times 2$ be divided into rectangles $1 \times 2$? b) Invent and describe a figure that can be cut into rectangles $1 \times 2$ in exactly 555 ways.

#
a) The number of ways is $f_{9}=34$, where $f_{n}$ is the $n$-th Fibonacci number. This statement follows from the following easily provable by induction lemma: a rectangle $\mathrm{n} \times 2$ can be divided into rectangles $1 \times 2$ in exactly $\mathrm{f}_{\mathrm{n}}$ ways.

## Answer

a) 34 ways.