Three schools have $200$ students each. Every student has at least one friend in each school (if the student $a$ is a friend of the student $b$ then $b$ is a friend of $a$). It is known that there exists a set $E$ of $300$ students (among the $600$) such that for any school $S$ and any two students $x,y\in E$ but not in $S$, the number of friends in $S$ of $x$ and $y$ are different. Show that one can find a student in each school such that they are friends with each other.
Problem
Source: Romanian TST 2001
Tags: combinatorics proposed, combinatorics, Hi
Ahwingsecretagent
19.01.2011 21:31
First I'll show that from each school there are exactly 100 students in the set $E$: Suppose not, hence there must be a school with $<100$ students from $E$; call this school $S_1$. In the other two schools therefore there are more than $200$ students from $E$, call this set $E'$. Everyone in $E'$ has at least a friend in $S_1$ and the number of friends from $S_1$ of each member of $E'$ is different; however this cannot possibly happen since there are only $200$ students in $S_1$. Hence in each school there are $100$ students in $E$. With the same logic as above, we see that for each school $S$, there is exactly one member of $E$ who is friends with everyone in $S$. Taking this student for each school, we have $3$ students $a,b,c$ who know everyone in schools $S_1,S_2,S_3$ respectively. They cannot all be from the same school, as $a$ is not in $S_1$, $b$ isn't in $S_2$ and $c$ isn't in $S_3$. If they are from different schools then we are done. Otherwise suppose wlog $a,b$ are in $S_3$, $c$ is in $S_1$. Then since everyone has at least a friend in each school, $c$ has a friend $d$ in $S_2$. Now $b,c,d$ are from $3$ schools and know each other, so we are done.