Turkish Mathematical Olympiad

Answer: 808.

Let us reformulate the problem in terms of graph theory: a $k$-regular graph $G$ on $2021$ vertices does not contain any triangle. What is the largest value of $k$? Below we give an example for $k = 808$:

Now we show that $k \le 808$. First of all, suppose that $G$ is bipartite: $G = (A, B)$ where all edges are between $A$ and $B$. Then since $|A| \cdot k = |B| \cdot k$ we get $|A| = |B|$ which is impossible since there are $2021$ vertices. Hence $G$ is not bipartite and $G$ contains a cycle of odd length. Let $C$ be the shortest odd cycle with $2t+1$ edges. Since $G$ does not contain any triangle $t \ge 2$.

Let us show that any vertex $v$ in $G-C$ has at most two neighbours on $C$. On the contrary, suppose that vertices $a, b, c \in C$ (in clockwise direction) are directly connected to $v$. Let $n_{ab}, n_{bc}, n_{ca}$ be the number of vertices on paths (without endpoints) $(a, b)$, $(b, c)$, $(c, a)$ of $C$, respectively. Since $G$ has no triangles $n_{ab}, n_{bc}, n_{ca} \ge 1$. Since $n_{ab} + n_{bc} + n_{ca} = 2t-2$, one of these three numbers, say $n_{ab}$, is even. The vertex $v$ and $(a, b)$ constitute a cycle of length $n_{ab}+3$. Since $n_{ab}+3$ is odd and $C$ is a shortest odd cycle, we get $n_{ab}+3 \ge 2t+1$ and $n_{ab} \ge 2t-2$. Hence we get a contradiction $n_{bc} + n_{ca} = 0$.

Let us consider all edges between $C$ and $G-C$. Since each vertex of $C$ has $k$ neighbours there are $(k-2)(2t+1)$ edges between $C$ and $G-C$. On the other hand, each vertex of $G-C$ has at most two neighbours in $C$. Therefore,
$$2(2021-2t-1) \geq (k-2)(2t+1) \Rightarrow 4042 \geq k(2t+1).$$
Finally, since $t \geq 2$ we get $k \leq 808$. Done.