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?
1 Answer
For a tower of height
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
We can "generate" the next possible towers for
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"
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
I leave it to the reader to use this method to see that the following pattern holds: When
Generally, for a height of
Thus, our answer is, given a tower of size