2019 ISL #C7

 There are 60 empty boxes $B_1,\ldots,B_{60}$ in a row on a table and an unlimited supply of pebbles. Given a positive integer $n$, Alice and Bob play the following game. In the first round, Alice takes $n$ pebbles and distributes them into the 60 boxes as she wishes. Each subsequent round consists of two steps: (a) Bob chooses an integer $k$ with $1\leq k\leq 59$ and splits the boxes into the two groups $B_1,\ldots,B_k$ and $B_{k+1},\ldots,B_{60}$. (b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes one pebble from each box in the other group. Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest $n$ such that Alice can prevent Bob from winning.

Solution 1:

The answer is $31+30+\dots+2+1+2+\dots+30 = \boxed{960}$.

Strategy for Alice (sufficiency):

Distribute the pebbles in the order $31,30, \dots 2,1,2, \dots , 30$ from left to right. Suppose Bob chooses an integer $k \ge 31,$ add to $B_1,\ldots,B_k$ if this is the $2n-1$th time Bob has made this choice for an integer $n.$ Otherwise, add to $B_{k+1},\ldots,B_{60}$. We can now assume that each integer has been toggled at most once, and it is easy to verify her strategy works.

Strategy for Bob (necessity):

Suppose for a positive integer $k$ there are $2k$ boxes with at most $k$ each. We claim Bob can win.

First, Bob does a $k, k$ split. Assume WLOG Alice adds to the left.

Now do a $k+1, k-1$ split. If Alice adds to the right, then the net effect after the last two rounds is that the $k+1$th box has one less pebble and the rest of the boxes are unaffected.

Otherwise Alice adds to the left again. Now do a $k+2, k-2$ split. If Alice adds to the right, then the net effect after the last two rounds is that the $k+2$th box has one less pebble and the rest of the boxes are unaffected.

Otherwise Alice adds to the left again. Now do a $k+3, k-3$ split, a $k+4, k-4$ split, and so on. Bob will continue performing moves in this way, and each time we may assume Alice adds to the left (otherwise she worsens her position). By the time he completes the $2k-1$ split, the rightmost box will be empty.

If Bob cannot win, than for any positive integer $k < 60$ there are at least $60-2k+1$ boxes contain more than $k$ (and obviously each box has at least one pebble); so we need at least $60+59+57+ \cdots + 1 = 960$ pebbles.

We are done. $\square$

Solution 2: 

The answer is $\boxed{960}$.

Generalize to $n$ boxes where $n$ is even. The answer is $(n/2 + 1)^2 - 1$, which is 960 when $n = 60$. Let box $B_i$ have $b_i$ coins. 

Claim: If Alice can avoid the game ending, then for all $x,y$ with $1 \leq x,y \leq n$, we must have $b_x + b_y \geq |x-y+2|$. 

Proof: We show the contrapositive. WLOG, $x = 1$ and $y = n$, since we won't need the other boxes. Then we want to show that $b_1 + b_n \leq n$ implies Bob can win. We'll have Bob split the boxes at $k = b_1$ each move. We claim that regardless of Alice's choice, $S = b_1(n - b_1) + T$ decreases by one each move, where $T$ is the total number of coins in all the boxes from $B_1$ to $B_n$. To show this, we just compute how $S$ changes for each of Alice's options, and the arithmetic is easily checked. Since $S \geq b_1b_n + T$, $S$ is always positive while the game is being played. But since $S$ decreases by one each move, it cannot always stay positive, so Bob must eventually win. We have proved the claim.

The claim implies that if Alice can survive, then $i = 1, 2, \ldots, n/2$, $b_i + b_{2n+1-i} \geq 2n+3-2i$. Therefore, \[ \sum_{i=1}^{n} b_i \geq \sum_{i=1}^{n/2} (2n+3-2i) = (n/2 + 1)^2 - 1. \]So Alice needs to place at least $(n/2 + 1)^2 - 1$ coins, as we claimed. 

We now show this many coins are enough. Alice will place $n+1, n, n-1, \ldots, 2$ coins in the first $n$ boxes and $1, 2, 3, \ldots, n$ coins in the last $n$ boxes, which gives the right total. Alice will also mark $m = n+1$ as the pivot, which will change over time, and maintain the invariant that each box $i$ will have at least $|i-m| + 1$ coins. When Alice has to make a move, she will always increase the number of coins in the pivot. Moreover, if Alice added a coin to box 1, she decreases the pivot $m$ by one, and otherwise she increases the pivot $m$ by one. It is easy to check that this will maintain the invariant, which shows that she can keep every box from being emptied. $\square$

Remarks

This was a somewhat unique problem. The first solution was standard, but the second solution was very short and sweet.