|
|
 |
Условие
В классе 32 ученика. Было организовано 33 кружка, причём каждый кружок состоит из трёх человек и никакие два кружка не совпадают по составу. Доказать, что найдутся такие два кружка, которые пересекаются ровно по одному ученику.
Решение 1
Решим более общую задачу: пусть k учеников занимаются в n кружках (из трёх человек), k ≤ n.
Предположим противное: каждые два кружка либо не пересекаются, либо пересекаются ровно по двум ученикам. Заметим, что если кружки K и L пересекаются с кружком M, то они пересекаются и между собой (их пересечения с M имеют общий элемент). Значит, кружки разбиваются на группы пересекающихся между собой кружков. Каждой группе кружков соответствует группа учеников – объединение их составов. Эти группы также не пересекаются. Далее можно рассуждать по-разному.
Первый способ. Поскольку кружков больше, чем учеников, в какой-то группе это неравенство также сохраняется. Поставим в соответствие каждой паре кружков этой группы пару учеников, каждый из которых ходит ровно в один из этих кружков. Пар кружков больше, чем пар учеников, поэтому какой-то паре учеников {a, b} соответствует по крайней мере две пары кружков {a, c, d}, {b, c, d} и {a, u, v}, {b, u, v}. Но кружки {a, c, d} и
{b, u, v} не могут иметь двух общих учеников, поскольку пары {c, d} и {u, v} не совпадают. Противоречие.
Второй способ. Если в группе, содержащей некоторый кружок {a, b, c}, есть кружки, содержащие хотя бы две из трех пар {a, b}, {a, c}, {b, c}, скажем кружок {a, b, d} и кружок {a, c, e}, то d = e (два последних кружка должны иметь двух общих членов). Единственный возможный кружок, пересекающийся с каждым из этих трех по двум элементам, – это {b, c, d}. Таким образом, в такой группе не более четырёх кружков, куда ходят не менее четырёх учеников.
Если же все кружки группы содержат только одну из трёх указанных пар (например, {a, b}), то количество кружков в ней на 2 меньше количества всех учеников, их посещающих.
Итак, число кружков не превосходит числа учеников в классе.
Решение 2
Пусть есть k учеников и набор (не совпадающих по составу) кружков, каждый из которых посещает нечетное число учеников. Поставим в соответствие каждому кружку A k-мерный вектор a над полем Z2 из двух элементов: ai = 1 тогда и только тогда, когда i-й ученик посещает А. "Скалярный квадрат"
(a, a) = 1 для каждого кружка. Если же два кружка A и В пересекаются по чётному числу учеников, то соответствующие векторы a и b "ортогональны":
(a, b) = 0. Рассмотрим набор из n кружков, каждые два из которых удовлетворяют этому условию. Тогда соответствующие векторы линейно независимы. Действительно, умножив равенство α1a1 + ... + αnan на ai, получим
αi = 0. Значит, n ≤ k, то есть число кружков с попарным "чётным" пересечением не превосходит числа учеников.
Замечания
7-8 кл. – 8 баллов, 9-10 кл. – 6 баллов
