In a school with some students, for any three student, there exists at least one student who are friends with all these three students.(Friendships are mutual) For any friends $A$ and $B$, any two of their common friends are also friends with each other. It's not possible to partition these students into two groups, such that every student in each group are friends with all the students in the other gruop. Prove that any two people who aren't friends with each other, has the same number of common friends.(Each person is a friend of him/herself.)
Problem
Source: Turkey 2021 IMO TST Problem 2
Tags: Turkey, combinatorics
BarisKoyuncu
24.05.2021 11:21
First of all, show that if $A-B$ and $A-C$ are not friends, then the number of common friends of $A$ and $B$ is the same as the number of common friends of $A$ and $C$. After that, create a graph by connecting non-friend pairs. See that this graph should be connected (rule $3$). We can complete the proof by these $2$ results.
CLAIM: Assume that $A-B$ and $A-C$ are not friends. Then, the number of common friends of $A$ and $B$ is the same as the number of common friends of $A$ and $C$.
PROOF:
Let $X:\{b_1,b_2,\cdots ,b_m\}$ be the set of students who are friends with $A$ and $B$, but not friends with $C$.
Let $Y:\{c_1,c_2,\cdots ,c_n\}$ be the set of students who are friends with $A$ and $C$, but not friends with $B$.
Let $Z:\{d_1,d_2,\cdots ,d_k\}$ be the set of students who are friends with $A,B$ and $C$.
If $m=n=0$, then we are done. Assume that $m\ge 1$.
Assume that a student from the set $X$ and a student from the set $Z$ are friends. Let $b_i$ and $d_j$ be friends. Also, they are both friends with $A$ and $B$. Hence, $A$ and $B$ should be friends. But they are not, contradiction. Hence, none of the students in the set $X$ has a friend in the set $Z$. Similarly, none of the students in the set $Y$ has a friend in the set $Z$.
Let $i\in\{1,2,\cdots ,m\}$. We know that $A, C$, and $b_i$ have a common friend. See that this student is different from $A, C$ and $b_i$. Also, he cannot be in $Z$ since $b_i$ doesn't have a friend in the set $Z$. Thus, this student should be in the set $Y$. Hence, each student from the set $X$ has a friend in $Y$ and each student from the set $Y$ has a friend in $X$.
In particular, $n\ge 1$.
Assume that $m\neq n$. WLOG $m<n$. Then, there exists a student in $X$ who has at least two friends in $Y$. WLOG $b_1$ is friend with $c_1$ and $c_2$.
We know that $A$ is friend with $b_1$ and $c_1, c_2$. Then, by rule 2, $c_1$ and $c_2$ should be friends. Also, both $c_1$ and $c_2$ are friends with $A$ and $C$. Hence, again by rule 2, $A$ and $C$ should be friends. But they are not, contradiction. Thus, $m=n$.
In conclusion, the number of common friends of $A$ and $B$ is the same as the number of common friends of $A$ and $C$.
Construct the reverse graph (the graph created by connecting non-friend pairs). By rule 3, this graph should be connected. Let's label each edge with the number of common friends of its endpoints. By our claim, all edges coming out of the same vertex are labeled with the same number. Since this graph is connected, we can find that all edges are labeled with the same number. Hence, any two students -who are not friends with each other- have the same number of common friends, done.