МОШ 2026, 11 класс, задача 4

Ответ: для любого натурального числа .

Решение. Сначала докажем, что должно быть полным квадратом. Действительно, обозначим количество мальчиков за , а количество девочек за . Просуммируем по всем людям количество человек того же пола, которым они помогли. Эта сумма будет равна

откуда

Итак, мы знаем, что . Более того, из рассуждений выше следует, что , откуда . Теперь осталось построить пример для таких параметров. Это можно сделать несколькими способами.

Первый способ. Докажем по индукции, что для всякого существует конструкция с мальчиками и девочками.

База: для пример строится непосредственно (например, можно взять конструкцию из Случая 2 следующего решения).

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

Пусть все дети из конструкции помогают в точности всем добавленным, кроме Тани (то есть они помогли девочкам и мальчикам);

Также пусть Таня помогает всем детям из конструкции , а также добавленным мальчикам, и ни одной добавленной девочке (таким образом, она помогла по мальчикам и девочкам).

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

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

Конструкция 1. Рассмотрим полный ориентированный граф на вершине, в котором вершины пронумерованы числами , причем из вершины выходят ребра с концами (все числа рассматриваем по модулю ). Это задает -регулярный турнир на вершине. Назовем такую конструкцию .

Конструкция 2. Рассмотрим полный ориентированный граф на вершинах, в котором вершины пронумерованы числами , причем из вершины выходят ребра с концами (все числа рассматриваем по модулю ). Кроме того, из вершин с номерами выходит ребро в вершину . Получаем граф, в котором исходящие степени вершин с номерами равны , а исходящие степени вершин с номерами равны . Такую конструкцию назовем .

Конструкция 3. Зафиксируем натуральные числа и и рассмотрим целые неотрицательные числа и с условиями , , . Пусть, кроме того, , . Заметим, что из условия немедленно следуют соотношения

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

Итак, теперь мы готовы строить примеры. Для этого разберем случая:

Случай 1. Пусть и оба нечетные. Заметим, что выполняются соотношения , , а также равенство (проверяется непосредственно)

Тогда построим на множестве мальчиков граф , на множестве девочек граф , а между ними - граф . Теперь для каждого ребра будем считать, что помог . Тогда каждый мальчик помог мальчикам и девочкам, а каждая девочка помогла мальчику и девочке.

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

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

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