Question

If I cannot put 2 successive black blocks on top of white and black blocks, In how many different ways can you build a tour of blocks of height N?

Answer 1

For a tower of height `n`, there are `F(n+2)` valid towers, where `F` is the Fibonacci sequence.

Explanation:

I'm not sure I have enough space to give you all of the details behind the answer, but I'll provide a solution and as much detail as I can concisely muster. Additionally, I'll be assuming the "rule" you're looking for is that there cannot be consecutive black blocks.

We start by considering the case where `n = 1`. That is, the tower is either W or B. Both of these are legal.

We can "generate" the next possible towers for `n = 2` from our previous set by adding in front of each option both a W and a B.

W --> WW, BW
B --> WB, BB

Note that this "doubles" our number of solutions initially, but since BB is illegal, we really have 3 solutions. Following a similar strategy, we can use this set of answers to "generate" `n = 3`.

WW --> WWW, BWW
BW --> WBW, BBW
WB --> WWB, BWB

Again, notice that our answer doubles, but that not all solutions are valid. In fact the solution BBW is not valid, meaning we have five solutions. Further note that we had to remove 1 solution exactly because we generated BBW from BW, by adding a B in front. Generally, if you have some solution set for `n = x` and it contains `b` towers starting with B, then your solutions for `n = x+1` will have double the number of solutions from `n = x`, minus `b`.

I leave it to the reader to use this method to see that the following pattern holds: When `n = 1`, we have 1 tower starting with a W and 1 tower starting with a B. For `n = 2`, we have 2 towers starting with W and 1 starting with B. For `n = 3`, we have 3 starting with W and 2 starting with B.

Generally, for a height of `n`, you have `F(n+1)` legal towers starting with a W and `F(n)` legal towers starting with a B, where `F` is the Fibonacci sequence given by `F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2)`.

Thus, our answer is, given a tower of size `n`, there are `F(n+1) + F(n)` valid towers, where `F` is the Fibonacci sequence. Note that, by the way `F` is defined, `F(n) + F(n+1) = F(n+2)`.