На экскурсионную поездку поехало 60 школьников. Известно, что среди всех десяти из

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

Задать свой вопрос
1 ответ
Классов, от которых на экскурсионную поездку поехало не меньше, чем по 2 воспитанника, может быть не более четырёх (пусть их 5 либо больше, тогда можно собрать группу, в которой будет ровно 2 воспитанника от каждой группы, что воспрещено условием). Обозначим число таких классов как N.

Классов, от которых на экскурсионную поездку поехал один человек, может быть не больше, чем 9 - 2N  (по другому берем по 1 воспитаннику из этих классов и по 2 ученика из оставшихся и получаем группу из не менее, чем 10 человек, в которой нет 3-х одноклассников). Пусть таких классов K.

Начнем распределять школьников по (N + K) классам. Сначала добавим в каждый класс по 1 школьнику, осталось распределить 60 - (N + K) школьников по N классам. В наивеличайший по размеру класс попадёт не меньше. чем (60 - (N + K))/N воспитанников (опять докажем от неприятного, если в хоть какой класс попало меньше, чем это число, то всех попадет меньше, чем 60 - (N + K). Противоречие).

Необходимо отыскать малый возможный размер группы самого великого по представительству класса. По написанному выше размер группы не меньше, чем 
1 + (60 - (N + K))/N gt;= 1 + (60 - (N + 9 - 2N))/N = 1 + (51 + N)/N = 2 + 51/N gt;= 2 + 51/4 = 14.75

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

Ответ. 15.
, оставишь ответ?
Имя:*
E-Mail:


Добро пожаловать!

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

Пройти регистрацию
Авторизоваться
Уже зарегистрированны? А ну-ка живо авторизуйтесь!

Войти на сайт