Question

На экскурсию поехало 60 школьников. Известно, что среди любых десяти из этих шестидесяти школьников найдётся три одноклассника. Во время ожидания автобуса школьники встали в группы (все одноклассники стоят в одной группе, школьники из разных классов стоят в разных группах). Найдите максимальное такое n, что при любом распределении поехавших на экскурсию школьников по классам существует группа из не менее n одноклассников.

Answer 1

Классов, от которых на экскурсию поехало не меньше, чем по 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.

Answer 2

Дано, что среди любых десяти школьников найдутся три одноклассника. Рассмотрим случай, когда в каждой группе из десяти школьников есть только два одноклассника.

В таком случае, можно разделить 60 школьников на 6 групп по 10 человек в каждой группе. При этом в каждой группе будут только два одноклассника. Таким образом, максимальное n в этом случае равно 2.

Докажем, что при n > 2 всегда найдутся группы, состоящие из n одноклассников.

Рассмотрим одного школьника и подсчитаем, сколько школьников он может не считая себя считать своими одноклассниками. У каждого школьника может быть не более 9 одноклассников, так как в каждой группе из десяти школьников не может быть больше двух одноклассников этого школьника.

Таким образом, один школьник может считать не более 9 школьников своими одноклассниками. Если мы выберем одного школьника и его 9 одноклассников, то среди этих 10 школьников найдутся 3 одноклассника.

Из этого следует, что в любом распределении школьников по классам найдется группа из не менее 3 одноклассников. Значит, максимальное n равно 3.