Пусть выбран некоторый максимальный набор секций.

Сделаем два замечания.

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

) Можно считать, что в каждой секции не более двух человек. Пусть нашлась секция в которую входят школьники и Среди них есть двое (например, и ), не образующих секцию (иначе ученик был бы участником сразу четырех секций: и что невозможно). Тогда заменим на В силу максимальности набора секция существует, потому новый набор тоже удовлетворяет условиям задачи.

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