, 2025

Combinatorics Difficulty 8.7 Shortlist Prove it China

Let $n \ge 2$ be an integer. Two players, Alice and Bob, play the following game: Initially all $\binom{n}{2}$ edges of the complete graph $K_n$ are uncolored. They take turns coloring edges red, with Alice starting first. In each move, a player selects one or two uncolored edges to color red, with the constraint that after each move, no three vertices can have all three edges between them colored red. The game ends when no more edges can be colored.
Prove that there exists a real number $\varepsilon > 0$ such that for any integer $n \ge 2$ , no matter how Bob plays, Alice can ensure that at the end of the game, the number of red edges does not exceed $\left(\frac{1}{4} - \varepsilon\right)n^2 + n$ .

Solution

We consider the graph $G$ formed by red edges. Initially, $G$ is an empty graph on $n$ vertices, and the condition requires that $G$ remains triangle-free throughout the game.

Step 1: We show that if at Alice's turn, $G$ has 24 isolated vertices, then Alice can create a 5-cycle among these vertices in four moves.
Let $S$ be the set of these 24 isolated vertices. Alice first selects three vertices $A, B, C \in S$ and colors $AB$ and $AC$ red. After Bob's move, $S$ still contains at least 17 isolated vertices. Alice then selects two isolated vertices $D, E \in S$ and colors $AD$ and $AE$ red. After Bob's move, $S$ has at least 11 isolated vertices remaining. Alice then selects two more isolated vertices $F, G \in S$ and colors $BF$ and $CG$ red.

Consider the four edges $DF$ , $DG$ , $EF$ , and $EG$ , which are currently uncolored. After Bob's move, at least one of them remains uncolored, say $DF$ . Now $S$ still has at least 5 isolated vertices. Alice selects one of them, $H$ , and colors $FH$ and $DH$ red. This creates a 5-cycle $ABFHD$ in $G$ . By following this strategy, after four moves by each player, the number of isolated vertices in $G$ decreases by at most 24.

Step 2: Alice follows the strategy described in Step 1. After $4 \times \lfloor \frac{n}{24} \rfloor$ moves, she can ensure that $G$ contains $\lfloor \frac{n}{24} \rfloor$ disjoint 5-cycles. Alice then colors edges arbitrarily until $G$ becomes a maximal triangle-free graph.

We now estimate the number of edges in $G$ . Let $k = \lfloor \frac{n}{24} \rfloor$ , and denote the disjoint 5-cycles by $C_1, C_2, \dots, C_k$ . Between any two cycles $C_i$ and $C_j$ , there are at most 10 edges. For each vertex $v$ not in any $C_i$ , there are at most 2 edges from $v$ to each $C_i$ . The remaining $n - 5k$ vertices outside all $C_i$ can have at most $\frac{(n-5k)^2}{4}$ edges between them (by Turán's theorem). The cycles $C_1, \dots, C_k$ themselves contribute $5k$ edges. Thus, the total number of edges is bounded by:

$\begin{align*} |E(G)| &= 10 \binom{k}{2} + 2k(n-5k) + \frac{(n-5k)^2}{4} + 5k \\ &= \frac{n^2}{4} - \frac{kn}{2} + \frac{5k^2}{4} \\ &\le \frac{n^2}{4} - \frac{1}{2} \left( \frac{n}{24} - 1 \right) n + \frac{5}{4} \left( \frac{n}{24} \right)^2 \\ &= \left( \frac{1}{4} - \frac{43}{48^2} \right) n^2 + \frac{n}{2}. \end{align*}$

Taking $\varepsilon = \frac{43}{48^2}$ satisfies the requirement. $\square$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.