2024 CGMO

Proof. Using the language of graph theory to describe this problem, we represent each student as a vertex and connect two vertices with an edge if the corresponding students are friends, forming a simple graph $G$ of order $100$. By the given condition, $G$ has exactly $2024$ edges.

Pair the $100$ vertices into $50$ pairs, called a "pairing." The problem requires proving the existence of a pairing where the number of adjacent vertex pairs satisfies certain conditions.

(1) It is well-known that the edge set of a complete graph of order $100$ can be partitioned into $99$ perfect matchings. Thus, there exist $99$ pairing methods such that each pair of vertices appears in exactly one of these pairings. Therefore, the total number of adjacent vertex pairs across these $99$ pairings is $2024$.

By the pigeonhole principle, there exists a pairing where the number of adjacent vertex pairs does not exceed $\lfloor \frac{2024}{99}\rfloor =20$.

(2) Assume the conclusion does not hold. Then, the maximum matching in $G$ has at most $22$ edges. We can add some edges to $G$ such that the maximum matching has exactly $22$ edges. We now prove that the number of edges in $G$ is less than $2024$.

Take a maximum matching, denoted as $A_i{B}_i$ ($1\le i\le 22$), and let $W$ be the set of remaining vertices, where $|W|=56$. By the maximality of the matching, there are no edges within $W$. If a vertex $A_i$ or $B_i$ is adjacent to at least two vertices in $W$, we call it a "good vertex."

Note that if one of $A_i$ or $B_i$ is a good vertex, the other cannot be adjacent to any vertex in $W$; otherwise, we could adjust $A_i{B}_i$ to two other edges, resulting in a larger matching.

Suppose there are $k$ good vertices among $A_i,B_i$ ($1\le i\le 22$), where $k\le 22$. Without loss of generality, assume $A_1,A_2,\dots ,A_k$ are good vertices. For $1\le i<j\le k$, $B_i$ and $B_j$ cannot be adjacent; otherwise, we could adjust $A_i{B}_i$ and $A_j{B}_j$ to three other edges, obtaining a larger matching.

Thus, the number of edges among $\{A_1,B_1,\dots ,A_{22},B_{22}\}$ is at most $\left(\genfrac{}{}{0ex}{}{44}{2}\right)-\left(\genfrac{}{}{0ex}{}{k}{2}\right)$. For $1\le i\le k$, there are at most $56$ edges between $\{A_i,B_i\}$ and $W$. For $k<i\le 22$, there are at most $2$ edges between $\{A_i,B_i\}$ and $W$. Therefore,

$$\begin{array}{rl}|E(G)|& \le \left(\genfrac{}{}{0ex}{}{44}{2}\right)-\left(\genfrac{}{}{0ex}{}{k}{2}\right)+56k+2(22-k)\\ & =990+\frac{1}{2}k(109-k)\le 990+\frac{1}{2}\times 22\times 87=1947<2024,\end{array}$$

which is a contradiction. This proves the conclusion.

(3) From the conclusions of (1) and (2), there exist two pairings: the first contains at most $20$ edges of $G$, and the second contains at least $23$ edges of $G$.

We now adjust the first pairing step-by-step to the second pairing as follows: Select a pair $(A,B)$ from the second pairing that is not in the first pairing. Suppose the first pairing contains $(A,C)$ and $(B,D)$. Replace $(A,C)$ and $(B,D)$ with $(A,B)$ and $(C,D)$.

After each adjustment, the number of pairs shared with the second pairing increases by at least one. Thus, after finitely many steps, the first pairing becomes the second pairing. Since each adjustment changes two pairs, the number of edges of $G$ in the pairing changes by at most $2$. Starting from at most $20$ and ending with at least $23$, if $22$ is not achieved at any intermediate step, there must exist a pairing $M_1$ with exactly $21$ edges of $G$, which after one adjustment becomes $M_2$ with exactly $23$ edges of $G$.

Let $M_2$ be $\{(A_i,B_i)|1\le i\le 50\}$, where $A_i{B}_i$ is an edge if and only if $1\le i\le 23$.

Without loss of generality, assume $M_1$ adjusts $(A_{22},A_{23})$ and $(B_{22},B_{23})$ to $(A_{22},B_{22})$ and $(A_{23},B_{23})$, and neither $A_{22}{A}_{23}$ nor $B_{22}{B}_{23}$ is an edge.

Note that in the following cases, we can adjust $M_2$ to obtain a pairing with exactly $22$ edges of $G$:

Case 1: There exist $1\le i<j\le 23$ such that among $\{A_i,B_i,A_j,B_j\}$, there is a pairing with exactly one edge of $G$. Replace $(A_i,B_i)$ and $(A_j,B_j)$ in $M_1$ with this pairing.

Case 2: There exist $24\le i<j\le 50$ such that among $\{A_i,B_i,A_j,B_j\}$, there is a pairing with exactly one edge of $G$. Replace $(A_i,B_i)$ and $(A_j,B_j)$ in $M_1$ with this pairing, and then replace $(A_{22},B_{22})$ and $(A_{23},B_{23})$ with $(A_{22},A_{23})$ and $(B_{22},B_{23})$. The resulting pairing has exactly $22$ edges of $G$.

Case 3: There exist $1\le i\le 21$ and $24\le j\le 50$ such that among $\{A_i,B_i,A_j,B_j\}$, there is a pairing with $0$ or $2$ edges of $G$. Replace $(A_i,B_i)$ and $(A_j,B_j)$ in $M_1$ with this pairing. If the number of edges increases by one, also replace $(A_{22},B_{22})$ and $(A_{23},B_{23})$ with $(A_{22},A_{23})$ and $(B_{22},B_{23})$. In any case, we obtain a pairing with exactly $22$ edges of $G$.

Now assume none of the above cases occur. Note that the number of edges in $G$ is even, while the number of edges of the form $A_i{B}_i$ is $23$ (odd). Thus, there exist $1\le i<j\le 50$ such that among $(A_i,A_j)$, $(A_i,B_j)$, $(B_i,A_j)$, $(B_i,B_j)$, exactly an odd number are edges in $G$. These four pairs can be split into two pairings: one with exactly $1$ edge of $G$ and the other with $0$ or $2$ edges.

Since Cases 1, 2, and 3 do not occur, we must have $22\le i\le 23$ and $24\le j\le 50$. Without loss of generality, let $i=23$, $j=24$, and suppose $A_{23}{A}_{24}$ and $B_{23}{B}_{24}$ are either both edges or both non-edges (by swapping $A_{24}$ and $B_{24}$ if necessary). If neither is an edge, then in $M_2$, replace $(A_{23},B_{23})$ and $(A_{24},B_{24})$ with $(A_{23},A_{24})$ and $(B_{23},B_{24})$, resulting in a pairing with exactly $22$ edges of $G$.

Now assume $A_{23}{A}_{24}$ and $B_{23}{B}_{24}$ are both edges of $G$.

Since Case 3 does not occur, for any $1\le i\le 21$ and $24\le j\le 50$, exactly two of $A_i{A}_j$, $A_i{B}_j$, $B_i{A}_j$, $B_i{B}_j$ are edges of $G$. Thus, the number of edges between $\{A_1,B_1,\dots ,A_{21},B_{21}\}$ and $\{A_{24},B_{24},\dots ,A_{50},B_{50}\}$ is exactly $2\times 21\times 27=1134$.

It follows that the number of edges among $\{A_1,B_1,\dots ,A_{22},B_{22}\}$ is at most $2024-1134=890<\left(\genfrac{}{}{0ex}{}{44}{2}\right)$. Thus, there exists a non-adjacent pair in $\{A_1,B_1,\dots ,A_{22},B_{22}\}$. Without loss of generality, assume $A_1{A}_2$ is not an edge of $G$. Since Case 1 does not occur, $B_1{B}_2$ is also not an edge.

In $M_2$, replace $(A_1,B_1)$, $(A_2,B_2)$, $(A_{23},B_{23})$, $(A_{24},B_{24})$ with $(A_1,A_2)$, $(B_1,B_2)$, $(A_{23},A_{24})$, $(B_{23},B_{24})$, resulting in a pairing with exactly $22$ edges of $G$. This completes the proof. □