Problem 1772

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 \sqcup X, E)$, where the edge set $E := \{(x, y) : x + y \in S\}$. In particular, the restriction of $G$ to $A \sqcup 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 \neq 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 \neq j_2$. Therefore, every vertex in $G$ restricted to $A \sqcup 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_1d_1, c_1d_2, c_2d_1, c_2d_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 \sqcup B$. This would force a vertex in $G$ restricted to $A \sqcup B$ to have degree at least 2, a contradiction.

Consequently, $S$ cannot contain two distinct pairs $(s_1, s_2)$ and $(s'_1, s'_2)$ satisfying $s_1 - s_2 = s'_1 - s'_2$. Otherwise, $(0, -s_1 + s'_1; 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$