a.k.a.a.k.a. Cardan's Rings, Baguenaudier

Very old design, this one owned by J. A. Storer's grandfather, circa 1900?

(2.4 by 8.5 by 1.75 inches high wood box with key and 6.5 inch long puzzle)

Each ring is attached to a post and, except for the rightmost ring (the one farthest from the handle), each goes around the post to its right (and under the ring to its right). Rings that are not on the skewer can pass sideways through the skewer. Initially, the skewer goes through all the rings. The goal is to remove the skewer from the rings (and then put it back).

Solution:Observe that the only two ways to move a ring are to put the rightmost ring on or off the skewer, or, a ring can be put on or off the skewer if and only if the ring to the immediate right is on but all other rings to the right are off. This leads to a simple iterative solution in a similar spirit to theTowers Of Hanoipuzzle; we use the phrase "complement a ring" to mean take it off if it is on or put it on if it is off:Take the rings off:Start with all rings ON.

repeatMake the only legal move that is not complementing the rightmost ring.

Complement the rightmost ring.

untilall rings are OFFPut the rings on:Start with all rings OFF.

repeatComplement the rightmost ring.

Make the only legal move that is not complementing the rightmost ring.

untilall rings are ON

Gray codes of n bits are a binary counting system where only one bit changes from the representation for an integerito the representation ofi+1, 0 &le i &le 2^{n}- 1. Let B(i,n) denote the standard binary representation ofiusingnbits, G(i,n) the Gray code ofnbits,XORthe exclusive or operation, andShiftRightthe operation of shifting the bits of a code one position to the right (discarding the rightmost bit and setting the leftmost bit to 0). Although Gray codes are not in general unique, a standard form is one where:G(Here is the correspondence fori,n) = B(i,n) XOR ShiftRight(B(i,n))n=4;

all 4 bit binary sequences are shown, but we only need entries 0 through 10:Observe that when going from one row to the next, every other time it is the rightmost bit that changes, and for the other times a bit changes where the bit to its right is 1 and all bits to the right of that are 0. Hence, if we let 0 denote a ring off and 1 denote a ring on, then one can see that the Gray code sequence corresponds to our solution for the Chinese rings; that is, for the case of 4 rings, taking them off corresponds to moving from row 10 to row 0 in the above table, and putting them on corresponds to moving from row 0 to row 10.

The number of moves to put the rings on or off is the same, so let's count the number of moves to take them off. We can express our iterative solution recursively as follows:Represent the rings as an array R[1] .. R[n] where R[1] corresponds to the leftmost ring, and R[The number of moves M(i] is 0 if the corresponding ring is off and 1 if it is on. Let FLIP(i) denote complementing R[1] through R[i], then set all positions to 1 and call FLIP(n):

procedureFLIP(i)

ifi=1thenComplement R[1].

else ifi=2thenComplement R[1] and R[2].

else doFLIP(i-2)

Complement R[i].

FLIP(i-2)

FLIP(i-1)

endn) for FLIP(n) is given by the recurrence relation:M(Two simple proofs by induction, one for whenn) = M(n-1) + 2M(n-2) + 1nis even and one for whennis odd, can now be used to show that the solution is:(2The first few values of M(^{n+1}-2)/3 ifnifnis even

(2^{n+1}-1)/3 ifnifnis oddn) are:1, 2, 5, 10, 21, 42, 85, 170, 341, 682. ...For the puzzle pictured here, which has seven rings, the solution is 85 moves.

Sometimes people count the moving of the two rightmost rings as one move, in which case it can be shown that the number of moves is reduced to:Note:2And now the first few solution values become:^{n-1}-1 ifnis even

2^{n-1}ifnis odd1, 1, 4, 7, 16, 31, 64, 127, 256, 511, ...