Всесиб 2026, отборочный этап, 11 класс, задача 5
( баллов) В классе ученика. Каждая группа, состоящая из трех учеников, встречается, выбирает одного из оставшихся учеников, назовём его , и делает ему подарок. При этом считает каждого члена группы, которая сделала ему подарок, своим другом. Докажите, что есть ученик, у которого есть по крайней мере друзей. Обращаем внимание, что в процессе дарений участвуют все возможные тройки учеников этого класса.
Ответ
Доказательство. Предположим противное, что каждый ученик может назвать своим другом не больше, чем других учеников этого класса. В таком случае его выбрали субъектом дарения не больше, чем тройки учеников класса. Каждая тройка учеников класса дарила подарок одному из одноклассников, поэтому учитывается в одной из таких троек для некоторого ученика, поэтому всего троек учеников класса будет не больше . Однако, это число равно — противоречие.