2014
Problem - 2495
How many different ways are there to cover a $1\times 10$ grid with some $1\times 1$ and $1\times 2$ pieces without overlapping?
Let $F_n$ be the number of ways to cover a $1\times n$ grid. Then we have $F_1=1$ and $F_2=2$. For $n \ge 3$, the following recursion holds $$F_n = F_{n-1}+F_{n-2}$$
depending on the size of the last piece placed:
- If it is $1\times 1$, then all the previous $1\times (n-1)$ grids are covered. There are $F_{n-1}$ ways.
- If it is $1\times 2$, then all the previous $1\times (n-2)$ grids are covered. There are $F_{n-2}$ ways.
It follows that $\{F_n\}$ is a Fibonacci sequence. We can either solve this sequence or simply compute the next $8$ values starting from $F_3$ manually. The answer is $F_{10}=\boxed{89}$.