, 2020

For convenience, we call choosing $B_1, \cdots, B_k$ choosing the left, and otherwise choosing the right.

a.
Partial solution: Let $V = (v_1, \cdots, v_N)$ denote the situation where box $i$ contains $v_i$ pebbles. We say $V > W$ if and only if $v_i \ge w_i$ holds for all $1 \le i \le N$. Moreover, for any $1 \le i \le N$, let $V_i$ denote the situation where box $j$ contains $1 + |j - i|$ pebbles; note that $V_i$ has no empty box.

Now, suppose $n = M$, and Alice initially distributes the pebbles into the situation $V_{[N/2]}$ (in this case the total number of pebbles is $M$). In each subsequent round, suppose the starting state is $W$ with $W > V_i$.

– If Bob chooses $k \ge i$, then Alice chooses the left, and the state at the end of the round will be $> V_{i+1}$.

– If Bob chooses $k < i$, then Alice chooses the right, and the state at the end of the round will be $> V_{i-1}$.

Therefore, at the end of any round, Alice can guarantee that her state is greater than some $V_i$, so there can never be an empty box. Part (a) is thus proved.

b.
Partial solution: We first prove two lemmas.

Lemma 1: Consider two consecutive rounds. Suppose that in the first round Bob chooses $k$, and Alice chooses the left. If in the next round Bob chooses $l > k$, then we only need to consider the possibility that Alice chooses the left.

Proof. Suppose the state at the start is $W = (w_1, \cdots, w_N)$. If Alice chooses the right the second time, then the new state she ends up with is $W' = (w_1, w_2, \cdots, w_k, w_{k+1} - 1, \cdots, w_l - 1, w_l, \cdots, w_N)$, so $W' < W$. In doing so Alice has only made her situation strictly worse than before, so we only need to consider the case where she chooses the left both times. □

Lemma 2: If there exist at least $2k$ boxes, each containing at most $k$ pebbles, then Bob has a winning strategy.

Proof. Ignore the boxes other than these $2k$ boxes. First, Bob splits the $2k$ boxes evenly in half, and without loss of generality assume Alice chooses the left. Bob then successively chooses $k+1, k+2, \cdots, 2k-1$; by Lemma 1, we may always assume Alice chooses the left. But then, after all of the above $k$ moves have been completed, the rightmost box will be empty, and Bob wins. □

Now, if initially there is no empty box, and for any positive integer $k$ the situation of Lemma 2 does not occur, this means that every box has at least 1 pebble, and for all $1 \le k \le [N/2]$, at least $N - (2k-1) = N + 1 - 2k$ boxes have at least $k+1$ pebbles. Summing all of these up, we get that the total number of pebbles is at least $M$. Hence if the initial number of pebbles is $< M$, Bob is guaranteed to win.