Задача 080 — Задачи на Графы

В классе учится $n$ человек. Некоторые из них образуют кружки по интересам, наборы учащихся ни в каких двух кружках не совпадают. Известно, что каждый школьник ходит хотя бы в два кружка, но также есть два кружка, в которые он не ходит. Докажите, что можно выбрать пару школьников $A$ и $B$ такую, что найдутся кружок, в который ходят оба школьника, кружок, в который ходит только $A$ , кружок, в который ходит только $B$ , и кружок, в который не ходят ни $A$ , ни $B$ .

Подсказка

Решение

Пусть всего школьники образовали $n$ кружков. Обозначим максимальное число кружков, в которые ходит один школьник, через $k$ , а минимальное — через $s$ . Без ограничения общности можно считать, что $k \leq n-s$ . В самом деле, пусть $k>n-s$ . Тогда запишем каждого школьника во все кружки, в которые он не ходит, и исключим его из всех кружков, в которые он ходит. Пара искомых школьников при этом останется той же самой, но $s$ превратится в $n-k, k$ превратится в $n-s$ , и неравенство $n-s \leq n-(n-k)$ , равносильное неравенству $k \geq n-s$ , будет выполнено.

Пусть Петя — школьник, который ходит в $k$ кружков. Посмотрим на два какие-то кружка, в которые он не ходит. Они состоят из разных наборов участников, значит, найдется школьник Вася, который ходит в один из этих кружков, а в другой не ходит.

Теперь посмотрим на все кружки, в которые Петя ходит. Вася не может ходить во все эти кружки, иначе бы он ходил в большее число кружков, чем Петя. Вася должен ходить хотя бы в один из этих кружков, иначе Вася не ходит в большее число кружков, чем количество кружков, в которые ходит Петя, что противоречит предположению $k \leq n-s$ . Значит, Петя и Вася подходят под условие.