2014-06-08
В каждой из трех школ учится по $n$ человек. Любой ученик имеет в сумме $n + 1$ знакомых учеников из двух других школ. Доказать, что можно выбрать по одному ученику из каждой школы так, чтобы все трое выбранных учеников были знакомы друг с другом.
Решение:
Среди всех $3n$ учеников выберем такого ученика (точнее, одного из таких учеников), который имеет наибольшее число $k$ знакомых в одной из двух других школ. Пусть для определенности им оказался ученик А первой школы, который знает $k$ учеников, например, из второй школы. Тогда А знает $n + 1 – k$ учеников из третьей школы, причем $n + 1 – k\geq 1$, так как $k \leq n$. Рассмотрим ученика В третьей школы, знакомого с А. Если В знает хотя бы одного ученика С из $k$ знакомых А во второй школе, то ученики A, В, С образуют искомую тройку. Если же В не знает никого из $k$ знакомых А во второй школе, то в этой школе он знаком не более чем с $n – k$ учениками, а значит, в первой школе он знаком не менее чем с $n + 1 - (n - k) = k + 1$ учениками, что противоречит выбору $k$. Утверждение доказано.