[math-fun] State Diagram of Hanoi
From: "Guy Haworth" <g.haworth@reading.ac.uk> [asked about numbering states]
From: Dan Asimov <dasimov@earthlink.net> what is an algorithm for using the fewest moves [between two states]?
From: "Andy Latto" <andy.latto@pobox.com> [proof that all states are connected, by induction adding the smallest disk to a solution for the others]
From: "Fred lunnon" <fred.lunnon@gmail.com> [obvious base-3 numbering, optimized base-2 numbering based on the standard solution]
Call the biggest disk 1, the next smallest 2, etc. The state diagram for one disk is a triangle: 1.. .1. ..1 The state diagram for n+1 disks replaces each vertex in the diagram for n disks with a triangle. For instance, for two disks: 21 . . 1 2 . 1 . 2 | \ . 2 1 . 1 2 . . 21 2.1 -- 2 1 . . 21 . Notice that the position of disk 2 is rotated in each of the three sub-triangles. This is like a Gray code, which you can construct from binary by exoring each bit with all the previous bits. So, each state can be assigned an (x,y) by going from the biggest to smallest disk (maybe a right rather than an equilateral triangle?). Also pretty easy to find the three (or two) states reachable from here and their (x,y) positions. Here's an algorithm for finding one of the shortest paths from where you are to target state T: while you're not at T: move to (one of) the reachable state(s) closest (in space) to T Pretty easy to encode the x and y numbers within a single base-three number if you like. You can also just skip the (x,y), let each digit stand for one of three directions, and choose the best move based on the most-significant different digit between the reachable positions. Giving the states (x,y) positions shows ties sometimes, and breaks what are really ties other times, You might say Gray code is a simplified Towers of Hanoi problem. --Steve -- My apples and oranges are beyond compare!
A diagram I like with the Hanoi puzzle (for 4 disks): pile_0 pile_+ pile_- moved summary direction disk of move 0: 1111 .... .... .... 0 0 0 0 1: 111. .... ...1 ...1 0 0 0 - 1 2: 11.. ..1. ...1 ..1. 0 0 + - 0 3: 11.. ..11 .... ...1 0 0 + + 1 4: 1... ..11 .1.. .1.. 0 - + + 1 5: 1..1 ..1. .1.. ...1 0 - + 0 1 6: 1..1 .... .11. ..1. 0 - - 0 0 7: 1... .... .111 ...1 0 - - - 1 8: .... 1... .111 1... + - - - 0 9: .... 1..1 .11. ...1 + - - + 1 10: ..1. 1..1 .1.. ..1. + - 0 + 0 11: ..11 1... .1.. ...1 + - 0 0 1 12: ..11 11.. .... .1.. + + 0 0 1 13: ..1. 11.. ...1 ...1 + + 0 - 1 14: .... 111. ...1 ..1. + + + - 0 15: .... 1111 .... ...1 + + + + 1 The rightmost column corresponds to the direction of the move made, it is the period-doubling sequence. Left from it the base-3 representation, Not all base-3 words occur. One more left the ruler function (aka bit changed with binary Gray code), telling which disk to move. The _untouched_ pile with the n-th move is (+-)n mod 3, the sign being + if n even, else - About threads with math-fun: I wondered why the threads are broken so often, here is why: The list sets a Reply-to to firstly the real sender, then to the list. Now a reasonable mailer will set the In-Reply-To to the message ID of the real sender (see the header of this mail). FIX: set the Reply-to to _firstly_ math-fun, then to the person that sent the mail! Note if you mailer uses the heuristic to put messages with same subject into the same thread you may not be observing the phenomenon. P.S.: Another bad: people using the reply function to start another thread. Please don't!
Joerg Arndt wrote:
About threads with math-fun: I wondered why the threads are broken so often, here is why: The list sets a Reply-to to firstly the real sender, then to the list. Now a reasonable mailer will set the In-Reply-To to the message ID of the real sender (see the header of this mail).
FIX: set the Reply-to to _firstly_ math-fun, then to the person that sent the mail!
Note if you mailer uses the heuristic to put messages with same subject into the same thread you may not be observing the phenomenon.
This sounds like a conversation to have when Rich is around. Recall that he's away for a few weeks; my pinch-list-admin foo does not extend to poking at settings. I'd bring this up when he's back.
P.S.: Another bad: people using the reply function to start another thread. Please don't!
(Aren't you deliberately breaking your own advice with this message?) --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
* Michael Kleber <michael.kleber@gmail.com> [Feb 12. 2008 13:46]:
Joerg Arndt wrote:
[...]
P.S.: Another bad: people using the reply function to start another thread. Please don't!
(Aren't you deliberately breaking your own advice with this message?)
Oh! ... but only "unter erheblichen inneren Vorbehalten" 8-)) (dunno what that would be in English)
I was recently looking at a beautiful Kissing Spheres page: http://pagesperso-orange.fr/math-a-mater/pack/packing.htm About halfway down the page, there is a simple question: Five colors suffice ? Interesting question. --Ed Pegg Jr http://www.mathpuzzle.com/
On 3/5/08, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
I was recently looking at a beautiful Kissing Spheres page:
http://pagesperso-orange.fr/math-a-mater/pack/packing.htm
About halfway down the page, there is a simple question: Five colors suffice ? Interesting question.
Consider the natural way to generate the tiling: start with a large (outer) sphere with three tangent spheres inside; then at each generation place a new smaller sphere within every pre-exisiting cavity. Each new sphere is tangent to just four larger ones; therefore it may be coloured using the fifth colour. A similar argument shows that n+2 colours suffice in n-space. WFL
On 3/6/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 3/5/08, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
I was recently looking at a beautiful Kissing Spheres page:
http://pagesperso-orange.fr/math-a-mater/pack/packing.htm
About halfway down the page, there is a simple question: Five colors suffice ? Interesting question.
Consider the natural way to generate the tiling: start with a large (outer) sphere with three tangent spheres inside; then at each generation place a new smaller sphere within every pre-exisiting cavity. Each new sphere is tangent to just four larger ones; therefore it may be coloured using the fifth colour.
A similar argument shows that n+2 colours suffice in n-space.
WFL
Incidentally, every Apollonian tiling is equivalent to every other under some Moebius (conformal) transformation: so a 5-colouring of one such sphere- packing immediately yields a 5-colouring of all such. WFL
participants (5)
-
Ed Pegg Jr -
Fred lunnon -
Joerg Arndt -
Michael Kleber -
Steve Witham