Students in a School

There are 3 schools, each of which has $n$ students. Each student knows altogether $n+1$ students from the other two schools. Prove that we can choose 3 students, each from a different school, such that they know each other.

Solution

Assign each student a score based on the higher number of students he/she knows from each school. For example, if a student knows 4 students from one school and 5 students from another school, his score is 5.

Choose student $a$ with the highest score. Since the highest score is not necessarily unique (there may be multiple highest scores), choose any one of them.

Suppose student $a$ belongs to school $A$, and let $k$ be his score. Suppose he knows $k$ students from school $B$ and $n+1-k$ students from school $C$, where $k \geq n+1-k$.

Take any student $c$ from school $C$ who knows $a$. If $c$ knows any of the $k$ students from school $B$, then we are done, since $a,c,$ and this mutual acquaintance from school $B$ form a desired trio. Thus, we may assume that $c$ knows at most $n-k$ students from school $B$, that is, the ones that $a$ doesn't already know.

But that means $c$ knows at least $(n+1) - (n-k) = k+1$ students from school $A$. Since $\max(k+1, n-k) \geq k+1 > k$, that means $c$ has a higher score than $a$, contradicting our choice of $a$.