Recursive (Counting) Intermediate
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}$.

report an error