Областная олимпиада по математике, 2002 год, 10 класс

В трех школах учатся по 200 школьников в каждой. У каждого школьника имеется как минимум один друг в каждой школе (если школьник $a$ является другом школьника $b$, то $b$ является другом $a$). Известно, что существует множество $\Sigma $, состоящее из 300 школьников, такое что для любой школы $S$ и любых двух школьников $x$, $y\in \Sigma $ которые не учатся в школе $S$, число друзей в школе $S$ для $x$ и $y$ различны. Докажите, что найдутся три ученика, по одному из каждой школы, которые дружат друг с другом.

Комментарий/решение

Пусть $\Sigma$ состоит из $S_1$, $S_2$, $S_3$ количества учеников первой, второй, и третьей школы соответственно. По условию количество друзей в школе $S$ может принимать значения от $1$ до $200$, следовательно количество учеников из $\Sigma$ не учащиеся в $S$ не больше $200$. Значит $S_1,S_2,S_3 \geq 100$, у нас тут равенства значит $S_1=S_2=S_3=100$.

Пусть боо ученик который дружит со всеми в второй школе учится в первой школе. У него есть друг из третьей школы, у которого есть друг с второй школы. Эта тройца удовлетворяет условию.