СПбГУ 2022, отборочный этап, 10–11 классы, задача 13
( баллов) В лагерь приехали школьников. Известно, что среди любых школьников обязательно найдутся два друга. Скажем, что группа школьников образует цепочку дружб, если детей в группе можно занумеровать числами от до так, что -й и -й — друзья, -й и -й — друзья, , -й и -й — друзья. Докажите, что всех школьников можно разбить не более чем на групп, каждая из которых образует цепочку дружб. (Группа из одного школьника тоже образует цепочку дружб.)
Ответ
Решение. Возьмем какое-то разбиение школьников на цепочки (например, на одноэлементные группы). Пусть и — крайние школьники из разных цепочек. Если они дружат, то их группы можно объединить, связав и друг с другом. Будем проводить такие объединения до тех пор, пока это возможно. Если осталось более цепочек, то выберем в каждой из них по крайнему школьнику. Их не менее , и по условию среди них найдутся два друга. Но тогда их цепочки можно объединить, что неверно. Значит, осталось не более цепочек.