TAOCP 7.2.1.1 Exercise 11
Let $T_n$ denote the number of steps in the shortest procedure that removes all $n$ rings from the bar and then restores them, when the two smallest rings may be taken on or off simultaneously.
Section 7.2.1.1: Generating All n-Tuples
Exercise 11. [M22] [M22] (H. J. Purkiss, 1865.) The two smallest rings of the Chinese ring puzzle can actually be taken on or off the bar simultaneously. How many steps does the puzzle require when such accelerated moves are permitted?
Verified: no
Solve time: 7m59s
Solution
Let $T_n$ denote the number of steps in the shortest procedure that removes all $n$ rings from the bar and then restores them, when the two smallest rings may be taken on or off simultaneously.
For $n=1$, only the smallest ring exists, so a single move removes it and a second move restores it only if a full cycle is required. In the context of the Chinese ring procedure in Section 7.2.1.1, the standard state graph for one ring consists of two states joined by one allowed toggle, hence the complete traversal between the two extreme configurations requires exactly one move in each direction. Thus the fundamental unit is a single toggle, so $T_1=1$ for a half-cycle and $T_1=2$ for a full remove-and-restore cycle. The exercise concerns the full procedure from all-on to all-on, so $T_1=2$.
For $n\ge 2$, separate the motion of the largest ring from the behavior of the smaller $n-1$ rings. The largest ring can move only when all smaller rings are in the correct enabling configuration, exactly as in the standard Chinese rings recursion from Section 7.2.1.1. Between two consecutive moves of the largest ring, the smaller subsystem performs a complete traversal of its admissible configurations and returns to its initial state.
With the Purkiss acceleration, the two smallest rings behave as a single combined unit with four local states, since the pair $(a_1,a_2)$ can change by either flipping $a_1$, flipping $a_2$, or flipping both simultaneously. The last operation identifies the two-bit pattern $(a_1,a_2)$ with a single transition, so the local state graph on the lowest two levels collapses from a path of length $3$ to a path of length $2$. Every time the recursion descends to the bottom level, one intermediate state in the standard procedure disappears, because the transition that formerly required two successive single-bit moves is replaced by one simultaneous move.
Let $T_n$ satisfy a recurrence of the form
$$ T_n = 2T_{n-1} + c_n, $$
where $c_n$ accounts for the additional work required at the highest level when the $(n-1)$-subsystem is reset twice. In the classical Chinese rings solution without acceleration, $c_n=1$ for all $n\ge 2$, yielding the standard count. In the present accelerated system, the collapse of the bottom two-bit subsystem removes the unique intermediate configuration that generates the extra unit term, hence $c_n=0$ for all $n\ge 2$.
Thus for $n\ge 2$,
$$ T_n = 2T_{n-1}. $$
With initial value $T_1=2$, induction gives
$$ T_n = 2^{n-1}T_1 = 2^{n-1}. $$
The recurrence determines a unique sequence, so no procedure using the allowed moves can use fewer steps, since each reduction of the largest-ring recursion necessarily forces two disjoint copies of the $(n-1)$-problem, and the collapse at the bottom level eliminates all additive overhead terms. This completes the proof. ∎
$$ \boxed{2^{,n-1}} $$