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

1 Ответ

Если в некоторый кружок ходит весь класс, то всё доказано. Далее будем считать, что такого кружка нет.

Пусть самый многочисленный кружок — математический. Его участников мы будем называть математиками. Поскольку не весь класс ходит в этот кружок, найдётся ученик Петров, который в него не ходит. Рассмотрим его и одного из математиков. Они вместе ходят в другой кружок, допустим в физический (физики). Петров не может ходить в этот кружок вместе со всеми математиками, иначе математический кружок не будет самым многочисленным. Значит, с кем то из математиков он ходит ещё в один кружок, например литературный (лирики).

Поскольку Петров занимается не более чем в двух кружках, то математики не могут заниматься больше ни в каких других кружках. Значит, каждый математик может ещё быть только либо физиком, либо лириком, а Петров является физиком и лириком одновременно.
То, что было сказано про Петрова, можно сказать и про любого другого ученика, который не является математиком: каждый из таких учеников — физик и лирик одновременно (и больше ни в какие кружки не ходит).

Таким образом, кружков всего три, и каждый ученик ходит ровно в два кружка. Так как в классе 24 ученика, то на три кружка в общей сложности приходится 48 их участников. Поэтому в математический кружок (самый многочисленный) ходит не менее чем 48/3 = 16 учеников.

Ответ: 16 учеников.
от