NYT Article on Indiana Puzzle Exhibition
 

[url=http://www.nytimes.com/2006/07/25/science/25puzz.html]http://www.nytimes.com/2006/07/25/science/25puzz.html[/url]

(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 [url=http://hogranch.com/mayer/nyt_puzzle_07.25.2006.html]Permalink[/url].)

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[sup]64[/sup] moves, which would seem to generalize straightforwardly to 2[sup](number of rings) - 1[/sup] 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.)

[QUOTE=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[sup]64[/sup] moves, which would seem to generalize straightforwardly to 2[sup](number of rings) - 1[/sup] 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.)[/QUOTE]

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, [URL=http://www.research.att.com/~njas/sequences/A000975]here[/URL] and [URL=http://www.research.att.com/~njas/sequences/A051049]here[/URL].

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