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 3 of 4: Key separation after move X

Previous step Next step

n=2^{k-1}+1\ \Longrightarrow\ \text{after the last exit }X\text{ of }2^{m-1}+1,\text{ marble }1\text{ never meets }\ge 2^{m-1}+1

Detailed analysis

We prove by induction on $k$ that $n=2^{k-1}+1$ is losing; $k=1$ , $n=2$ is clear since no move is possible with one box. Assume $m$ boxes cannot win for $2^{m-1}+1$ marbles, and suppose $m+1$ boxes could win for $2^m+1$ marbles. Let $X$ be the last move at which marble $2^{m-1}+1$ leaves the starting box. After $X$ , marbles $1,\ldots,2^{m-1}+1$ can never all lie in one box: otherwise reversing the moves from that moment back to $X$ and ignoring marbles $>2^{m-1}+1$ would win for $2^{m-1}+1$ marbles using only the $m$ non-starting boxes (since the starting box permanently holds marbles $>2^{m-1}+1$ after $X$ ), contradicting the induction hypothesis. Because boxes always hold consecutive intervals, this means after $X$ marble $1$ never shares a box with any marble $\ge 2^{m-1}+1$ .