The Tower of Hanoi Story
| Taken
From W.W. Rouse Ball & H.S.M. Coxeter, Mathematical Recreations
and Essays, 12th edition. Univ. of Toronto Press, 1974. |
| The
De Parville account of the origen from La Nature, Paris,
1884, part I, pp. 285-286. |
| In the great temple at Benares beneath
the dome that marks the centre of the world, rests a brass plate
in which are fixed three diamond needles, each a cubit high and
as thick as the body of a bee. On one of these needles, at the
creation, God placed sixty-four discs of pure gold, the largest
disk resting on the brass plate, and the others getting smaller
and smaller up to the top one. This is the tower of Bramah. Day
and night unceasingly the priest transfer the discs from one
diamond needle to another according to the fixed and immutable
laws of Bramah, which require that the priest on duty must not
move more than one disc at a time and that he must place this
disc on a needle so that there is no smaller disc below it. When
the sixty-four discs shall have been thus transferred from the
needle which at creation God placed them, to one of the other
needles, tower, temple, and Brahmins alike will crumble into
dust and with a thunderclap the world will vanish. |
| The number
of separate transfers of single discs which the Brahmins must
make to effect the transfer of the tower is two raised to the
sixty-fourth power minus 1 or 18,446,744,073,709,551,615 moves.
Even if the priests move one disk every second, it would take
more than 500 billion years to relocate the initial tower of
64 disks. |
|
Assignment - Part
1
|
Solve some versions of
the Tower of Hanoi problem that involve fewer disks. Namely,
consider a problem in which there
- is a single disk on a needle
(peg). Transfer this 1 disk from its initial needle (or peg)
to one of the other pegs.
- are two disks on a peg. Transfer
these 2 disks from their initial needle (or peg) to one of the
other pegs.
- are three disks on a peg. Transfer
these 3 disks from their initial needle (or peg) to one of the
other pegs.
- are four disks on a peg. Transfer
these 4 disks from their initial needle (or peg) to one of the
other pegs.
- are five disks on a peg. Transfer
these 5 disks from their initial needle (or peg) to one of the
other pegs.
Keep a CLOG (a cognitive
log) of your thinking as you work on this problem....and try,
at least initially to think about the problem in your "head"
-- that is, try not to use paper and pencil to keep track of
the problem......Ideally, your CLOG should be spoken into a tape
recorder so you can't go back and look at your earlier thoughts....so
if you can not do it this way then write down your thoughts but
avoid looking back at what you have written until you have completed
the exercise.
Try to record your errors as
well as your successes.....errors are often the most interesting
data from which to determine something about the way we are thinking
about something.
When finished, type up, if you
can your CLOG - preferably in WORD or in some other environment
which you can same as a pdf document. As you type it or re-write
it edit it only to put it in a form that someone else (namely,
me) could follow what you were thinking.
|
Assignment - Part 2
| After reading over
the Appendix of your text...go back to your CLOG and see what
aspects of your thinking about the problem can be represented
in the syntax of First Order Logic(FOL). Minimally, try to represent
the states of the solution sequence for the 3-disk problem in
FOL. See if you can determine why some aspects of your CLOG are
difficult or impossible to represent in the syntax of FOL. |
|
|
