Team Selection Test for JBMO

Let $f(n)$ be the minimal number of moves necessary for Bob to guarantee winning. We will show that if $n=5$ Bob cannot win and $$f(n)=\{\begin{array}{ll}2& \text{if }n=3,4,n\ge 12\\ 3& \text{if }6\le n\le 11\end{array}$$

Let the vertices be $v_1,v_2,\dots ,v_n$ in clockwise direction. The Bob's choice and Alice's answer at move number $i$ will be denoted by $B(i)$ and $d(i)$ respectively. Below always $B(1)=v_1$ and the obvious cases when $d(i)=0$ will be omitted.

$n=3$. If $d(1)=1$, $B(2)=v_2$ and Bob locates the bead after the second move. Therefore, $f(3)=2$.

$n=4$. If $d(1)=2$ then Bob locates the bead after the first move. If $d(1)=1$, $B(2)=v_2$ and Bob locates the bead after the second move: for $d(2)=1,2$ the bead is located at $v_3$ or $v_4$ respectively. Therefore, $f(4)=2$.

$n=5$. If $d(1)=2$, then w.l.o.g. $B(2)=v_2,v_3$. If $B(2)=v_2$, $d(2)=2$ is possible. If $B(2)=v_3$ then $d(2)=1$ is possible. In either case the location is not possible and the situation repeats. Therefore, Bob cannot win for $n=5$.

$n=6$. If $d(1)=1$ then $B(2)=v_2$ and Bob locates the bead after the second move. If $d(1)=2$, then w.l.o.g. $B(2)=v_1,v_2,v_3,v_4$. If $B(2)=v_1,v_2$ or $v_4$ then $d(2)=2$ is possible and two moves will not be enough for winning. $B(2)=v_3$. If $d(2)=2,3$ then Bob locates the bead. If $d(2)=1$ then $B(3)=v_4$ and wins after the third move. If $d(1)=3$ Bob locates the bead after the first move. Therefore, $f(6)=3$.

$n=7$. If $d(1)=1$ then $B(2)=v_2$ and locates the bead after the second move. If $d(1)=2$, then w.l.o.g. Bob can choose $v_1,v_2,v_3$ or $v_4$. If Bob chooses $v_1,v_2$ or $v_4$ then $d(2)=2$ is possible and two moves will not be enough for winning. $B(2)=v_3$. If $d(2)=2$ then Bob locates the bead at $v_5$. If $d(2)=1$ then $B(3)=v_2$ and Bob wins after the third move. If $d(2)=3$ then $B(3)=v_1$ and Bob locates the bead after the third move. Therefore, $f(7)=3$.

$n=8$. If $d(1)=1$ then $B(2)=v_2$ and Bob locates the bead after the second move. If $d(1)=2$ then w.l.o.g. Bob can choose $v_1,v_2,v_3,v_4$. If $B(2)=v_1,v_2,v_4$ then $d(2)=2$ is possible and two moves will not be enough for winning. $B(2)=v_3$. If $d(2)=4$ Bob locates the bead at $v_7$. If $d(2)=1,3$ Bob chooses $v_1$ and wins after the third move. If $d(1)=4$ Bob locates the bead after the first move. Therefore, $f(8)=3$.

$n=9$. If $d(1)=1,4$ then Bob chooses $B(2)=v_3,v_4$ respectively and locates the bead after the second move. If $d(1)=2$ then $B(2)=v_4$ locates the bead after the second move. If $d(1)=3$ two moves will not be enough for winning. $B(2)=v_4$. If $d(2)=3$, Bob locates the bead after the second move. If $d(2)=1$ then $B(3)=v_2$; If $d(2)=2$ then $B(3)=v_1$ locates the bead. Therefore, $f(9)=3$.

$n=10$. If $d(1)=1,4$ then Bob chooses $B(2)=v_3,v_4$ respectively and locates the bead after the second move. If $d(1)=2,3$ two moves will not be enough for winning. If $d(1)=2$ then $B(2)=v_4$ for all possible values of $d(2)$ except $d(2)=4$ Bob locates the bead, for $B(2)=v_4$ there are two possibilities $v_8$ and $v_{10}$ and Bob finishes by $v_1$. Therefore, $f(10)=3$.

$n=11$. As above, if $d(1)=1,2,4,5$ then Bob locates the bead after the second move. If $d(1)=3$ then two moves will not be enough for winning. $B(2)=v_4$. If $d(2)=1,2,4,5$ then $B(3)=v_1$ locates the bead. If $d(2)=3$, $B(3)=v_2$ locates the bead. Therefore, $f(11)=3$.

$n\ge 12$. If $d(1)<\lfloor \frac{n}{2}\rfloor$ then $B(2)=v_{d+2}$, if $d(1)\ge \lfloor \frac{n}{2}\rfloor$ then $B(2)=v_d$ locates the bead after the second move. Therefore, $f(n)=2$.