I'm not sure which is the official thread, so just in case The answer is all $(n,k)$ such that $n \le 2^{k-1}$. Note that if $(n,k)$ works, then $(z,k)$ for $z < n$ works too since while removing marbles from the first box, at some point we will have $z$ be the top marble of the first box. Let $f(k)$ be the largest $n$ that works, given $k$ boxes. It suffices to show $f(k) = 2^{k-1}$. First, observe that every box contains only marbles with consecutive labels, this is easy to see since if it has this property, the operations do not change it. Call the box in which all marbles are initially there as the source. Suppose a pile $(a+1, a+2, \cdots, a+b)$ is going to be formed, at some point, $a+b$ must be alone in its pile and the numbers $a+1, a+2, \cdots, a+b-1$ are all not at the source, call this the "formation point" Claim: At formation point of a pile with $x$ stones, if these stones are spread over $y$ boxes, then $x \le 2^{y-1}$ Proof: Ignore all boxes containing numbers not in $[a+1, a+x]$. Among the boxes containing these, we can ignore any number not in this range too, so since we're only dealing with these numbers, wlog assume they are $1,2,\cdots, x$. Since this is formation point, $x$ is in a unique box and since $x-1$ must be moved to this next, $x-1$ must also be in its unique box. Suppose at some point the numbers $x, x-1, x-2, \cdots, x- \alpha$ are in the pile and there are $m$ empty boxes, ignore all the other nonempty boxes now. Since we want to add $x - \alpha - 1$, this is just the game with $m+1$ boxes and wanting to isolate the maximal marble, which means the box containing $x - \alpha - 1$ can contain at most $2^m$ marbles by induction. Next, there are $m+1$ empty boxes, then $m+2$ and so on, so eventually, we could have added at most $1 + 2 + 4 + \cdots + 2^{y-2} = 2^{y-1} - 1$ pebbles to the pile so we indeed have $x \le 2^{y-1}$, as claimed. $\square$ To prove the bound for the problem, consider the pile with the number $1$, by the previous claim, it can have at most $2^{k-2}$ pebbles since there are at most $k-1$ empty boxes available. Once the pile is formed, since we dont touch it again, by induction the remaining game can have $2^{k-2}$ pebbles at most so overall, we can have at most $2^{k-1}$ pebbles, as needed. For the construction(which also motivates the entire proof), use the construction for $k-1$ to generate a $2^{k-3}$ pile, then use the construction for $2^{k-2}$ to generate a $2^{k-2}$ pile and do this until a $2^{k-k}$ pile, which overall uses $k-2$ boxes and $1 + 2 + \cdots + 2^{k-3} = 2^{k-2} - 1$ boxes, so now place the marble labelled $2^{k-2}$ in an empty pile. Next, use the procedure of the Claim to convert this into a since pile containing $2^{k-2}$ pebbles, now ignore this box and we've reduced this to the $k-1$ case, so we can indeed isolate the largest marble if $n \le 2^{k-1}$, as desired. $\blacksquare$

L567 wrote: I'm not sure which is the official thread It should be this one, since this was the first to be posted.

The other thread was here. Yannick points out that the rules of this game resemble the stacks of freecell solitaire (and other solitaire games), with $k$ cascades and a one-suit deck with $n$ cards. Indeed, the linked Wikipedia article writes that: Quote: The number of cards a player can move is equivalent to number of empty cells plus one, with that number doubling based on how many empty cascades there are. The mathematical equation for the number of cards that can be moved is $(2^M) \times (N + 1)$, where $M$ is the number of empty cascades and $N$ is the number of empty cells. The APMO problem is the special case $M = k-1$, $N = 0$.

So the outline I have:

Thus we just need to finish off with $f(1)=1$.

Oops…misread the problem, but somehow it is still solvable (pretty much equally fun). Imagine if you change the original condition to “initially each marble is placed in one of the k boxes”, it would give a different answer, but I do recommend you give it a try.

Solution ( Also done by L567) : The answer is all $(n,k)$ such that $n \le 2^{k-1}$. Note that if $(n,k)$ works, then $(z,k)$ for $z < n$ works too since while removing marbles from the first box, at some point we will have $z$ be the top marble of the first box. Let $f(k)$ be the largest $n$ that works, given $k$ boxes. It suffices to show $f(k) = 2^{k-1}$. First, observe that every box contains only marbles with consecutive labels, this is easy to see since if it has this property, the operations do not change it. Call the box in which all marbles are initially there as the source. Suppose a pile $(a+1, a+2, \cdots, a+b)$ is going to be formed, at some point, $a+b$ must be alone in its pile and the numbers $a+1, a+2, \cdots, a+b-1$ are all not at the source, call this the "formation point" Claim: At formation point of a pile with $x$ stones, if these stones are spread over $y$ boxes, then $x \le 2^{y-1}$ Proof: Ignore all boxes containing numbers not in $[a+1, a+x]$. Among the boxes containing these, we can ignore any number not in this range too, so since we're only dealing with these numbers, wlog assume they are $1,2,\cdots, x$. Since this is formation point, $x$ is in a unique box and since $x-1$ must be moved to this next, $x-1$ must also be in its unique box. Suppose at some point the numbers $x, x-1, x-2, \cdots, x- \alpha$ are in the pile and there are $m$ empty boxes, ignore all the other nonempty boxes now. Since we want to add $x - \alpha - 1$, this is just the game with $m+1$ boxes and wanting to isolate the maximal marble, which means the box containing $x - \alpha - 1$ can contain at most $2^m$ marbles by induction. Next, there are $m+1$ empty boxes, then $m+2$ and so on, so eventually, we could have added at most $1 + 2 + 4 + \cdots + 2^{y-2} = 2^{y-1} - 1$ pebbles to the pile so we indeed have $x \le 2^{y-1}$, as claimed. To prove the bound for the problem, consider the pile with the number $1$, by the previous claim, it can have at most $2^{k-2}$ pebbles since there are at most $k-1$ empty boxes available. Once the pile is formed, since we dont touch it again, by induction the remaining game can have $2^{k-2}$ pebbles at most so overall, we can have at most $2^{k-1}$ pebbles, as needed. For the construction(which also motivates the entire proof), use the construction for $k-1$ to generate a $2^{k-3}$ pile, then use the construction for $2^{k-2}$ to generate a $2^{k-2}$ pile and do this until a $2^{k-k}$ pile, which overall uses $k-2$ boxes and $1 + 2 + \cdots + 2^{k-3} = 2^{k-2} - 1$ boxes, so now place the marble labelled $2^{k-2}$ in an empty pile. Next, use the procedure of the Claim to convert this into a since pile containing $2^{k-2}$ pebbles, now ignore this box and we've reduced this to the $k-1$ case, so we can indeed isolate the largest marble if $n \le 2^{k-1}$, as desired. Nice solution by L567.

The answer is $n \leq 2^{k-1}$. Obviously if $(n,k)$ works then so does $(n-1,k)$, so it suffices to show that given $k$ boxes, the largest $n$ that works is $2^{k-1}$. By induction it is easy to see that at any point each box contains marbles labelled with some consecutive integers, since we either remove or add to the bottom. It is then easy to see that operations are always reversible—in particular, moving a marble $i$ to a box containing marble $i+1$ necessarily requires the original box containing $i$ to become empty, at which point we can move marble $i$ back. It's also clear that we can ignore some of the largest marbles (or similarly some of the smallest marbles), i.e. we can perform the same sequence of operations on $1,\ldots,m$ for some $m<n$ as we can on $n=m$. We now provide a construction for $n=2^{k-1}$. For $k=1$ this is trivial. For $k \geq 2$ we first perform the procedure for $k-1$, ignoring marbles $2^{k-2}+1$ through $2^{k-1}$. This will clearly make the first box (initially containing all marbles) have marbles $2^{k-2}$ through $2^{k-1}$, and there will be one unoccupied box. We then move $2^{k-2}$ to that empty box, and then reverse all but the last operation to get marbles $1$ through $2^{k-2}$ into a single box. Then ignore the box and repeat the procedure for $k-1$ on $2^{k-2}+1$ through $2^{k-1}$. Now we will prove $n=2^{k-1}$ is maximal. Change the problem slightly as follows: Cathy has an unlimited number of boxes, but at any given time at most $k$ boxes can have marbles in them. This clearly doesn't change anything since there's a clear bijection between legal moves in this modified version and the original, but it will make a later part of the solution clearer. If the game is to end immediately after a box is found containing only marble $n$, then it is clear that this box is the original box, i.e. marble $n$ does not move. Therefore to prove that $n=2^{k-1}+1$ fails, it suffices to show that for $n=2^{k-1}$ Cathy can't move marble $n$ out of the original box, or equivalently that Cathy can't end up with an empty box given that $n$ is alone in its original box and hasn't moved yet. We use induction with $k=1$ being trivial. Suppose that for some $k \geq 2$ we can perform a series of moves leaving $n=2^{k-1}$ alone in its original box (without moving it) such that some other box is also empty. Suppose that at any point a box $B$ other than the original contains marbles $1$ through $m$ with $m>2^{k-2}$. Then at some point we must have moved marble $2^{k-2}$ onto $B$, before which it contained marbles $2^{k-2}+1$ through $m$. If we now run the process in reverse from the point where $B$ contains marbles $1$ through $m$ to right before moving marble $2^{k-2}$ and ignore the marbles $2^{k-2}+1$ through $2^{k-1}$, we find that at any time only at most $k-1$ boxes contain a marble we care about, since the original box also contains a marble that we don't care about, and in the end we have another empty box, namely $B$, which contradicts our inductive hypothesis for $k-1$. Thus (reintroducing all marbles) at every point there must be some nonempty box that doesn't contain any marbles with labels greater than $2^{k-2}$, since boxes contain consecutive marbles—if every nonempty box contained a marble with a label greater than $2^{k-2}$, then the one with minimal label $\ell $would contain everything from $1$ to $\ell$ as well. But this now means that marbles $2^{k-2}+1$ through $2^{k-1}$ only ever occupy at most $k-1$ boxes at a time, and in the end only occupy $k-2$ boxes. This again contradicts the inductive hypothesis for $k-1$. Thus our claim is proven, implying the bound. $\blacksquare$