Question

11 детей занимаются в 5 кружках. Докажите, что найдутся 2 ученика, что все кружки, которые посещает первый, посещает и второй.

Answer 1

Пусть школьники ходят только в 1 кружок. Тогда вариантов всего 5, из 11 человек минимум в каждый кружок - по двое.

Пусть школьники ходят в 2 кружка. И тогда вариантов всего 10. Школьников у нас 11, и в каком-то из вариантов будет 2 школьника.

Пусть школьники ходят в 3 кружка. Вариантов снова 10.

4 кружка - пять вариантов.

5 кружков - вариант то один, и вроде бы все остальные могут ходить в 1 любой кружок. Но тогда этот, ходящий в большее количество кружков сам исполнит роль пары для менее активного школьника.

Answer 2

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

Предположим, что первый ученик посещает кружки A, B, C, D и E (пять различных кружков). Теперь рассмотрим оставшихся 10 учеников. Каждый из них может посещать максимум 5 кружков, так как всего есть 5 кружков. Но у нас 10 учеников, и каждый из них должен посещать одну из кружков, которую не посещает первый ученик.

Попробуем распределить этих учеников по кружкам. Поскольку у каждого из 10 учеников есть 5 возможных кружков для посещения, а всего кружков 5, по принципу Дирихле (или "парадокс ящиков", если в каждый из пяти "ящиков" мы пытаемся положить по два "шара"), как минимум два ученика окажутся в одной и той же кружке, что противоречит нашему предположению.

Таким образом, мы пришли к противоречию, и исходное утверждение верно: найдутся два ученика, которые посещают все кружки, которые посещает первый ученик.