Day 14: CM, Page 1

Day 14: The first page of Concrete Mathematics. "This chapter explores three sample problems that give a feel for what's to come... their solutions all use the idea of recurrence" (CM p.1)

The first page explains the Tower of Hanoi problem. "We are give a tower of eight disks, initially stacked in decreasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller" (CM p.1). This is a famous problem in computer science. Most CS students are exposed to it at some point. The picture below shows a solution with four disks.


Here is a brief description of the legend behind the problem:

There is a legend about a Vietnamese or Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, since that time.... According to the legend, when the last move of the puzzle is completed, the world will end.
- wikipedia

There is no discussion of a solution on the first page, only a description of the problem. We'll save discussion of the solution for tomorrow.