2

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$ to $n$. Initially, all marbles are placed inside one box. Each turn Cathy chooses a box and then moves the marbles 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.

The solution to this question is $n \le 2^{k-1}$ according to the official solutions but the answer that I've gotten is entirely different. What is wrong in my approach?

My attempt:

All of the $n$ marbles are in $1$ of the $k$ boxes, let's call this the box $B_m$, the only thing we can do to seperate marble labelled $n$ is to remove all the marbles labelled from $1$ to $n-1$. Hence the only move that progresses the procedure is placing marble $1$ in any random box, then placing marble $2$ in another and so on till $k-1$ marbles occupy each $k-1$ boxes, next we transfer marble $k-2$ to the box having marble $k-1$, similarly we transfer all the marbles in a backwards way into the box containing marble $k-1$, we repeat this process, but now we only have $k-2$ boxes to work with. We repeat this process till we have no empty box. At this point, if $B_m$ has any more than 1 marble, then it becomes impossible to separate $n$ out. hence our equation: $$\frac{k(k-1)}{2} + 1 \ge n$$ $$\frac{k^2 - k + 2}{2} \ge n$$

However $2^{k-1} > \frac{k^2 - k + 2}{2}$, which makes my inequality weaker, what is the inconsistency with my method?

Rodrigo de Azevedo
  • 1
Aadi
  • 804
  • 1
    When someone says "the only move that ...", that triggers alarm bells in my head. EG Assuming your calculations are correct, you've only dealt with the case where the first few marbles are placed in distinct empty boxes. What about the case where Marble 1 is placed in box 1, and Marble 2 is placed in 2, THEN Marble 1 is placed in box 2? – Calvin Lin Mar 20 '23 at 22:51
  • @Calvin Lin My aim was to maximise n for a given k and yeah I could do that, but eventually I'd have to perform such an algorithm on different marbles so that I can fit in as many marbles as possible. I may be wrong and there may be a better method of arranging marbles, but I can't figure it out. For instance if there are 8 marbles and 4 boxes, the official solution states you can win but I say you can't – Aadi Mar 21 '23 at 08:33
  • 1
    Hint: For $k=4$, think about how we can make 1234 in the same box, and 5678 in the starting box. Your argument claims we cannot do that (since you have only combined the first $k-1$ marbles in one box). From there, we can win the game for 8, and the induction for $n \leq 2^{k-1}$ follows. – Calvin Lin Mar 21 '23 at 14:29

1 Answers1

2

When someone says "the only move that ... (without any justification)", that triggers alarm bells in my head because they are enforcing some structure without further substantiating that they have truly considered all cases.

For example, instead of placing the first $k-1$ marbles in individual boxes, another start could be:

Marble 1 is placed in box 1,
Marble 2 is placed in box 2,
THEN Marble 1 is placed in box 2.

(I was basically looking for the simplest approach that violates your "the only move ..." description. It wasn't guaranteed to do better, but as it turns out, that is sufficient.)

In particular, for $k=4, n = 8$, your approach gives us $123 \quad 45 \quad 6 \quad 78 $, and at most 3 marbles are in any non-starting box at any time.

Think about how my steps could allow us to place 1234 in the same box, and 5678 in the starting box, leaving the rest empty.
From there, show that we can win the game for 8.
In fact, using this observation, we can complete the induction for $n \leq 2^{k-1}$.

(We still have to show that for $n > 2^{k-1}$, this is impossible.)

Calvin Lin
  • 68,864