Problem 1860

Bob wins for all pairs of $(k, m \ge 2^k - 1)$ if $k = 1, 2, \dots, 10$ and for all pairs $(k, m \ge 2012)$ if $2012 \ge k \ge 11$.

Let us show that Bob wins in all cases listed above. If $k = 1$ then $2^k - 1 = 1$ and the result is trivial. Suppose that Bob wins for $k - 1 \le 9$ when $m \ge 2^{k-1} - 1$. Bob places the first card on a square numbered $2^k - 1$. The square $2^k - 1$ divides the whole board into two parts. Let $L$ be the number on the first card chosen by Alice. After the first move all cards numbered less than $L$ will be placed to the left part and all cards numbered greater than $L$ will be placed to the right part. Note that both parts having sizes not less than $2^{k-1} - 1$ and by assumption Bob has a winning strategy for remaining $k - 1$ moves and we are done.

If $k \ge 11$ and $m \ge 2012$, then Bob just places the card numbered $L$ to the square numbered $L$.

Now we show that Alice wins in all remaining cases. Alice's strategy: Let us line the cards in increasing order. Suppose Alice's $i$-th move is a card numbered $L$. Bob places the card numbered $L$ into some square. After Bob's $i - 1$-th move, the set of all vacant squares of the board $1 \times m$ is naturally decomposed into connected components. The card $L$ divides the connected component $I$ into two parts, say $I_{left}$ and $I_{right}$. Alice chooses the part $I'$ not exceeding the other one in length. The set of remaining cards is also naturally decomposed into connected components. If the part $I'$ is $I_{left}$ then Alice will choose a card from connected component of remaining cards ending at $L - 1$ for the next step, if the part $I'$ is $I_{right}$ then Alice will choose a card from the connected component of remaining cards starting at $L + 1$ for the next step. In her $i + 1$-th move, if she needs to choose a card from component $[N, M]$ she chooses a card numbered $[(N + M)/2]$. It can be readily seen that Alice wins in all remaining cases if she starts with a card numbered $1006$.