| At time of publication: | University of York |
| Currently: | Lancaster University alan@hcibook.com |
Paper presented at BCTCS-9, York, March 1993.
Download full paper (PDF, 65K)
Full reference:
A. J. Dix (1993).
The Many Towers of Hanoi. (abstract only, part of Report of The Ninth British Colloquium on Theoretical Computer Science, March 29th-31st 1993).
Bulletin of the European Association for Theoretical Computer Science, 50.
http://www.hcibook.com/alan/papers/hanoi93/
Many years ago, in a lonely valley the foothills of the Himalayas, their lay two monasterys. In one of these were three crystal towers on which were stacked sixty-four golden rings of different sizes. Year by year the monks move the rings between the towers following the well known rules, and as is also well known when the task is finished the monks will sit back contented and the world disappear in a puff of smoke. Excitement mounted in the monastery, they had been at the task for four thousand years, and now over half of the disks had been moved. Recruitment was up, pilgrims and novices flocked to the monastery and across the valley their rival monastery looked on in despair. Then as the story goes, a wandering mathematician appeared and after scribbling on the back of a yak for a few moments declared that the world would be safe for another 450 billion years. Within days the pilgrims were dispersed and the towers fell into disrepute.
The abbot of the other monastery was not unduely alarmed at the demise of his rival, but saw that his own monastery was in need of a little publicity. If they should by chance find some towers of their own... But how many towers should there be? Too many towers would be a trifle expensive (have you ever tried to make a crystal tower), and besides if the task were to be finished in a few weeks and the world not end, what would people think? Yet if there were too few, and some inconvenient mathematician calculated the task would take millions of years to complete, it would lack popular appeal. What was needed was a task taking the odd thousand years, short enough to arouse interest, and long enough to hide away before it became a liability.