СПбГУ 2026, 10-11 классы, задача 4
( баллов) В школе обучается одиннадцатиклассников. Каждый из них отправил в VK поздравление с Новым Годом одиннадцатикласснику. Для какого наибольшего обязательно можно выбрать группу из одиннадцатиклассников, каждый из которых отправил поздравления остальным участникам группы?
Ответ: .
Решение. Покажем как нужно было посылать поздравления, чтобы нельзя было выбрать требуемую группу из четырех учеников. Посадим учеников за круглым столом. Пусть каждый из них поздравил следующих , сидящих за ним по часовой стрелке. Предположим, что можно выбрать требуемую группу из четырех человек. Возьмем двоих участников этой группы. Для того чтобы они поздравили друг друга нужно чтобы между ними сидело не менее человек. Но тогда кроме учеников из группы должно быть не менее чем школьников, а это не так.
Докажем, что группу из трех учеников можно выбрать всегда. Общее количество поздравлений , поэтому кто-то получил не менее поздравления. Назовем его Петей. Он не посылал поздравлений школьникам, поэтому есть не менее учеников, которые с Петей поздравили друг друга. Покажем, что среди этих учеников (назовем их классом) есть двое поздравивших друг друга. Предположим противное, тогда для любой пары учеников в классе между ними послано не более одного поздравления, т. е. всего не более поздравлений. С другой стороны каждый не поздравлял учеников, поэтому он должен был послать не менее поздравлений одноклассникам. Следовательно, между учениками классе было послано не менее поздравлений. Но . Противоречие.