Team Selection Test

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^{\prime }$ not exceeding the other one in length. The set of remaining cards is also naturally decomposed into connected components. If the part $I^{\prime }$ 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^{\prime }$ 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$.