Too Many Choices

Probability Level 1

You're creating a catalog of tile designs for a friend. In this series of designs, the area to be tiled is 2'' x 16'' and the tiles are each 1'' x 2''.

How many different ways are there to cover the area with tiles?

Note: The image shows a few examples that describe such scenario.

233 550 987 1597 2634

4 solutions

Joan Palacios Beltran
Aug 15, 2015

Let A(n) be the set of all possible arrangements for the area $2\times n$ $|A(1)|=|\{(|)\}|=1$ $| A(2)|=|\{(||), (=)\}|=2$ And for $n>2$ $A(n)=\{(|)\}\times A(n-1)\oplus\{(=)\}\times A(n-2)$ $|A(n)|=|A(n-1)|+|A(n-2)|$ Is the Fibonacci sequence, so $|A(16)|=1597$

Hadia Qadir
Aug 18, 2015

The number of ways to arrange tiles follow the Fibonacci sequence so there will be 1597 way for 16"x2" 1 ways for 1"x2", (I) 2 ways for 2"x2", (II, = ) 3 ways for 3"x2", (III =I, I=) 5 ways for 4"x2", (IIII, =II, I=I, II=, ==) 8 ways for 5"x2", (IIIII, =III, I=II, II=I, III=, ==I, =I=, I==) ...

Achille 'Gilles'
Aug 14, 2015

1 ways for 1"x2", (I)

2 ways for 2"x2", (II, =)

3 ways for 3"x2", (III =I, I=)

5 ways for 4"x2", (IIII, =II, I=I, II=, ==)

8 ways for 5"x2", (IIIII, =III, I=II, II=I, III=, ==I, =I=, I==)

...

The number of ways to arrange tiles follow the Fibonacci sequence so there will be 1597 way for 16"x2"

c1 = 1 c2 = 2 c3 = 3 c4 = 5 c5 = 8 c6 = 13 c7 = 21 c8 = 34 c9 = 55 c10 = 89 c11 = 144 c12 = 233 c13 = 377 c14 = 410 c15 = 787 c16 = 1197

I could not think of a concrete formula. I just worked my way up, by adding the two previous numbers to get the current case. Eg. c3 = c1 + c2. Since c1 = 1 and c2 = 2, then c3 = 1 + 2 or c3 = 3.

I don't know where 1597 came from. Where's my error?

jay bro - 10 months, 1 week ago

Pedro Zilmar Rysdyk da Silva
Aug 14, 2015

For a 2x2 area, we have = and || as options. For a 2x3 area, |=, =| and |||. That said, you have the 2x4 area by doing the following:

Take the 2x3 and add one vertical tile on every design it has. You'll have: |=|, =|| and ||||.
After, take the 2x2 area and add two horizontal tiles, like =. Then you have == and ||=.

So, we found the 2x4 number of designs is the sum of the 2x2 and 2x3 designs. With these rules it becomes clear that it is like the Fibonacci series, as it will work for any area with the format 2xL. If, for 2x4 area we found the 5th Fibonacci serie number, for 2x16 we may need the 17th number on Fibonacci.

Sorry for my bad english and please comment.

Can't we solve it in another way?

Rakib Hasan - 5 years, 10 months ago

This solution is not really complicated, we can go directly to Fibonacci, it's not needed to go through all of that. I just wanted to show how did I find out that this scenario works like the Fibonacci Series (and not just say that it works that way).

Pedro Zilmar Rysdyk da Silva - 5 years, 9 months ago

Because horizontal tiles co-exist (there's always one above and below), we only need to look at the top one. We can think of a horizontal tile as value 2 (since it takes up 2/16 length) and a vertical tile as 1 (since it takes up 1/16 length). Starting with all horizontal tiles, we get the array [2,2,2,2,2,2,2,2] - eight 2s. This is one possible combination. Another combination is [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] - sixteen 1s. A 2 turns to two 1s (2 -> 1,1). To get the combinations in between, the number of 2s that change to 1s varies.

For example for combination [2,2,2,2,2,2,2,1,1], we need to find out the different ways the 1s can be arranged. I did this using the choose function, so 9C2 gives you the number of ways the 1s can be rearranged which is 36. Repeat this each time you change a 2 to two 1s. nCm where n is the length of the array and m is the number of 1s.

At the end, you take the sum of all combinations {1+36+210+462+495+286+91+15+1} = 1597.

I realise this has nothing to do with recursion but thought it was an interesting way to approach the problem.

Farham ahmad - 1 year, 6 months ago

Too Many Choices

4 solutions

0 pending reports