На экскурсию поехало 60 школьников. Известно, что среди любых десяти из этих шестидесяти школьников найдётся три одноклассника. Во время ожидания автобуса школьники встали в группы (все одноклассники стоят в одной группе, школьники из разных классов стоят в разных группах). Найдите максимальное такое n, что при любом распределении поехавших на экскурсию школьников по классам существует группа из не менее n одноклассников.
More Questions From This User See All
Answers & Comments
Verified answer
Классов, от которых на экскурсию поехало не меньше, чем по 2 ученика, может быть не более четырёх (пусть их 5 или больше, тогда можно собрать группу, в которой будет ровно 2 ученика от каждой группы, что запрещено условием). Обозначим число таких классов как N.Классов, от которых на экскурсию поехал один человек, может быть не больше, чем 9 - 2N (иначе берем по 1 ученику из этих классов и по 2 ученика из оставшихся и получаем группу из не менее, чем 10 человек, в которой нет трех одноклассников). Пусть таких классов K.
Начнем распределять школьников по (N + K) классам. Сначала добавим в каждый класс по 1 школьнику, осталось распределить 60 - (N + K) школьников по N классам. В наибольший по размеру класс попадёт не меньше. чем (60 - (N + K))/N учеников (вновь докажем от противного, если в любой класс попало меньше, чем это число, то всех попадет меньше, чем 60 - (N + K). Противоречие).
Нужно найти минимальный возможный размер группы самого большого по представительству класса. По написанному выше размер группы не меньше, чем
1 + (60 - (N + K))/N >= 1 + (60 - (N + 9 - 2N))/N = 1 + (51 + N)/N = 2 + 51/N >= 2 + 51/4 = 14.75
Поскольку размер группы - натуральное число, то размер максимальной группы не может быть меньше 15. Равенство достигается, если, например, есть 4 класса, из каждого из которых поехали ровно 15 учеников.
Ответ. 15.