Три одноклассника готовились к олимпиаде им дали список из 60 задач

а) Разо­бьем всех школь­ни­ков на клас­сы. Пусть в каж­дом клас­се не более 14 че­ло­век. Пусть k – число клас­сов, со­сто­я­щих хотя бы из двух школь­ни­ков (такие клас­сы на­зо­вем боль­ши­ми). Тогда из усло­вия ясно, что kle 4 (иначе, взяв по два школь­ни­ка из пяти боль­ших клас­сов, мы по­лу­чим 10 че­ло­век, среди ко­то­рых нет трех од­но­класс­ни­ков).

Пусть k = 4. Тогда общее число школь­ни­ков в боль­ших клас­сах не пре­вос­хо­дит 56. Зна­чит най­дут­ся 4 школь­ни­ка, каж­дый из ко­то­рых не имеет од­но­класс­ни­ков. Возь­мем их и еще по два школь­ни­ка из трех боль­ших клас­сов. У нас по­лу­чи­лось 10 школь­ни­ков, среди ко­то­рых нет трех од­но­класс­ни­ков.

Пусть те­перь k мень­ше че­ты­рех. Тогда (ана­ло­гич­но) най­дут­ся как ми­ни­мум 18 школь­ни­ков, каж­дый из ко­то­рых не имеет од­но­класс­ни­ков. Это, ко­неч­но, про­ти­во­ре­чит усло­вию.

Таким об­ра­зом, хотя бы в одном клас­се не менее 15 школь­ни­ков.

б) Не­обя­за­тель­но. Рас­смот­рим 4 клас­са по 15 школь­ни­ков. Тогда среди любых де­ся­ти най­дут­ся три од­но­класс­ни­ка, но 16 од­но­класс­ни­ков не най­дет­ся.

РАЗБОР РЕГИОНА ПО ИНФОРМАТИКЕ!!!

Ответ: а) Обя­за­тель­но; б) Нет.

Источник: izi-otvet.ru

Три одноклассника готовились к олимпиаде им дали список из 60 задач

Среди любых десяти из шестидесяти школьников найдётся три одноклассника. Обязательно ли среди всех шестидесяти школьников найдётся
а) 15 одноклассников;
б) 16 одноклассников?

Решение

а) Разобьём всех 60 школьников на группы одноклассников. Если среди школьников нет 15 одноклассников, то в каждой группе не более 14 школьников. Пусть k – число групп, состоящих из двух и более школьников. Такие группы назовём большими.
Из условия вытекает, что k ≤ 4 (иначе, взяв по двое из пяти больших групп, мы получим 10 школьников, среди которых не будет трёх одноклассников). Рассмотрим два случая.
1. k ≤ 3. Тогда общее число школьников в больших группах не превышает 14·3 = 42. Следовательно, найдётся 18 школьников, которые не входят в большие группы, а значит, не имеют ни одного одноклассника! Противоречие.
2. k = 4 . Тогда общее число школьников в больших группах не превышает 56. Следовательно, найдутся 4 школьника, каждый из которых не имеет одноклассников. Взяв этих четверых и добавив к ним по два из всех четырёх больших групп, мы получим даже 12 школьников, среди которых не найдётся трёх одноклассников. Противоречие.

б) Не обязательно. Пример: по 15 школьников из четырёх классов.

Ответ

а) Обязательно; б) не обязательно.

Источники и прецеденты использования

олимпиада
Название	Математический праздник
год
Год	1994
класс
1
Класс	6
задача
Номер	7

Проект осуществляется при поддержке и .

Как затащить Всерос и перечневые олимпиады по математике | Борис Трушин

Источник: problems.ru

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

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

Источник: znanija.site