Задача: В школе 500 учеников и 502 клуба. В каждом клубе состоит хотя бы один ученик, в любых двух разных клубах — разные наборы учеников. Известно, что для любых 498 клубов есть не менее 498 учеников, состоящих хотя бы в одном из этих клубов. Докажите, что есть ученик, состоящий хотя бы в трех клубах.
Решение: Пусть ученики — элементы, а клубы — множества. Пусть утверждение неверно и каждый элемент входит не более, чем в два множества. Рассмотрим любые три элемента. Если существует не более четырех множеств, содержащих эти три элемента, то остальные 498 множеств содержат не более 497 элементов, что противоречит условию. Таким образом, для любых 3 эле-ментов есть не менее 5 множеств, содержащих хотя бы один из этих элементов.
Предположим, что есть множество, содержащее хотя бы три элемента a, b, c. Остаются еще 4 множества, пересекающие {a, b, c}. Следовательно, один из элементов a, b, c входит хотя бы в три множества, и задача решена. Теперь рассмотрим случай, когда все множества содержат не более, чем по два элемента. Предположим, что есть два пересекающихся двухэлементных множества {a, b} и {b, c}. Тогда больше нет множеств, содержащих b, а, значит, есть еще хотя бы три множества, пересекающие {a, c}, и хотя бы один из элементов a, c входит по крайней мере в три множества.
Остается случай, когда двухэлементные множества не пересекаются. Тогда их не более 250, а остальные множества — одноэлементные. Отсюда легко вывести, что найдутся три элемента a, b, c, каждый из которых входит не более, чем в одно множество. Для этой тройки элементов очевидно нет пяти множеств, пересекающихся с {a, b, c}, что противоречит доказанному выше.
