The Chinese Rings and the Gray Code

What’s going on

The Chinese rings puzzle, or baguenaudier, is a row of rings on a long wire loop. Each ring stands on a rod, and the rods are threaded through one another, so the rings cannot simply be pulled off. The goal is to free the loop.

Strip away the metal and two rules are left. Number the rings from the free end of the loop: ring 1, ring 2, and so on.

• Ring 1 can always go on or off.
• Any other ring can go on or off only when the ring just below it is on, and every ring below that one is off.

So ring 4 can move only when ring 3 is on and rings 2 and 1 are both off. So at most two moves are ever possible: ring 1, and the ring just above the lowest ring that is on. Click the rings in the scene above to try; the ones outlined in amber can move.

Write the position as 0s and 1s

Under each ring the scene writes 1 if it is on the bar and 0 if it is off. Every move changes exactly one digit. Three rings, all on, come off like this:

111 → 110 → 010 → 011 → 001 → 000

Five moves, and you can check that there is no shorter way. Now look at the table beside the puzzle. It counts 0, 1, 2, 3, … but not in ordinary binary. In ordinary binary, going from 3 to 4 changes three digits at once: 011 becomes 100. In the Gray code column, neighbours always differ in exactly one digit, and that is the column the rings follow. Solving the puzzle is counting down in Gray code.

Here is how the table is built. Start with 0 and 1. To get the codes with one more digit, write the list, then the same list backwards (as in a mirror), put 0 in front of the first half and 1 in front of the second half:

• 0, 1
• 00, 01, 11, 10
• 000, 001, 011, 010, 110, 111, 101, 100

Where the two halves meet, only the new front digit changes, and inside each half the old list already changes one digit at a time. That is why it is called the reflected Gray code.

How many moves?

Since the rings walk along the list one step at a time, a position’s place in the list is exactly the number of moves needed to clear it.

There is a neat way to read it. Go along the digits from the left, keeping a running answer in binary: each new binary digit equals the previous binary digit if the Gray digit is 0, and flips it if the Gray digit is 1. For 1 1 1 1 1 (five rings, all on) that gives 1 0 1 0 1, which is 21. Press Solve in the scene with five rings: it takes 21 moves.

All rings on gives 1, 2, 5, 10, 21, 42, 85, 170, 341 moves for 1 to 9 rings. Each extra ring roughly doubles the work: the count is 2ⁿ⁺¹ ÷ 3, rounded down. We checked these numbers by letting a computer search through every possible position of up to 12 rings.

The hardest start of all is not all rings on. Choose only the last ring on in the scene: then the rings must pass through every one of the 2ⁿ positions, which takes 2ⁿ − 1 moves. That is 511 moves for nine rings.

Try it yourself

1. Six rings

How many moves does it take to free six rings that all start on the bar?

Answer

42. Read 1 1 1 1 1 1 with the running-answer rule: the binary digits are 1 0 1 0 1 0, which is 32 + 8 + 2 = 42. (Check: 2⁷ ÷ 3 ≈ 42.7, rounded down.)

2. Halfway through

You find a puzzle of four rings with rings 4, 3 and 1 on and ring 2 off: 1 1 0 1. How many moves are still needed?

Answer

9. The running rule turns the Gray code 1 1 0 1 into binary 1 0 0 1, which is 8 + 1 = 9. Set the scene to four rings and play it out to check.

3. The busiest ring

Starting with only ring 5 on, the rings make all 31 moves of the full Gray code. How many of those moves are made by ring 1?

Answer

16, every other move. Only two moves are ever possible and one of them undoes the last move, so ring 1 and the other rings take turns: ring 1 makes moves 1, 3, 5, …, 31. Similarly ring 2 moves 8 times, ring 3 four times, ring 4 twice and ring 5 once: 16 + 8 + 4 + 2 + 1 = 31.

Go deeper

• The code is named after Frank Gray, an engineer at Bell Labs, who described it in a patent filed in 1947 for turning signals into digital pulses.
• Rotary encoders, the sensors that tell a machine how far a shaft has turned, often mark their discs in Gray code. As the disc turns, only one track changes at each boundary, so a reading taken right on a boundary is off by at most one step.
• The rings puzzle is much older than the code: the Italian scholar Gerolamo Cardano described it in the sixteenth century.