Friday, May 2, 2014

Fit 1*2 dominos in 2*N strip

Problem

In how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?

Solution


Please notice that we can put tiles either vertically or horizontally. For putting vertical tiles, we need a gap of at least 2 X 2. For putting horizontal tiles, we need a gap of 2 X 1. Number of arrangements will be the same as the arrangements, we can make with gaps of 1 and 2 (order dependent). In this manner, this problem reduces to find the number of ways to partition N using the numbers 1 and 2 with order considered relevant.

For example: 11 = 1 + 2 + 2+ 1 +2 + 2 + 1

If we have to find such arrangements for 12, we can either place a 1 in the end or can add 2 in the arrangements possible with 10.

Similarly, Lets say we have Xn possible arrangements for N. Then for (N+1), we can either place just 1 in the end. Or we can find possible arrangements for (N-1) and put a 2 in the end.

Going by above theory: Xn+1 = Xn + Xn-1

Lets verify above theory for our original problem:

In how many ways, we can fill a 2 X 1, strip:
  • 1 -> only one vertical tile.

In how many ways, we can fill a 2 X 2, strip:
  • 2 -> Either 2 horizontal or 2 vertical tiles.

In how many ways, we can fill a 2 X 3, strip:
  • 3 -> either put a vertical tile in 2 solutions possible for 2 X 2 strip or put 2 horizontal tiles in only solution possible for 2 X 1 strip. (2 + 1 = 3)

Similarly in how many ways, we can fill a 2 X N, strip:
  • Either put a vertical tile in solutions possible for 2 X (N-1) strip or put 2 horizontal tiles in solution possible for 2 X (N-2) strip. (Xn-1 + Xn-2).

That’s how, we verified that our final solution:
Xn = Xn-1 + Xn-2

Above recurrence relation is nothing but Fibonacci Series with X1 = 1 and X2 = 2.


References

Reactions:

0 comments:

Post a Comment