Team Selection Test for IMO 2023

Answer: $n=2024,2026,2028,2696,4044$.

Let us reformulate a more general version of the problem in terms of the graph theory: In a regular graph $G$ on $n$ vertices each vertex has a degree $k<n-1$ and if two vertices are not neighbours then they have exactly $k-1$ common neighbours. Find all pairs $(n,k)$ satisfying these conditions.

If $n=2024$ then the complete graph satisfies the conditions. The answer in the remaining cases: all pairs $(n,k)=(2ab,2a(b-1)+1)$ where $a>1$ and $b$ are positive integers and also all pairs $(n,n-3)$ (if $n=4b$ then all pairs $(n,n-3)$ are among pairs given by $(n,k)=(2ab,2a(b-1)+1)$).

Let $w$ be a vertex with neighbours $v_1,\dots ,v_k$. If some vertex is not a neighbour of $w$ then it is directly connected to $k-1$ neighbours of $w$ and hence it has exactly $1$ neighbour among remaining vertices. Therefore, all vertices in the graph $G-\{w,v_1,\dots ,v_k\}$ have degree $1$ and consequently the number of vertices not directly connected to $w$ is even. Let us denote them by $u_1,\dots ,u_{2l}$. Since $1+l+2l=n$ we get that $2l=n-k-1$. Without loss of generality

for $1\le t\le l$ let $u_{2t-1}$ and $u_{2t}$ be neighbours. When $l=1$ we get a pair $(n,n-3)$. Let $l\ge 2$. For any $t\ge 3$ the vertices $u_1$ and $u_t$ are not neighbours and their unique neighbours among vertices $u_i$ are not common. Hence, $u_1$ and $u_t$ have $k-1$ neighbours among vertices $v_i$. The same is true for $u_2$ and $u_t$. Therefore, all these vertices are connected to the same $k-1$ vertices of $w$. Without loss of generality, let $v_1$ be the vertex not connected to $u_i$, $1\le i\le 2l$. Since the degree of $v_1$ is $k$ it is directly connected to each $v_i$. Therefore, for each $2\le i\le k$ the degree of $v_i$ in $G-\{w,v_1,u_1,\dots ,u_{2l}\}$ is $k-1-1-2l=2k-n-1$. Then the graph on the vertices $v_2,\dots ,v_k$ satisfies problem conditions with new parameters $(k-1,2k-n-1)$. Since $(k-1)-(2k-n-1)=n-k$, by repeating the same procedure we get that the graph $G$ contains pieces with $2l+2$ vertices and each piece contains $l+1$ perfectly matching edges and all possible edges between different pieces are drawn. By denoting $l+1$ by $a$ and the number of pieces by $b$ we get the desired answer.

When $k=2023$ from $2a(b-1)+1=2023$ we get that $a|1011=3\cdot 337$. Therefore the possible values for $a$ are $a=3,337,1011$ and we get $n=2ab=2028,2696,4044$. The pair $(n,n-3)$ yields $n=2026$.