lxvii. Chinese Rings (Baguenaudier)

Problem. The Chinese rings (Baguenaudier): $n$ rings on a bar. Ring $1$ can always be moved on or off; ring $i+1$ can be moved iff ring $i$ is on and rings $\mathrm{1..}i-1$ are off. Remove all rings.

Answer: $\lfloor 2^{n+1}/3\rfloor$ moves: $1,2,5,10,21,42,\dots$ The sequence of states visited is the reflected Gray code.

long long chineseRingsMoves(int n) { return (1LL << (n + 1)) / 3; }          // minimum moves to remove all n rings

Proof: the move count

Let $a_n$ be the minimum moves to remove $n$ rings. To remove ring $n$, rings $\mathrm{1..}n-2$ must be off and ring $n-1$ on: remove the first $n-2$ rings ($a_{n-2}$), move ring $n$ (1), put the first $n-2$ back ($a_{n-2}$, by reversibility), then remove the first $n-1$ rings ($a_{n-1}$). So $a_n=a_{n-1}+2a_{n-2}+1$ with $a_1=1$, $a_2=2$. The closed form $\lfloor 2^{n+1}/3\rfloor$ satisfies the same recurrence and initial values (check $2^{n+1}\mathrm{mod}3$ alternates between $1$ and $2$). The states form a path in which each move flips one ring, exactly the reflected Gray code sequence (Gray Code). Checked by BFS over all $2^n$ states for $n\le 14$.