2025 International Mathematical Olympiad China National Team Selection Test

Let $X=\{0,\dots ,n-1\}$, $A=\{a_1,\dots ,a_m\}$, $B=\{b_1,\dots ,b_m\}$, and $S=X\setminus C$. We need to show that $|S|<\sqrt{n}+\frac{1}{2}$.

Consider the bipartite graph $G:=(X\bigsqcup X,E)$, where the edge set $E:=\{(x,y):x+y\in S\}$. In particular, the restriction of $G$ to $A\bigsqcup B$ consists of several edges with no common vertices, meaning no vertex has degree at least 2. If this were not the case, suppose $a_i\in A$ is connected to both $b_{j_1}$ and $b_{j_2}$, where $j_1\ne j_2$. Since $a_i+b_{j_1},a_i+b_{j_2}\in S$ do not belong to $C$, it follows that $E\cap (A\times B)\subseteq \{(a_i,b_i):1\le i\le m\}$. Hence, $i=j_1$ and $i=j_2$, contradicting $j_1\ne j_2$. Therefore, every vertex in $G$ restricted to $A\bigsqcup B$ has degree at most 1.

If $G$ contains a cycle $C_4$ of length 4, since $G$ is bipartite, $C_4$ must take the form $c_1,c_2$ in the first copy of $X$ and $d_1,d_2$ in the second copy, with edges $c_1{d}_1,c_1{d}_2,c_2{d}_1,c_2{d}_2\in E$. By the definition of $G$, for any $u\in X$, the quadruple $(c_1+u,c_2+u;d_1-u,d_2-u)$ also forms a $C_4$ in $G$. Letting $u$ range over all elements of $X$, since $|A|+|B|=n+1>n$, an averaging or pigeonhole argument shows that there exists a $u$ such that at least three of these four points lie in $A\bigsqcup B$. This would force a vertex in $G$ restricted to $A\bigsqcup B$ to have degree at least 2, a contradiction.

Consequently, $S$ cannot contain two distinct pairs $(s_1,s_2)$ and $(s_1^{\prime },s_2^{\prime })$ satisfying $s_1-s_2=s_1^{\prime }-s_2^{\prime }$. Otherwise, $(0,-s_1+s_1^{\prime };s_1,s_2)$ would form a $C_4$ in $G$, again a contradiction. Thus, $X$ must contain at least $|S{|}^2-|S|+1$ elements, implying $|S|<\sqrt{n}+\frac{1}{2}$. $\square$