How many different ways are there to tile a corridor of $2 \times N$ meters with blue tiles of $1 \times 2$ meters? 


closed as off-topic by Travis, Jean-Claude Arbaut, user223391, graydad, quid Oct 24 '15 at 16:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Travis, Jean-Claude Arbaut, Community, graydad, quid
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Try to find a reccurence $u_n=u_{n-1}+u_{n-2}$. The answer will be the Fibonacci numbers. To find this relation, consider a $N\times2$ (vertical) corridor, and how you fill the top: either with an horizontal $1\times2$ tile, either with two vertical tiles. And then you have respectively to fill a $(N-1) \times 2$ or a $(N-2)\times2$ corridor. $\endgroup$ – Jean-Claude Arbaut Oct 24 '15 at 10:56

Let the number of ways to fill the $2 \times N$ grid with $1 \times 2$ tiles be $f(N)$

We will think of the grid as vertical with base 2.

$Case 1$ : We start with one tile placed horizontally (to fill the first row)

Number of ways to fill the rest = $f(N-1)$ since we are left with a $2 \times (N-1)$ grid

$Case 2$ : We start with two tiles placed vertically to fill the first two rows.

Number of ways to fill the rest = $f(N-2)$

These are all the cases, therefore, $$f(N) = f(N-1) + f(N-2), f(1)=1, f(2)=2$$

This is similar to the fibonacci numbers and gives a closed form as:

$$f(N) = {{{\phi^{(N+1)} - (1- \phi)^{(N+1)}} }\over {\sqrt 5}} , \phi ={1+\sqrt 5 \over 2}$$


Not the answer you're looking for? Browse other questions tagged or ask your own question.