Problem 4

Let

n

and

k

be positive integers. Cathy is playing the following game. There are

n

marbles and

k

boxes, with the marbles labelled

1

n

. Initially, all marbles are placed inside one box. Each turn, Cathy chooses a box and then moves the marble with the smallest label, say

i

, to either any empty box or the box containing marble

i+1

. Cathy wins if at any point there is a box containing only marble

n

. Determine all pairs of integers

(n,k)

such that Cathy can win this game.

Step 2 of 4: Induction for achievability at

n=2^{k-1}

Previous step Next step

n=2^{k-1}\ \Longrightarrow\ \text{Cathy can isolate marble }n\text{ using }k\text{ boxes}

Detailed analysis

Proceed by induction on $k$ ; $k=1$ , $n=1$ is trivial. Suppose $m$ boxes suffice for $2^{m-1}$ marbles, and consider $m+1$ boxes with $2^m$ marbles. Using $m$ boxes (keeping one box $B$ empty) apply the $m$ -box winning sequence to the top movements until only marbles $2^{m-1},\ldots,2^m$ remain in the starting box. Move $2^{m-1}$ into the empty box $B$ , then run the initial sequence in reverse treating $B$ as the target box; this collects $1,\ldots,2^{m-1}$ into $B$ , leaves $2^{m-1}+1,\ldots,2^m$ in the starting box, and frees the other $m-1$ boxes. Finally apply the $m$ -box strategy to the $2^{m-1}$ marbles $2^{m-1}+1,\ldots,2^m$ using the $m$ boxes outside $B$ to isolate $2^m$ . The same strategy works for any $n\le 2^{k-1}$ .