[math-fun] towers of Hanoi
The recursive solution to the Towers of Hanoi is well known. Here is a puzzle which a friend of mine and I found more challenging than we thought at first: give an _iterative_ algorithm, i.e., one which has no memory, and chooses its next move based only on the current state of the puzzle (and perhaps the knowledge of the initial and final peg for the entire stack of disks). Hint: first come up with an iterative algorithm for the Gray code. - Cris p.s. The Santa Fe Institute has a copy of the French recreational mathematics magazine where Edouard Lucas proposed the Towers of Hanoi puzzle (he also, confusingly, mentions Benares). I like to point out that if a Vietnamese mathematician had invented the puzzle, it would presumably be called the Towers of Eiffel.
This used to be a famous puzzle among the high school math club circles I moved in 45 years ago. Once you know the iterative solution it becomes much easier to execute that the recursive one. On Sun, Jul 7, 2019, 4:31 PM Cris Moore <moore@santafe.edu> wrote:
The recursive solution to the Towers of Hanoi is well known. Here is a puzzle which a friend of mine and I found more challenging than we thought at first: give an _iterative_ algorithm, i.e., one which has no memory, and chooses its next move based only on the current state of the puzzle (and perhaps the knowledge of the initial and final peg for the entire stack of disks).
Hint: first come up with an iterative algorithm for the Gray code.
- Cris
p.s. The Santa Fe Institute has a copy of the French recreational mathematics magazine where Edouard Lucas proposed the Towers of Hanoi puzzle (he also, confusingly, mentions Benares). I like to point out that if a Vietnamese mathematician had invented the puzzle, it would presumably be called the Towers of Eiffel.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The iterative solution is described on Wikipedia. Due to "the march of the monoculture", all phrases "Tower of _country_" are becoming more and more difficult to distinguish (cf. Keangnam Hanoi Landmark Tower ). Some people are happy to have standard problems and standard solutions, but if you are really where you say you are, isn't the focus more on complex systems? Here's an idea . . . The "firefly algorithm" has been criticized as only trivially different from particle swarm optimization [1]. This is not even the worst problem--light emission and absorption are not isotropic phenomena relative to insect biology. So why doesn't this "firefly algorithm" at least account for the vector nature of the insect body? --Brad [1] https://en.wikipedia.org/wiki/Firefly_algorithm On Sun, Jul 7, 2019 at 3:31 PM Cris Moore <moore@santafe.edu> wrote:
p.s. The Santa Fe Institute has a copy of the French recreational mathematics magazine where Edouard Lucas proposed the Towers of Hanoi puzzle (he also, confusingly, mentions Benares). I like to point out that if a Vietnamese mathematician had invented the puzzle, it would presumably be called the Towers of Eiffel.
participants (3)
-
Allan Wechsler -
Brad Klee -
Cris Moore