10-я задача от тестовой контрольной Яндекса

[Редактор]

Задача от Высшей школы экономики.

На зачёт к преподавателю английского языка пришли 30 студентов: 13 с факультета экономики, 9 с факультета математики и 8 с факультета компьютерных наук. Их одинаковые внешне и на ощупь зачётные книжки лежат на столе. Какое наибольшее количество зачётных книжек должен взять преподаватель, чтобы быть уверенным, что среди оставшихся на столе присутствуют зачётки хотя бы 7 студентов одного факультета и 4 студентов другого?

Решение : сначала поймём, как обеспечить хотя бы 7 студентов одного факультета.

Наименее "выгодная" комбинация распределения зачёток по факультетам при этом возникает, когда зачётки будут оставлены в количестве 7+6+6 = 19 штук.

Если преподавателем будет взято не более 11 зачёток, то это гарантирует, что среди оставшихся зачёток будет минимум 7 зачёток с одного факультета. Если преподаватель оставит меньше 19 зачёток, то это не гарантирует, что среди них будет хотя бы 7 зачёток с одного факультета (ввиду наличия возможной комбинации 18 = 6+6+6).

Теперь сообразим, как обеспечить среди оставленных на столе минимум 4 зачётки со второго факультета.
Из ранее доказанного - преподаватель берёт не более 11 зачёток, остаётся не менее 19 зачёток.

Наименее выгодная ситуация для возникновения минимум 4-х зачёток другого факультета возникнет, если преподаватель оставит на столе 13 зачёток с факультета экономики и по 3 - с других факультетов. (Во всех других случаях на столе и так останется минимум 4 зачётки другого факультета.) Чтобы подстраховаться от наименее выгодной ситуации, преподаватель должен оставить на столе ещё одну, двадцатую, зачётку : 13+4+3 = 20.

Итого преподаватель должен взять максимум 10 зачёток, чтобы оставить на столе минимум 7 зачёток с одного факультета и минимум 4 зачётки другого факультета.