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 4 of 4: Delete middle marbles to finish the induction

Previous step Next step

\text{Delete }2,\ldots,2^{m-1}\ \Longrightarrow\ 2^{m-1}+1\text{ marbles win in }m\text{ boxes, contradiction}\ \Longrightarrow\ n\le 2^{k-1}

Detailed analysis

Now delete marbles $2,\ldots,2^{m-1}$ from the post- $X$ play. Marble $1$ then only ever hops between empty boxes, permanently occupying one box and blocking any marble $\ge 2^{m-1}+1$ from entering it. Hence the remaining $2^{m-1}+1$ marbles (namely $2^{m-1}+1,\ldots,2^m+1$ ) achieve isolation of $2^m+1$ using only the other $m$ boxes, again contradicting the induction hypothesis. Thus no win is possible when $n\ge 2^{k-1}+1$ , and Cathy wins if and only if $n\le 2^{k-1}$ .