IMO 2019 Shortlisted Problems

Solution 1 (Alice).

Alice initially distributes pebbles according to $V_{\lceil \frac{N}{2}\rceil }$. Suppose the current configuration of pebbles dominates $V_i$. If Bob makes a $k$-move with $k⩾i$ then Alice picks the left group, which results in a configuration that dominates $V_{i+1}$. Likewise, if Bob makes a $k$-move with $k<i$ then Alice picks the right group, which results in a configuration that dominates $V_{i-1}$. Since none of $V_1,\dots ,V_N$ contains an empty box, Alice can prevent Bob from ever winning.

Solution 1 (Bob).

The key idea in this solution is the following claim.

Claim. If there exist a positive integer $k$ such that there are at least $2k$ boxes that have at most $k$ pebbles each then Bob can force a win.

Proof. We ignore the other boxes. First, Bob makes a $k$-move (splits the $2k$ boxes into two groups of $k$ boxes each). Without loss of generality, Alice picks the left group. Then Bob makes a $(k+1)$-move, $\dots$, a $(2k-1)$-move. By Observation A, we may suppose Alice always picks the left group. After Bob's $(2k-1)$-move, the rightmost box becomes empty and Bob wins.

Now, we claim that if $n<M$ then either there already exists an empty box, or there exist a positive integer $k$ and $2k$ boxes with at most $k$ pebbles each (and thus Bob can force a win). Otherwise, assume each box contains at least 1 pebble, and for each $1⩽k⩽\lfloor \frac{N}{2}\rfloor$, at least $N-(2k-1)=N+1-2k$ boxes contain at least $k+1$ pebbles. Summing, there are at least as many pebbles in total as in $V_{\lceil \frac{N}{2}\rceil }$; that is, at least $M$ pebbles, as desired.

Solution 2 (Alice).

Let $K=\lfloor \frac{N}{2}+1\rfloor$. Alice starts with the boxes in the configuration $V_K$. For each of Bob's $N-1$ possible choices, consider the subset of rounds in which he makes that choice. In that subset of rounds, Alice alternates between picking the left group and picking the right group; the first time Bob makes that choice, Alice picks the group containing the $K^{\text{th}}$ box. Thus, at any time during the game, the number of pebbles in each box depends only on which choices Bob has made an odd number of times. This means that the number of pebbles in a box could decrease by at most the number of choices for which Alice would have started by removing a pebble from the group containing that box. These numbers are, for each box, $$\lfloor \frac{N}{2}\rfloor ,\lfloor \frac{N}{2}-1\rfloor ,\dots ,1,0,1,\dots ,\lceil \frac{N}{2}-1\rceil$$ These are pointwise less than the numbers of pebbles the boxes started with, meaning that no box ever becomes empty with this strategy.

Solution 2 (Bob).

Let $K=\lfloor \frac{N}{2}+1\rfloor$. For Bob's strategy, we consider a configuration $X$ with at most $M-1$ pebbles, and we make use of Observation A. Consider two configurations with $M$ pebbles: $V_K$ and $V_{N+1-K}$ (if $n$ is odd, they are the same configuration; if $n$ is even, one is the reverse of the other). The configuration $X$ has fewer pebbles than $V_K$ in at least one box, and fewer pebbles than $V_{N+1-K}$ in at least one box.

Suppose first that, with respect to one of those configurations (without loss of generality $V_K$), $X$ has fewer pebbles in one of the boxes in the half where they have $1,2,\dots ,\lceil \frac{N}{2}\rceil$ pebbles (the right half in $V_K$ if $N$ is even; if $N$ is odd, we can take it to be the right half, without loss of generality, as the configuration is symmetric). Note that the number cannot be fewer in the box with 1 pebble in $V_K$, because then it would have 0 pebbles. Bob then does a $K$-move. If Alice picks the right group, the total number of pebbles goes down and we restart Bob's strategy with a smaller number of pebbles. If Alice picks the left group, Bob follows with a $(K+1)$-move, a $(K+2)$-move, and so on; by Observation A we may assume Alice always picks the left group. But whichever box in the right half had fewer pebbles in $X$ than in $V_K$ ends up with 0 pebbles at some point in this sequence of moves.

Otherwise, $N$ is even, and for both of those configurations, there are fewer pebbles in $X$ only on the $2,3,\dots ,\frac{N}{2}+1$ side. That is, the numbers of pebbles in $X$ are at least $$\frac{N}{2},\frac{N}{2}-1,\dots ,1,1,\dots ,\frac{N}{2}$$ with equality occurring at least once on each side. Bob does an $\frac{N}{2}$-move. Whichever group Alice chooses, the total number of pebbles is unchanged, and the side from which pebbles are removed now has a box with fewer pebbles than in $(C)$, so the previous case of Bob's strategy can now be applied.

Solution 3 (Bob).

For any configuration $C$, define $L(C)$ to be the greatest integer such that, for all $0⩽i⩽N-1$, the box $B_{i+1}$ contains at least $L(C)-i$ pebbles. Similarly, define $R(C)$ to be greatest integer such that, for all $0⩽i⩽N-1$, the box $B_{N-i}$ contains at least $R(C)-i$ pebbles. (Thus, $C$ dominates the 'left half' of $V_{L(C)}$ and the 'right half' of $V_{N+1-R(C)}$.) Then $C$ dominates a 'V$-$shaped' configuration if and only if $L(C)+R(C)⩾N+1$. Note that if $C$ dominates a V-shaped configuration, it has at least $M$ pebbles.

Now suppose that there are fewer than $M$ pebbles, so we have $L(C)+R(C)⩽N$. Then Bob makes an $L(C)$-move (or more generally any move with at least $L(C)$ boxes on the left and $R(C)$ boxes on the right). Let $C^{\prime }$ be the new configuration, and suppose that no box becomes empty (otherwise Bob has won). If Alice picks the left group, we have $L(C^{\prime })=L(C)+1$ and $R(C^{\prime })=R(C)-1$. Otherwise, we have $L(C^{\prime })=L(C)-1$ and $R(C^{\prime })=R(C)+1$. In either case, we have $L(C^{\prime })+R(C^{\prime })⩽N$.

Bob then repeats this strategy, until one of the boxes becomes empty. Since the condition in Observation A holds, we may assume that Alice picks a group on the same side each time. Then one of $L$ and $R$ is strictly decreasing; without loss of generality assume that $L$ strictly decreases. At some point we reach $L=1$. If $B_2$ is still nonempty, then $B_1$ must contain a single pebble. Bob makes a 1-move, and by Observation A, Alice must (eventually) pick the right group, making this box empty.