Question 9
C4 (EST) There are $n+1$ fixed positions in a row, labeled $0$ to $n$ in increasing order from right to left. Cards numbered $0$ to $n$ are shuffled and dealt, one in each position. The object of the game is to have card $i$ in the $i$th position for $0\le i\le n$. If this has not been achieved, the following move is executed. Determine the smallest $k$ such that the $k$th position is occupied by a card $l\gt k$. Remove this card, slide all cards from the $(k+1)$th to the $l$th position one place to the right, and replace the card $l$ in the $l$th position.
(a) Prove that the game lasts at most $2^n-1$ moves.
(b) Prove that there exists a unique initial configuration for which the game lasts exactly $2^n-1$ moves.
(a) Prove that the game lasts at most $2^n-1$ moves.
(b) Prove that there exists a unique initial configuration for which the game lasts exactly $2^n-1$ moves.