Simanaitis Says

On cars, old, new and future; science & technology; vintage airplanes, computer flight simulation of them; Sherlockiana; our English language; travel; and other stuff

THE TOWER OF HANOI—AND CANNONBALLS

IS THE Tower of Hanoi a kid’s game? A mathematical endeavor connected to cannonballs? Or a calendar to the end of the universe?

Yes, yes and yes.

m

A classic Tower of Hanoi, this one with eight discs. Construction by User:Evanherk.

Start with a number of discs of decreasing size (hence the Tower moniker). Reconstruct the tower at one of two other locations while obeying the following rules: 1. Only one disc can be moved at a time among the three locations. 2. Only a topmost disc can be moved. 3. No disc may be placed upon a smaller disc.

m

A two-disc Tower of Hanoi, step-by-step.

A two-disc game is easy, in only three moves. A three-disc version takes a bit more cleverness. Use a quarter, nickel and dime to figure out its seven steps. Four discs offer plenty of dead ends and a solution in 15 steps. See http://vimeo.com/31091547 for its video by Pablo Campos.

m

Guess the pattern.

 

In fact, a Tower of Hanoi with five discs requires 31 moves; n discs requires 2n – 1 moves, a number that grows exponentially large.

Which brings us to the end of the universe. Along the banks of the Ganges in northern India lies the temple of Kashi Vishwanath.

m

Kashi Vishwanath, one of the most sacred of Hindu temples.

At the beginning of time, the temple was given the Tower of Brahma, 64 discs, each smaller than the one beneath it, arranged on one of three spires. Since then, priests have been moving the discs among the spires with the immutable rules of the Brahma: Move only one topmost disc at a time; never offend a disc by placing a larger one upon it.

When the Tower of Brahma is reconstructed on the other spire, the priests’ work is completed and the universe ends.

Rest easy, as this requires 264 – 1 moves. If these 18,446,744,709,551,615 moves are performed at a rate of one per second, this is slightly more than 580 billion years.

The French mathematician Édouard Lucas is credited with introducing the Tower of Hanoi to the west. Under the nickname N. Claus de Siam, an anagram of Lucas d’Amiens, he marketed the idea as a kid’s game.

m

François-Édouard-Anatole Lucas, 1842 – 1891, French mathematician, who first publicized the Tower of Hanoi in 1883.

Lucas is also known for first solving what has come to be known as the Cannonball Problem, related to another called the Diophantine Equation. How many cannonballs are required to build a square pyramid from a square array of cannonballs?

m

At left, a tetrahedral pyramid (not our goal); at right, a square pyramid.

If you start with a two-by-two array, it’s easy to build a tetrahedral pyramid with three on the base and one on top, but this isn’t our goal. We want a square pyramid, one with a square base, not a triangular one.

This proves a great deal more difficult. Lucas showed that a 70-by- 70 array of 4900 cannonballs could be rearranged to build a square pyramid of 24 packed layers. What’s more, he conjectured that this was the only solution. Others have since proved that Lucas was correct in this.

And, as an example of  mathematical truth popping up in other areas, it turns out the cannonball solution has relevance in the modern concept of string theory.

I for one am pleased the Tower of Brahma gives us all this time for mathematical discovery. ds

© Dennis Simanaitis, SimanaitisSays.com, 2014

One comment on “THE TOWER OF HANOI—AND CANNONBALLS

  1. Bill Urban
    May 8, 2014

    Defeatthedebt.com offers this “one per second” lesson for the numbers challenged: count to one million saying one number each second and it takes about 12 days. But counting to one billion takes about 31 years.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: