Towers and Dragons Problem

Problem 1: The Tower of Hanoi is a classic math puzzle. Imagine 4 discs stacked on one of three posts. The discs get progressively smaller from the bottom to the top of the stack. The puzzle--move all 4 discs, one disc at a time, to another post. One other thing--you can never place a larger disc on a smaller one. What's the fewest number of moves needed to move all of the discs?

Here is a table that gives the number of moves needed to move discs in a tower with 1, 2, 3, or 4 discs. For the sequence, note that the discs are labeled from largest (1) to smallest (1, 2, 3 ,4, depending on the number of discs you are playing with):

In general, the argument that the minimum number of moves to solve the Hanoi Puzzle is 2ⁿ – 1 is inductive. Here’s an inductive argument that you might give to a middle schooler--it’s evident that we need one move to move a single disc and 3 moves to move 2 discs. To move 3 discs, first, the first 2 discs must be moved (3 moves)—note here that to move the largest disc, all other discs must be on a single ‘Tower’ so all 3 moves really are required. Now move the large disc (1 move); then the other 2 discs again (3 moves). So we see that it takes at least 7 moves to move three discs. Etc. 

Problem 2: Take a strip of paper. fold it in half from left to right. Don't unfold; instead, fold again; and again; and again (always left to right). Now unfold--how many creases are there? (This fold is called the Dragon Fold). 

This table gives the sequence of creases formed at each stage—1 indicates that the first fold indicates a crease made the first time you fold; 2 indicates the folds made the 2^nd time you fold, etc.:

You can easily see the number of new creases doubles from the previous iteration with each new fold, and it should be clear from all of what’s here that 1 + 2 + 4 + …. + n = 2ⁿ – 1!

The Real Problem: How are Problem 1 and Problem 2 related? 

We hope you can now see the connection!