Team Selection Test for JBMO 2024

Answer: 205.

Let us show that Zehra can guarantee to determine the colours of all balls for $N=205$. Zehra writes the pairs $(1,2),(1,3),\dots ,(1,206)$ on the board. Let us assign a number $i$ to the ball contained in the box number $i$. Suppose that out of balls numbered $2,3,\dots ,206$ the number of balls same-coloured with $i$ is $a$ and the number of differently coloured balls is $b=205-a$. Then the colours of all balls can be easily determined: One of these numbers $a$ and $b$ is greater or equal to 103. If $a\ge 103$ then ball 1 is white. $a+1$ is either 106 or 107. In the first case ball 207 is white, in the second case ball 207 is red. If $b\ge 103$ then ball 1 is red. $b$ is either 106 or 107. In the first case ball 207 is white, in the second case ball 207 is red.

Now we show that if $N\le 204$ then Zehra cannot guarantee to determine colours of all balls. Suppose that $N$ pairs $(i,j)$ are already chosen by Zehra. Let us define a graph $G$ consisting of 207 vertices representing balls where vertices $i$ and $j$ are connected by an edge if and only if there is a pair $(i,j)$ on the board. Since the total number of edges is $N\le 204$ the graph $G$ has at least 3 connected components. Asli divides these connected components into 3 non-empty groups $C_1,C_2$ and $C_3$ with number of vertices $|C_1|,|C_2|$ and $|C_3|$. Assuming $|C_1|\ge |C_2|\ge |C_3|$ we get that $|C_2|+|C_3|\le 138$. Obviously at least one of groups $C_2,C_3$ and $C_2\cup C_3$ contains even number of vertices. Asli can divide vertices of this group into two parts $A_1$ and $A_2$, where $|A_1|=|A_2|<100$. Since Zehra is going to guarantee to determine ball colours we can suppose that Asli knows all pairs on the board before her ball distribution. Thus, Asli can make all balls in $A_1$ red coloured and all balls in $A_2$ white coloured or alternatively all balls in $A_1$ white coloured and all balls in $A_2$ red coloured and the remaining balls will have arbitrary colours just to provide 100 red and 107 white balls in total. In both cases the answers of Asli will be the same. Therefore, Zehra cannot determine the ball colours of this group containing even number of boxes. Done.