Timeline for Number of Configurations in the optimal Hanoi tower
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2013 at 14:20 | comment | added | kakia | "It seems forcing the number of disks on all 3 towers specifies a unique position" _ this seems to imply that $2^n \in O(n^3)$ :) | |
| Jul 2, 2013 at 17:08 | comment | added | dspyz | Shouldn't the number of times a hanoi position is encountered in an optimal strategy always be zero or one? After all, if you re-encounter the same position twice, then you're clearly not solving the problem optimally. It seems forcing the number of disks on all 3 towers specifies a unique position. Where's the variable here? | |
| May 2, 2013 at 21:25 | history | edited | kakia | CC BY-SA 3.0 |
added 450 characters in body; edited tags; edited title
|
| May 2, 2013 at 13:42 | comment | added | kakia | Well, I see these connections can be arbitrary and there might be no nice way to show the equivalence. I just wanted to have a closed formula for Hanoi tower configurations, from the computational perspective, formulas I see with the equal sequences can be calculated in linear time with respect to $n$, whilst recurrent formula for Hanoi configurations takes cubic time. | |
| May 1, 2013 at 14:22 | comment | added | Douglas Zare | These appear to be twice oeis.org/A197657, which mentions a definition of a meander. These are row sums of oeis.org/A194595, which filters the meanders. oeis.org/wiki/User:Peter_Luschny/Meander | |
| May 1, 2013 at 1:20 | comment | added | Douglas Zare | By the way, another way to state the recurrence is in terms of generating functions. Let $[x^ay^bz^c]f_k(x,y,z)$ be the number of positions along the shortest solution with $a$ in the original position, $b$ in the middle position, and $c$ in the target position. Then $f_{k+1}(x,y,z) = xf_k(x,z,y) +zf_k(y,x,z)$. | |
| May 1, 2013 at 0:55 | comment | added | Douglas Zare | I don't think the connection with Sierpinski's triangle helps here. The vertices of the Hanoi graph correspond to the $3^n$ legal positions. However, you only encounter $2^n$ positions as you solve it using a shortest solution, and these are just the solutions along one side of the triangle. However the Hanoi graph does answer mathoverflow.net/questions/128897/…. | |
| Apr 30, 2013 at 18:20 | comment | added | Barry Cipra | On further idle thought, let me change that "seems likely to" to a "might." The connection I thought I saw was illusory. But there might be one I didn't see. | |
| Apr 30, 2013 at 18:02 | comment | added | Barry Cipra | The explanation seems likely to be found in the connection between the Tower of Hanoi and the Sierpinski triangle (or gasket). See, for example, cut-the-knot.org/triangle/Hanoi.shtml | |
| Apr 30, 2013 at 11:54 | history | asked | kakia | CC BY-SA 3.0 |