Tower of Hanoi

Long ago in Brahma, or was it Bali, maybe it was Burma, definitely NOT Boston, the god was Brahma, or was it Buddah, definitely not Bob, a group of Hindu priests were charged with the daunting task of moving 64 giant golden disks stacked on a giant pole to a different pole. Why? 'cause they were told to by someone of great importance. The disks were originally stacked so that the largest disk was on the bottom, and each successive stacked disk was slightly smaller in diameter (radius, circumference, surface area, and volume too). The priests had to not only move ginormous golden disks, but there were rules too! Arrrg, rules.

In the process of moving disks, there were only two other poles on which the could (and had to) temporarily stack the disks. Additionally, and this one's the real kicker, no disk of larger radius could be stacked upon a disk with smaller radius. Great.

As if that wasn't enough for them to decide to abandon the project and possibly their religion, the great, superior being that ordered them to do such a random, arduous task instructed them that upon completion of the restacking, the temple would turn to dust and the world would VANISH, including all the fruits of their ridiculous labor.

With blind, faithful religious fervor, they set out, never bothering to "hustle," or to actually calculate how long the task would take them.

That's where I come in.

Before determining how long it will take them, we need to determine how many moves they will have to make with the disks. For the sake of clarity and conserving energy, I'll start small.

A typical modern puzzle has 6-10 smaller disks with 3 dowel rods. Something like this:
One way to see if there is a way to "count" the number of total moves for n disks is to start with one disk, then two, then three, etc. and look for a pattern. A mental or actual experiment would yield the following results:

• one disk takes one move
• two disks takes three moves
• three disks takes seven moves
• four disks takes fifteen moves

Continuing in such a manner will eventually lead one to the formula that for n disks, it will take 2^n - 1 moves. For example, four disks: n = 4. 2^4 = 16, and 16-1 = 15. This equation can also be mathematically derived by defining a recursive relation, then reducing it down to the finite sum of a geometric series. I won't get into that here, but ask me to show you in person some time . . .

So as it turns out, in the case of the Hindu priests, it would take one move less than 2^64. Wow. In case you're wondering, that comes out to

18,446,744,073,709,551,615 moves!

That's JUST over 18 quintillion moves. Assuming these priest worked in shifts around the clock, 24 hours a day, 7 days a week, 365 days a year, not even taking leap day off, not even taking time out to update their Facebook status, making an astounding and doubtful ONE MOVE PER SECOND, it would take them a shad (shade + tad) over 580 BILLION years pull it off . . . only to be reduced to ashes at the end.

Totally anticlimactic. Think about THAT next time someone knocks over your house of cards or destroys your sand castle.