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 1 of 4: Consecutive-interval invariant and reversibility

Previous step Next step

\text{Every non-empty box holds a consecutive interval }\{a,a+1,\ldots,b\};\ \text{moves are reversible}

Detailed analysis

Initially the starting box holds $\{1,\ldots,n\}$ . Because Cathy only ever removes the minimum of a box and places it into an empty box or onto the minimum $i+1$ of another box, every non-empty box always holds a consecutive block of labels, and the reverse of any legal move is also a legal move.