СПБГУ - задания по годам → .01 СПБГУ 2015 и ранее

Оценка.

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

Пример.

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

Речь идёт о числе Покажем, что оно делится на но не делится на Действительно, То же самое можно сказать про В то время как

То есть по модулю число сравнимо с Учитывая, что имеем Значит, входит в это число в степени, то есть оно не квадрат.

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

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

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

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

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

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

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

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

Из доказанных утверждений вытекает, что в выбранную систему входят все -элементные подмножества и некоторое -элементное подмножество (например, ). Но не все -элементные подмножества содержат что противоречит выбору множеств