Blocks and Towers solution

See the puzzle

Let's say that you've found every single way to build a 1x10 tower. Imagine that you've lined up each of these solutions. Let's remove the top block from each 1x10 tower. For some of them, you will be removing a 1x2 block, and for others, you will be removing a 1x1 block. You will be left with a bunch of 1x8 towers and 1x9 towers.

But here's the crucial point. The 1x8 and 1x9 towers constitute the complete set of solutions for towers of those sizes. No matter what kind of 1x8 tower you can build, you can always add a 1x2 block on top to get a unique 1x10 tower. Similarly, you can always add a 1x1 block on top of a 1x9 tower. Therefore, the total number of unique 1x10 towers you can build is equal to the sum of the total number of 1x8 towers and 1x9 towers.

In fact, this isn't just true of 1x10 towers. The number of ways to build any 1xN tower is equal to the sum of the ways to build 1x(N-1) and 1x(N-2) towers. So if we start with 1x1 towers (1 way) and 1x2 towers (2 ways), we can proceed to calculate the total number of ways for any size of tower:

1x1: 1
1x2: 2
1x3: 3
1x4: 5
1x5: 8
1x6: 13
1x7: 21
1x8: 34
1x9: 55
1x10: 89

This sequence of numbers is known as the Fibonacci sequence. I actually mentioned this sequence not-so-subtly in a previous post, and was even kind enough to give a closed expression for it. The number of ways to build a 1xN tower is equal to F(N+1).

The Fibonacci sequence is one of those things that seems to show up everywhere. It is closely related to the number called "the golden ratio", which I'm sure most people have heard about. It turns up all the time in nature.