There is a school with $n$ students. Suppose that every student has exactly $2023$ friends and every couple of student that are not friends has exactly $2022$ friends in common. Then find all values of $n$
Problem
Source: 2023 Turkey TST D1 P2
Tags: combinatorics, graph theory
BarisKoyuncu
30.03.2023 00:17
$2024,2026,2028, 2696,4044$
If we replace $2023$ with $2k+1$ and $n$ is the number of students, then $n=2k+2r$ where $r|k$ or $n=2k+4$.
Let's prove our hypothesis by induction over $k$ where $k\ge 0$.
The base cases $k=0,1$ can be hand checked. Suppose that our assumption holds for $k=0,1,\cdots, m-1$ where $m\ge 2$. Let's prove it for $k=m$.
If every student is friends with all the other students, then there are $2m+2$ students in total. $K_{2n+2}$ works for this case. Also, $2m+2-2m$ is even and divides $2m$, as desired.
Now, assume that $A$ and $B$ are not friends. Then, they have $2m$ common friends in total, say $X_1,\cdots X_{2m}$. Let the other friend of $A$ be $C$ and the other friend of $B$ be $D$.
Suppose that $C$ and $D$ are friends. $C$ and $B$ have $2m$ common friends in total and $C$ has a friend ($A$) who is not friend with $B$. Thus, all the other $2m-1$ friends of $C$ must be from the set $\{X_1,\cdots ,X_{2m}\}$. Similarly, all the other $2m-1$ friends of $D$ are from the same set. Now, assume that there is a student other than $A,B,C,D,X_1,X_2,\cdots ,X_{2m}$, say $E$. $E$ is not friend with $C$ so they have $2m$ common friends. But $C$ has two friends ($A$ and $D$) who are not friends with $E$, contradiction. Hence, there are $2m+4$ students in total. For this case, a complete graph $K_{2m+4}$ minus a cycle of length $2m+4$ works.
Suppose that $C$ and $D$ are not friends. $C$ and $B$ have $2m$ common friends in total and $B$ has a friend ($D$) who is not friend with $C$. Thus, all the other $2m$ friends of $C$ must be $X_1,\cdots ,X_{2m}$. Similarly, all the other $2m$ friends of $D$ are $X_1,\cdots ,X_{2m}$. Let $G$ be the set of students other than $A,B,C,D,X_1,X_2,\cdots ,X_{2m}$ (We can assume that $G$ is not empty because we've already considered the case where there are $2m+4$ students in total). Let $E\in G$. $E$ and $C$ have $2m$ common friends and $C$ has a friend ($A$) who is not a friend of $E$. Hence, $E$ must be friends with $X_1,\cdots ,X_{2m}$. Therefore, all the students in the set $G$ are friends with all $X_1,\cdots ,X_{2m}$ and they have exactly one friend in the set $G$. Then, we can pair up the friends in the set $G$. In particular, there must be an even number of students in the set $G$. Let $|G|=2r$ where $r\ge 1$. Then, there are $2m+2r+4$ students in total.
Remove the points from the set $G$ and $A,B,C,D$ from the graph. Each of the remaining students - $X_1,\cdots X_{2m}$ - is friends with all of the students we have removed. Hence, this new graph satisfies the problem condition for $k=m-r-2$. By our induction hypothesis, we get $2m-(2m-2r-4)|2m-2r-4\Rightarrow 2r+4|2m-2r-4$ or $2m-(2m-2r-4)=4$. The latter is impossible as $r\ge 1$. Thus, we get $(2m+2r+4)-2m|2m$, as desired. For these cases, we can reverse-engineer our last steps and construct example graphs by induction hypothesis.