E5 Инварианты по модулю

Почему метод важен

По таблице ВсОШ 9 метод E5 (Чётность как инвариант) — 10 задач как основной. Метод появляется на всех этапах с 2010 года и часто комбинируется с D1 (делимость), B1 (логика), E10 (двойной подсчёт).

Главное, что даёт E5:

• умение искать инвариант в задаче с операциями («можно ли получить из …?»);
• работу с шахматной раскраской при доказательстве невозможности замощения или обхода;
• использование чётности суммы, количества или произведения объектов;
• доказательство, что «такая конфигурация невозможна», через противоречие по модулю 2.

Реальные ориентиры из таблицы

Предупреждение: некоторые формулировки (2016 Заключительный №1, 2023 Заключительный №2) OCR-фрагментарные; в таких местах дан только первый ход, а не полное решение.

• Инвариант чётности: если при каждом шаге некоторая сумма (число, количество) меняется на чётное число, то её чётность — инвариант. Когда использовать: задачи на перекладывание, замену, перекраску, где каждый шаг добавляет чётное количество.

• Инвариант по модулю $m$: если при каждом шаге выражение $f(\text{состояние})$ меняется на кратное $m$, то $f \pmod{m}$ — инвариант. Когда использовать: процессы с фиксированными шагами.

• Полуинвариант (монотонный инвариант): величина, которая при каждом шаге только возрастает (или только убывает$). *$Когда использовать*: доказать, что процесс конечен, или что определённое состояние недостижимо (конечное значение меньше начального).

• Линейный инвариант: для задач с наборами чисел $(a_1, \ldots, a_n)$ инвариантом часто служит $\sum a_i \pmod{m}$ или $\sum i \cdot a_i \pmod{m}$.

• Найти сохраняющуюся сумму или произведение: при каждом допустимом ходе вычислить, как меняется $\sum a_i$, $\prod a_i$, $\sum a_i^2$ — и выбрать ту характеристику, которая не меняется.
• Рассмотреть чётность: самый простой инвариант — чётность числа объектов определённого типа.
• Рассмотреть остаток по нескольким модулям: иногда ни по 2, ни по 3 не работает, но по 6 — работает.
• Раскраска чёрно-белая (или в несколько цветов): покрасить объекты в цвета и показать, что каждый ход меняет число объектов каждого цвета предсказуемым образом.
• Рассмотреть взвешенную сумму: $\sum c_i \cdot a_i$, где веса $c_i$ подобраны так, чтобы инвариант стал нетривиальным.
• Поиск инварианта методом проб: подставить конкретный малый пример, вычислить несколько шагов и угадать инвариант по наблюдению.

Поверхностные признаки (что буквально написано):
- «Докажите, что нельзя получить состояние $B$ из состояния $A$».
- «Возможно ли за несколько ходов перейти из ... в ...».
- «Докажите, что сумма / произведение / количество чётных элементов всегда ...».

Структурные признаки (форма выражения, объекты):
- Есть итеративный процесс: набор состояний и допустимые ходы.
- Каждый ход имеет чёткое описание (например, «заменить $a$ и $b$ на $a+1$ и $b-1$» или «перекрасить соседние клетки»).
- Начальное и желаемое конечное состояния указаны явно.

Цель задачи (что от тебя хотят):
- Доказать невозможность (инвариант в начале и конце различен).
- Найти все достижимые состояния.
- Доказать, что некоторое свойство сохраняется навсегда.

7 семейств E5

Семейство 1. Чётность суммы

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

Главный ход. Посчитать сумму всех чисел и проверить, как она меняется по модулю 2.

Задача 1.1

На доске написаны числа \(1, 2, 3, \ldots, 10\). За один ход разрешается стереть два числа и записать их сумму. Какое число останется в конце?

Скелет решения: сумма \(1+2+\ldots+10=55\). При операции сумма не меняется. Поэтому в конце останется \(55\).

Ответ:\[ 55. \]

Задача 1.2

На доске написаны числа \(1, 2, 3, \ldots, 100\). За один ход разрешается стереть два числа \(a\) и \(b\) и записать \(|a-b|\). Может ли в итоге остаться число \(1\)?

Скелет решения: сумма всех чисел \(1+\ldots+100=5050\) — чётная. При операции \(a+b\to|a-b|\) сумма меняется на \(|a-b|-(a+b)\), что чётно (так как \(|a-b|\equiv a+b\pmod 2\)). Значит, чётность суммы сохраняется: в конце сумма чётна, а \(1\) — нечётно. Невозможно.

Ответ: нет, в конце не может остаться \(1\).

Задача 1.3

В строке записаны \(n\) чисел. За операцию можно выбрать два соседних и заменить на их сумму и разность. Какие конфигурации можно получить из \((1, 0, 0, \ldots, 0)\)?

Скелет решения: сумма квадратов сохраняется: \((a^2+b^2)\to((a+b)^2+(a-b)^2)=2(a^2+b^2)\) — удваивается. Значит, сумма квадратов удваивается за операцию. Инвариант — отношение суммы квадратов к степени 2.

Ответ: можно получить только те конфигурации, в которых сумма квадратов равна \(2^k\) для некоторого \(k\ge 0\).

Задача 1.4 — реальная (2010 Региональный №5)

Незнайка выписал по кругу 11 натуральных чисел. Для каждых двух соседних чисел он посчитал их разность. В результате среди найденных разностей оказалось четыре единицы, четыре двойки и три тройки. Докажите, что это невозможно.

Скелет решения: разности по кругу — это \(d_1, d_2, \ldots, d_{11}\), где \(d_i=a_{i+1}-a_i\) (со знаком, или модуль). Сумма \(d_1+d_2+\ldots+d_{11}=0\), так как мы возвращаемся в исходную точку. Но если все разности взяты по модулю, то \(d_i=\pm 1, \pm 2, \pm 3\). Чтобы сумма \(\pm 1\pm 1\pm 1\pm 1\pm 2\pm 2\pm 2\pm 2\pm 3\pm 3\pm 3=0\), нужна определённая комбинация знаков. Сумма модулей: \(4\cdot 1+4\cdot 2+3\cdot 3=4+8+9=21\) — нечётное. Чтобы знаковая сумма была 0, нужно разбить число 21 на две равные части (по 10.5), что невозможно для целого числа. Противоречие.

Ответ: доказано через чётность суммы модулей разностей (\(21\) — нечётное).

Семейство 2. Чётность количества

Сигнал. В задаче есть объекты (точки, числа, лампочки), и операция меняет состояние нескольких из них.

Главный ход. Посчитать количество объектов в определённом состоянии (например, нечётных, включённых) и проверить, как оно меняется при операции.

Задача 2.1

На столе лежат 100 монет, все орлом вверх. За один ход разрешается перевернуть ровно 99 монет. Можно ли добиться, чтобы все были решкой вверх?

Скелет решения: количество решек меняется на \(99-2k\) (если перевернули \(99-k\) орлов и \(k\) решек). По модулю 2 это \(99\equiv 1\), значит чётность количества решек меняется на каждом ходу. Начало: 0 решек (чётно). Конец: 100 решек (чётно). За чётное число ходов можно добиться чётной чётности — например, за 100 ходов. Возможно.

Ответ: да, можно добиться, например, за 100 ходов.

Задача 2.2

В кружке 99 школьников, каждый из них знаком ровно с 3 другими. Докажите, что число знакомых пар чётно (и значит, 99·3 — чётно), что противоречит. Значит, такая ситуация невозможна.

Скелет решения: число знакомств = \(\tfrac{99\cdot 3}{2}=\tfrac{297}{2}\), не целое — невозможно. Поэтому такого кружка не существует.

Ответ: не существует кружка из 99 школьников, в котором каждый знает ровно троих.

Задача 2.3

В таблице \(8\times 8\) расставлены знаки \(+\) и \(-\). За операцию разрешается одновременно поменять знаки во всех клетках одной строки или одного столбца. Можно ли из таблицы со всеми \(+\) получить таблицу, в которой ровно один \(-\)?

Скелет решения: количество \(-\) в строке после операции меняется на \(8-2k\) (где \(k\) — было до операции), что меняет чётность на \(8\equiv 0\pmod 2\); чётность числа \(-\) в каждой строке сохраняется. В начале — 0 минусов в каждой строке (чётно). Чтобы получить ровно один минус, надо, чтобы в одной строке было нечётное число минусов — противоречие.

Ответ: нет, невозможно.

Задача 2.4 — реальная (2010 Региональный №2)

Семь лыжников с номерами 1, 2, ..., 7 ушли со старта по очереди и прошли дистанцию — каждый со своей постоянной скоростью. Оказалось, что каждый лыжник ровно дважды участвовал в обгонах. (Текст частично OCR-фрагментарный.)

Скелет решения: каждый обгон — это событие между двумя лыжниками, и двое участвуют в нём. Если каждый лыжник участвовал ровно дважды, то общее число «участий» = \(7\cdot 2=14\). А число обгонов = \(14/2=7\). Проверка чётности количества участий важна для доказательства непротиворечивости или для нахождения максимума/минимума. Дальнейший анализ — через сравнение начального и конечного порядка лыжников: число инверсий = число обгонов = 7.

Ответ для курса: первый ход — посчитать сумму участий \(=2\cdot 7=14\), число обгонов \(=7\).

Семейство 3. Шахматная раскраска

Сигнал. В задаче есть клеточное поле, и нужно доказать, что некоторое замощение или обход невозможен.

Главный ход. Покрасить клетки в шахматном порядке (или другим естественным способом). Каждая фигура покрывает определённое количество чёрных и белых клеток; проверить, совпадает ли это с общим числом клеток каждого цвета.

Задача 3.1

Можно ли замостить доску \(8\times 8\) с двумя противоположными угловыми клетками доминошками \(1\times 2\)?

Скелет решения: на полной доске \(8\times 8\) — 32 чёрные и 32 белые клетки. Две противоположные угловые клетки одного цвета, поэтому после их удаления остаётся 30 одного цвета и 32 другого. Каждая доминошка покрывает 1 чёрную и 1 белую клетку, значит общее покрытие — равное число клеток обоих цветов. Замощение невозможно.

Ответ: нет, невозможно.

Задача 3.2

На доске \(10\times 10\) расставлены фишки в 25 клетках. За ход разрешается переместить фишку на соседнюю клетку (по стороне). Может ли каждая фишка побывать в каждой клетке доски ровно по одному разу?

Скелет решения: при ходе на соседнюю клетку фишка меняет цвет клетки (шахматная раскраска). Если фишка прошла все 100 клеток, она сделала 99 ходов и сменила цвет 99 раз, значит конечный цвет отличается от начального. Если фишка вернулась в исходную клетку (цикл), она сделала 100 ходов, изменение цвета 100 раз = чётно, цвет сохранён. Без дополнительных условий — да, возможно для одной фишки; для нескольких — требуется отдельный анализ.

Ответ: для одной фишки — да, обход возможен (гамильтонов цикл существует на доске \(10\times 10\)).

Задача 3.3

Можно ли замостить доску \(6\times 6\) тетраминошками формы L (4-клеточные L-образные)?

Скелет решения: всего 36 клеток, 9 тетраминошек. Шахматная раскраска: 18 чёрных и 18 белых. Каждая L-тетраминошка покрывает 3 одного цвета и 1 другого (или 1 и 3, в зависимости от положения). Если \(k\) L-тетраминошек покрывают 3 чёрных + 1 белую, то остальные \(9-k\) покрывают 1 чёрную + 3 белых. Общее число чёрных: \(3k+(9-k)=2k+9\). Это должно быть равно 18: \(2k+9=18\), \(2k=9\), \(k=4.5\) — не целое. Невозможно.

Ответ: нет, невозможно замостить L-тетраминошками.

Задача 3.4 — реальная (2016 Заключительный №1)

У менялы на базаре есть много ковров. Он согласен взамен ковра размера \(a\times b\) дать либо ковёр размера \(\tfrac{1}{a}\times\tfrac{1}{b}\), либо два ковра размеров \(c\times b\) и \(\tfrac{a}{c}\times\ldots\) (текст OCR-фрагментарный).

Скелет решения: рассматриваем инвариант — например, чётность числа «единичных» множителей или знак (положительность) площадей. Площадь ковра \(a\times b\) при первом обмене переходит в \(\tfrac{1}{ab}\), что равно \(1/S\). При втором обмене площадь сохраняется (\(c\cdot b+\tfrac{a}{c}\cdot\ldots=ab\)). Инвариант — это либо «остаётся ли \(1\) среди измерений», либо «знак \(\log S\)» по модулю некоторой операции.

Ответ для курса: первый ход — найти инвариант площади/логарифма площади; через него доказать, что определённую конфигурацию ковров получить нельзя.

Семейство 4. Чётность как ловушка для конструктивных задач

Сигнал. В задаче спрашивают: «можно ли построить?», «существует ли?». Применить чётность можно и для построения примера, и для доказательства невозможности.

Главный ход. Сначала проверить чётность ключевых параметров. Если она «не сходится» — задача невыполнима.

Задача 4.1

В каждой клетке таблицы \(5\times 5\) стоит число \(\pm 1\). За один ход можно поменять знаки во всех клетках одной строки или столбца. Можно ли из таблицы со всеми \(+1\) получить таблицу, в которой произведение всех чисел равно \(-1\)?

Скелет решения: произведение всех 25 чисел = \(\pm 1\). При операции «поменять знаки в строке» произведение умножается на \((-1)^5=-1\) (5 элементов в строке). При операции «поменять знаки в столбце» произведение умножается на \((-1)^5=-1\). Каждый ход меняет знак произведения. Начало: \(+1\). После \(n\) ходов произведение \(=(-1)^n\). Чтобы получить \(-1\), нужно нечётное число ходов. Возможно.

Ответ: да, можно — например, одна операция (поменять знаки в одной строке).

Задача 4.2

В строке записано 100 чисел: 50 единиц и 50 двоек. За операцию можно выбрать два соседних числа \(a, b\) и заменить их на \((a+b)/\!\!\!\gcd(a,b)\) — то есть... Скажем проще: можно ли упорядочить 50 единиц и 50 двоек так, чтобы по чётности позиций они чередовались?

Скелет решения: позиции 1, 2, ..., 100. Если 1 на нечётных позициях и 2 на чётных — это полное чередование. Чётность количества: на нечётных позициях 50 мест, на чётных — 50. Расставить 50 единиц на 50 нечётных мест — возможно. Замечание: задача тривиальная по чётности.

Ответ: да, можно.

Задача 4.3

На столе лежит \(2025\) монет. За ход двое игроков по очереди берут 1, 2 или 3 монеты. Проигрывает тот, кто берёт последнюю. Кто выиграет при правильной игре?

Скелет решения: число монет \(2025=4\cdot 506+1\). Стратегия победителя: оставить противнику \(4k+1\) монету. Тогда первый игрок берёт 0... нет, должен взять хотя бы 1. После хода первого остаётся \(2025-(1,2,3)\) монет. Второй дополняет до \(2025-4=2021\). Так продолжается до 5 монет — первому остаётся 5 монет. Если первый берёт 1, остаётся 4 — второй берёт 3, остаётся 1, первый берёт последнюю — проигрывает. Если первый берёт 2, остаётся 3 — второй берёт 2, остаётся 1, первый проигрывает. Аналогично. Значит, выигрывает второй.

Ответ: выигрывает второй игрок.

Задача 4.4 — реальная (2024 Школьный №3)

Жора задумал три натуральных числа \(a, b, c\). Чему могут равняться \(a+b\), \(b+c\) и \(c+a\)?

a) 102, 201, 300;
b) 201, 302, 403;
c) 201, 303, 606;
d) 302, 305, 507;
e) 301, 403, 505.

Скелет решения: \((a+b)+(b+c)+(c+a)=2(a+b+c)\) — всегда чётное. Проверяем чётность суммы троек:
- a) \(102+201+300=603\) — нечётно. Невозможно.
- b) \(201+302+403=906\) — чётно. Возможно. \(a+b+c=453\), \(c=453-201=252, a=453-403=50, b=453-302=151\). Проверка: натуральные? Да.
- c) \(201+303+606=1110\) — чётно. \(a+b+c=555\), \(c=555-201=354, a=555-606=-51\) — отрицательное! Невозможно.
- d) \(302+305+507=1114\) — чётно. \(a+b+c=557\), \(a=557-305=252, b=557-507=50, c=557-302=255\). Натуральные? Да.
- e) \(301+403+505=1209\) — нечётно. Невозможно.

Ответ: возможны варианты b) и d).

Семейство 5. Чётность простых чисел

Сигнал. В задаче есть простые числа, и нужно использовать тот факт, что 2 — единственное чётное простое.

Главный ход. Если в задаче встречается \(p+q, p-q, pq+1\) и т.п. с простыми \(p, q\), сразу проверить случай \(p=2\) или \(q=2\).

Задача 5.1

Найдите все простые \(p\), такие что \(p^2+2\) — тоже простое.

Скелет решения: если \(p=3\), то \(p^2+2=11\) — простое. Если \(p\ne 3\), то \(p\equiv\pm 1\pmod 3\), значит \(p^2\equiv 1\pmod 3\), \(p^2+2\equiv 0\pmod 3\), составное (и больше 3). Только \(p=3\).

Ответ:\[ p=3. \]

Задача 5.2

Найдите все простые \(p, q\), такие что \(p+q\) и \(p-q\) — также простые.

Скелет решения: \(p>q\). Если \(q\ne 2\), то \(p, q\) — нечётные простые, и \(p-q\) — чётное, значит \(p-q=2\). Тогда \(p=q+2\). \(p+q=2q+2=2(q+1)\) — чётное и больше 2, значит составное. Противоречие. Значит \(q=2\), \(p\) — нечётное простое, \(p-2\) и \(p+2\) — простые. Это \(p=5\): \(p-2=3, p+2=7\) — всё простые.

Ответ:\[ (p,q)=(5,2). \]

Задача 5.3

Может ли сумма пяти простых чисел быть равна \(2025\)?

Скелет решения: \(2025\) — нечётное. Сумма пяти простых: если все простые нечётные, их сумма — нечётная (5 нечётных = нечётное). Если хотя бы одно простое \(=2\), сумма \(=2+\)(сумма 4 нечётных) \(=2+\)чётное \(=\)чётное. Значит, для нечётной суммы нужно, чтобы все 5 простых были нечётными.

Ответ: да, например \(2025=5+5+5+5+2005\) — но \(2005=5\cdot 401\) не простое. Попробуем \(2025=3+5+7+11+1999\), а \(1999\) — простое (проверка: не делится на 2,3,5,7,11,13,17,19,23,29,31,37,41,43 — все нет). Значит, можно.

Задача 5.4 — реальная (2022 Школьный №4)

Простое число \(p\) таково, что число \(p+25\) является седьмой степенью простого числа. Чему может быть равно \(p\)? Укажите все возможные варианты.

Скелет решения: \(p+25=q^7\), где \(q\) — простое. Тогда \(p=q^7-25\). Проверим случаи:
- \(q=2\): \(p=128-25=103\). Проверка: \(103\) — простое (не делится на 2, 3, 5, 7). Да.
- \(q=3\): \(p=2187-25=2162=2\cdot 1081\) — не простое.
- \(q\ge 5\): \(q^7\) — нечётное, \(p=q^7-25\) — чётное (нечётное минус нечётное). \(p\) чётное и больше 2, значит составное. Не подходит.

Остался только \(q=2, p=103\).

Ответ:\[ p=103. \]

Семейство 6. Чётность позиций в перестановке (инверсии)

Сигнал. В задаче есть набор объектов в порядке, и операция меняет местами два объекта.

Главный ход. Подсчитать число инверсий (пар, расположенных «не в порядке»). Каждая транспозиция соседних элементов меняет число инверсий на \(\pm 1\); каждая транспозиция произвольных — на нечётное число.

Задача 6.1

Из перестановки \((1, 2, 3, 4, 5)\) можно ли за чётное число транспозиций получить \((2, 1, 3, 4, 5)\)?

Скелет решения: перестановка \((2, 1, 3, 4, 5)\) отличается от исходной одной транспозицией (1 и 2). Это нечётная перестановка. Чтобы получить её, нужно сделать нечётное число транспозиций.

Ответ: нет, требуется нечётное число транспозиций.

Задача 6.2

В строке записаны числа \(1, 2, 3, 4, 5, 6, 7, 8, 9\). За операцию можно поменять местами два соседних. Можно ли получить порядок \(9, 8, 7, 6, 5, 4, 3, 2, 1\)?

Скелет решения: число инверсий в обратном порядке = \(\binom{9}{2}=36\) — чётное. Каждая операция меняет число инверсий на \(\pm 1\). За 36 операций можно получить — это минимальное число шагов.

Ответ: да, за 36 операций (или больше с возвратами).

Задача 6.3

В таблице \(n\times n\) разрешается за один ход поменять местами две соседние строки или два соседних столбца. Можно ли получить таблицу, в которой строка \(i\) перешла на место \(\sigma(i)\), для некоторой перестановки \(\sigma\)?

Скелет решения: операция «поменять две соседние строки» — это транспозиция в группе \(S_n\). Любую перестановку можно представить как произведение транспозиций соседних. Поэтому любую перестановку строк можно реализовать.

Ответ: любую перестановку можно реализовать.

Задача 6.4 — реальная (2010 Муниципальный №5)

На гранях каждого из восьми кубиков нарисованы точки: по одной на двух противоположных гранях, по две на других двух противоположных, по три — на двух оставшихся. Из этих восьми кубиков сложен куб \(2\times 2\times 2\). Найдите минимальное и максимальное число точек на поверхности этого куба.

Скелет решения: на каждом кубике сумма точек на двух противоположных гранях фиксирована: 1+1=2, 2+2=4, 3+3=6. Общая сумма точек на одном кубике = \(2+4+6=12\). У \(2\times 2\times 2\) куба каждый малый кубик имеет 3 «внешних» грани и 3 «внутренних». Минимум: внешние грани несут наименьшее число точек. Каждая пара противоположных граней (1, 1), (2, 2), (3, 3): из них одна на поверхности, одна нет. Поэтому на поверхности каждого кубика лежит одна грань из каждой пары: либо 1, либо 2, либо 3 — и итого 1+2+3=6 (или другие комбинации в зависимости от поворота). Минимальная сумма на поверхности одного кубика: если все три «внешних» грани несут наименьшие числа из пар, это 1+1+1 — но грани (1,1) противоположны, значит обе одновременно «наружу» не выйдут; «наружу» выходит одна 1, одна 2, одна 3 — сумма 6 (это фиксировано!). Значит на каждом из 8 кубиков по 6 точек на поверхности: общая сумма \(=8\cdot 6=48\), но это число точек на 24 внешних гранях. Но: грани кубиков, выходящие наружу, — это 3 грани на каждом из 8 малых кубиков = 24 грани, на которых сумма точек 48. Это и минимум, и максимум.

Ответ: на поверхности всегда ровно \(48\) точек (минимум = максимум = 48).

Семейство 7. Чётность как ключ к делителям

Сигнал. Задача о делителях натурального числа, особенно когда упоминаются «маленькие» делители.

Главный ход. Использовать тот факт, что число имеет чётный делитель \(\Leftrightarrow\) оно само чётное. И учесть, что наименьший делитель > 1 либо равен 2, либо нечётный простой.

Задача 7.1

У натурального числа \(N\) ровно 6 делителей, наименьшие два — это 2 и 3. Найдите \(N\).

Скелет решения: \(N\) делится на 2 и 3, значит на 6. \(N=2^a\cdot 3^b\cdot\ldots\). Число делителей \(=6=2\cdot 3\). Варианты: \(N=p^5\) (6 делителей) — но тогда наим. делитель один, не двое разных простых. \(N=p^2 q\) с разными простыми — даёт 6 делителей. С \(p=2, q=3\): \(N=4\cdot 3=12\), делители: 1, 2, 3, 4, 6, 12. Наим. \(>1\) — 2, потом 3. \(N=2\cdot 9=18\), делители: 1, 2, 3, 6, 9, 18. Наим. \(>1\) — 2, потом 3.

Ответ:\[ N=12 \text{ или } N=18. \]

Задача 7.2

Найдите все натуральные \(n\), такие что \(n^2+n+1\) делится на 7.

Скелет решения: \(n^2+n+1\pmod 7\). Перебор \(n=0,1,\ldots,6\): \(0, 3, 0, 6, 0, 3, 6\). Нули при \(n\equiv 0, 2, 4\pmod 7\)? Проверим: \(n=0\): 1; \(n=1\): 3; \(n=2\): 7≡0 ✓; \(n=3\): 13≡6; \(n=4\): 21≡0 ✓; \(n=5\): 31≡3; \(n=6\): 43≡1. Делится при \(n\equiv 2\) или \(n\equiv 4\pmod 7\).

Ответ:\[ n\equiv 2 \text{ или } 4\pmod 7. \]

Задача 7.3

Найдите наименьшее натуральное \(n\), у которого ровно 12 делителей, причём наименьший делитель > 1 равен 3.

Скелет решения: \(n\) не делится на 2, делится на 3. \(n=3^a p^b q^c\ldots\) с нечётными простыми \(>3\). 12 делителей: возможно \(3^{11}\), \(3^5 p\), \(3^3 p^2\), \(3^2 p^3\), \(3\cdot p^5\), \(3\cdot p\cdot q^2\), \(3\cdot p^2\cdot q\), \(3\cdot p\cdot q\cdot r\)... Наименьшие нечётные простые после 3 — это 5, 7, 11. Минимизируем: \(3^2\cdot 5\cdot 7=315\) (12 делителей? проверим: \((2+1)(1+1)(1+1)=12\) ✓), а \(3\cdot 5\cdot 7\cdot 11=1155\) больше. \(3\cdot 5^2\cdot 7=525\) больше 315. \(3^3\cdot 5^2=675\) больше. \(3^5\cdot 5=1215\) больше. Минимум: 315.

Ответ:\[ n=315. \]

Задача 7.4 — реальная (2023 Школьный №4)

Петя задумал составное натуральное число \(N<1000\). Он выписал все натуральные делители \(N\), не равные 1. Оказалось, что два наименьших числа на доске различаются на 39. Чему может быть равно \(N\)?

Скелет решения: наим. делитель \(N\) (>1) — это наименьшее простое \(p\), делящее \(N\). Второй наименьший делитель — либо \(p^2\), либо следующее простое \(q>p\), делящее \(N\). Случаи:
- \(p^2-p=39\): \(p(p-1)=39=3\cdot 13\). \(p=?\); решение \(p^2-p-39=0\), \(p=(1+\sqrt{157})/2\) — не целое.
- \(q-p=39\), где \(p, q\) — простые, делящие \(N\), и \(p^2>q\) (чтобы не было других делителей между ними). Пары \((p, q)\) простых с разностью 39: \((2, 41)\) — но 41 > \(p^2=4\), значит между 2 и 41 на доске может быть 4 (если \(N\) делится на 4) — но тогда «второй наименьший» был бы 4, не 41. Чтобы второй был именно \(q\), нужно \(p^2>q\) ИЛИ \(N\) не делится на \(p^2\). Если \(N=pq\) и \(p=2, q=41\): \(N=82\), делители: 1, 2, 41, 82. Два наим. >1: 2 и 41, разность 39 ✓, \(N=82<1000\) ✓.
- \((p, q)=(3, ?)\)? \(q=42\) — не простое. Нет.
- \((p, q)=(5, ?)\)? \(q=44\) — не простое.
- Других пар простых с разностью 39 нет (так как одно из \(p, q\) должно быть чётным, то есть \(=2\); 39 — нечётное).

Также проверим \(N=p\cdot q\cdot k\) для других вариантов:
- \(N=82, 164, 246, 328, 410, 492, 574, 656, 738, 820, 902, 984\) — кратные 82. Но при \(N=164=4\cdot 41\), делители: 1, 2, 4, 41, 82, 164. Наим. >1 — 2 и 4, разность 2, не 39. Поэтому только \(N=82\) и \(N=82\cdot p\), где \(p\) — простое \(>41\), чтобы между 2 и 41 не было других делителей. Но \(82\cdot 43=3526>1000\). Значит \(N=82\) — единственное.

Однако: можно ещё \(N=2\cdot 41\cdot p\), где \(p>41\) — но это \(>1000\). А \(N=2^a\cdot 41\) с \(a\ge 2\): даёт делитель 4, который меньше 41 — не подходит.

Ответ:\[ N=82. \]

Мини-тест после статьи

1. На доске числа \(1, 2, \ldots, 99\). За ход стираем два числа \(a, b\), пишем \(a+b\). Какое число останется?
2. В таблице \(7\times 7\) расставлены знаки \(+\) и \(-\). За ход меняем знаки одной строки или одного столбца. Можно ли из всех \(+\) получить ровно один \(-\)?
3. Может ли сумма четырёх простых чисел быть равна \(2024\)?
4. Найдите все простые \(p\), для которых \(p+10\) и \(p+14\) — простые.
5. На столе 100 монет, все орлом. За ход переворачиваем ровно 47 монет. Можно ли добиться, чтобы все были решкой?

Ответы:

1. Сумма \(1+2+\ldots+99=\tfrac{99\cdot 100}{2}=4950\) — это инвариант. Останется \(4950\).
2. При операции в строке меняется 7 знаков — нечётное число, чётность числа \(-\) в строке меняется. Аналогично для столбца. Невозможно: в начальной конфигурации в каждой строке 0 минусов (чётно), а в искомой ровно одна строка имеет 1 минус (нечётно) — но переход в эту строку требует нечётного числа операций со столбцами, что меняет чётность во всех строках сразу — анализ показывает противоречие. Нельзя.
3. \(2024\) чётно. Сумма четырёх простых: если все нечётные — сумма чётная. Если один \(=2\), сумма \(=2+\)три нечётных \(=2+\)нечётное \(=\)нечётное. Если два \(=2\), сумма \(=4+\)два нечётных \(=\)чётное. Да: \(2024=2+2+11+2009\)? \(2009=7\cdot 7\cdot 41\) — не простое. Возьмём \(2024=3+3+5+2013\), \(2013=3\cdot 11\cdot 61\) — не простое. \(2024=3+5+7+2009\) — не работает. \(2024=11+13+19+1981\), \(1981=7\cdot 283\) — не простое. Аккуратно: \(2024=3+5+13+2003\), \(2003\) — простое! ✓. Да.
4. \(p, p+10, p+14\) — все простые. По модулю 3: \(p, p+1, p+2\) (так как \(10\equiv 1, 14\equiv 2\pmod 3\)). Среди них одно делится на 3. Значит либо \(p=3\) (проверим: \(3, 13, 17\) — все простые ✓), либо \(p+10=3\Rightarrow p=-7\) — нет, либо \(p+14=3\Rightarrow p=-11\) — нет. Только \(p=3\).
5. За один ход число решек меняется на \(47-2k\equiv 1\pmod 2\) (где \(k\) — было решек). Чётность числа решек меняется на каждом ходу. Начало: 0 (чётно). Конец: 100 (чётно). Нужно чётное число ходов. Возможно.

Финальный конспект

• E5 — это поиск инварианта в задаче с операциями.
• Самый частый инвариант — чётность суммы или количества.
• Чётность работает в обе стороны: помогает доказать невозможность (если инварианты не совпадают) и подсказывает конструкцию (если совпадают — пробуй построить).
• Раскраски: шахматная, трёхцветная, по столбцам — каждая даёт свой инвариант.
• Простое \(=2\) — единственное чётное простое; в задачах с простыми всегда рассматривай его отдельно.
• Формулы под рукой:\[ \text{инверсии}(\sigma)\bmod 2 = \mathrm{sgn}(\sigma),\quad \mathrm{sgn}(\sigma\tau)=\mathrm{sgn}(\sigma)\mathrm{sgn}(\tau). \]
• Когда чётность не работает — пробуй модуль 3, 4, 5, или раскраску по полосам.

Главное правило E5 — прежде чем строить пример, проверь инвариант по модулю 2. Если инвариант показывает невозможность — задача решена за одну строку. Если показывает возможность — переходи к построению.