NYT Article on Indiana Puzzle Exhibition

[ewmayer]

http://www.nytimes.com/2006/07/25/science/25puzz.html

(Since NYT online articles have a distressing habit of either vanishing or getting switched to for-pay-only mode after a few weeks, I've also created an unofficial Permalink.)

One strange thing (at least on a quick initial reading) - the article mentions that for the 65-ring Chinese puzzle, a perfect solution requires 18446744073709551616 = 2⁶⁴ moves, which would seem to generalize straightforwardly to 2^{(number of rings) - 1} moves. Thus, for the "classic" 9-ring version of the same puzzle I would've expected a minimum of 256 moves to be required, but the article says the 9-ring version needs 341 moves for an ideal solution. Am I missing something? (I suppose actually buying one and trying it out might help, but if the formula were something more complicated than the aforementioned power-of-2 formula, I would certainly not expect the 65-ring version to have such a simple form.)

[fetofs]

Originally Posted by ewmayer

One strange thing (at least on a quick initial reading) - the article mentions that for the 65-ring Chinese puzzle, a perfect solution requires 18446744073709551616 = 2⁶⁴ moves, which would seem to generalize straightforwardly to 2^{(number of rings) - 1} moves. Thus, for the "classic" 9-ring version of the same puzzle I would've expected a minimum of 256 moves to be required, but the article says the 9-ring version needs 341 moves for an ideal solution. Am I missing something? (I suppose actually buying one and trying it out might help, but if the formula were something more complicated than the aforementioned power-of-2 formula, I would certainly not expect the 65-ring version to have such a simple form.)

The strangeness comes from the fact Slocum mentioned two different rulesets. The minimum number of moves needed for n rings is ceil(2/3(2^n-1)). If you can move the two end rings simultaneously, the formula is 2^(n-1) - (n+1 % 2). (% is the modulo operation, just so I wouldn't write any non-math symbol, like even and odd :] )

You can see the two sequences at Sloane, here and here.

[victor]

"Do it yourself" http://staff.ccss.edu.hk/jckleung/ninering/ ;)