|
|
 |
Условие
На олимпиаду пришло 2018 участников, некоторые
из них знакомы между собой. Будем говорить, что несколько попарно знакомых участников образуют "кружок", если любой другой участник олимпиады не знаком с кем-то
из них. Докажите, что можно рассадить всех участников
олимпиады по 90 аудиториям так, что ни в какой аудитории не будут сидеть все представители какого-либо "кружка".
Решение
Докажем индукцией по k более общее утверждение: 2k аудиторий хватит для того, чтобы рассадить n ≤ k2 участников. Тогда для получения утверждения задачи достаточно будет подставить k = 45 , поскольку 2018 ≤ 2025 = 452.
База k = 1, 2 . Поскольку 2k ≥ k2 , мы можем посадить каждого участника в отдельную аудиторию.
Пусть утверждение доказано, когда количество участников не больше (k – 1)2 . Докажем утверждение, когда количество участников не больше k2 . Рассмотрим участника v c наибольшим числом d знакомых. Если d ≥ 2k – 2, то посадим v в одну аудиторию, всех его знакомых во вторую, а оставшихся n – 1 – d ≤ k2 – 1 – (2k – 2) = (k – 1)2 по предположению индукции мы можем рассадить в 2(k – 1) аудиторий так, что в этих аудиториях не будет "кружков". В первой аудитории только один человек, поэтому "кружков" там быть не может, во второй аудитории нет "кружков", так как там нет v, но он знаком со всеми из этой аудитории.
Если же d < 2(k – 1) , то заметим, что нам заведомо хватит d + 1 ≤ 2k аудиторий. Выделим d + 1 аудиторий и будем рассаживать участников по очереди так, чтобы никакие два знакомых не сидели в одной аудитории, тогда в одной аудитории не будут образовываться "кружки" (люди, сидящие в одной аудитории, не знакомы друг с другом). У каждого участника не больше чем d знакомых, так как аудиторий d + 1 , то всегда есть аудитория, где нет его друзей, куда мы его и посадим.
