Сложный вариант весеннего тура Турнира Городов

Решим более общую задачу: пусть учеников занимаются в кружках (из трёх человек), Предположим противное: каждые два кружка либо не пересекаются, либо пересекаются ровно по двум ученикам. Заметим, что если кружки и пересекаются с кружком M, то они пересекаются и между собой (их пересечения с имеют общий элемент). Значит, кружки разбиваются на группы пересекающихся между собой кружков. Каждой группе кружков соответствует группа учеников — объединение их составов. Эти группы также не пересекаются. Далее можно рассуждать по-разному.

Первый способ. Поскольку кружков больше, чем учеников, в какой-то группе это неравенство также сохраняется. Поставим в соответствие каждой паре кружков этой группы пару учеников, каждый из которых ходит ровно в один из этих кружков. Пар кружков больше, чем пар учеников, поэтому какой-то паре учеников соответствует по крайней мере две пары кружков и Но кружки и не могут иметь двух общих учеников, поскольку пары и не совпадают. Противоречие.

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

Итак, число кружков не превосходит числа учеников в классе.