Олимпиадная задача: кружки и пары учеников — доказательство через принцип Дирихле
Задача
Каждый из учеников класса занимается не более чем в двух кружках, причём для любой пары учеников существует кружок, в котором они занимаются вместе. Докажите, что найдётся кружок, в котором занимается не менее ⅔ всего класса.
Решение
Если в некоторый кружок ходит весь класс, то всё в порядке. Далее мы считаем, что такого кружка нет.
Пусть самый многочисленный кружок – математический; его участников мы будем называть математиками. Есть ученик Вася, который в него не ходит. Рассмотрим его и одного из математиков. Они вместе ходят в другой кружок, допустим, в фото. Вася не может ходить в этот кружок вместе со всеми математиками, иначе математический кружок не будет самым многочисленным. Значит, с кем-то из математиков он ходит ещё в один кружок, например, в танцевальный.
Итак, каждый математик ещё является либо фотографом, либо танцором (и никем другим).
То, что было выше сказано про Васю, можно сказать и про любого ученика, который не является математиком: каждый из таких учеников – фотограф и танцор одновременно (и больше ни в какие кружки не ходит).
Таким образом, кружков всего три, и каждый ученик ходит ровно в два кружка. Пусть в классе n учеников, тогда на три кружка в общей сложности приходится 2n их участников. Поэтому в математический кружок (самый многочисленный) ходит не менее, чем 2n/3 учеников.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь