Дано:
1. Ученик может заниматься не более чем в двух кружках.
2. Для любой пары учеников существует кружок, в котором они занимаются вместе.
Найти:
Доказать, что существует кружок, в котором занимается не менее двух третей всего класса.
Решение:
1. Пусть всего в классе N учеников. Обозначим кружки как K1, K2, ..., Km. Пусть каждый кружок содержит хотя бы один ученик.
2. Так как любой ученик может быть занят не более чем в двух кружках, и для любой пары учеников существует кружок, в котором они занимались вместе, можно сделать следующие выводы.
3. Рассмотрим граф, где вершины - это ученики, а ребра соединяют пару учеников, если они занимались в одном кружке. Так как любой ученик занят не более чем в двух кружках, то граф представляет собой объединение нескольких графов, каждый из которых является связным подграфом.
4. Если каждый кружок имеет не менее двух третей всех учеников, то мы завершаем доказательство. В противном случае, предположим, что ни один из кружков не содержит двух третей всех учеников.
5. Пусть все кружки содержат не более, чем (2/3)N - 1 учеников. Тогда, учитывая, что в каждом кружке содержится меньше двух третей учеников, число учеников, которые участвуют в каждом кружке, по меньшей мере (N - (2/3)N) = (1/3)N.
6. Рассмотрим, что каждый ученик встречается не более чем в двух кружках. Если мы суммируем количество учеников по кружкам, где каждый кружок содержит менее двух третей от общего числа учеников, то общее число "участий" всех учеников во всех кружках будет меньше 2 * N * (2/3)N = (4/3)N^2.
7. Однако, по условию, каждый ученик может посещать не более двух кружков, что создает неравенство: если в каждом кружке находится менее двух третей учеников, то в сумме число таких посещений будет значительно больше (N * (2/3)N), что приводит к противоречию.
8. Следовательно, наше предположение неверно, и должно существовать как минимум один кружок, в котором количество учеников составляет не менее двух третей от общего числа учеников.
Ответ:
Существует кружок, в котором занимается не менее двух третей всего класса.