РЕШУ ОЛИМП — математика

Задания

Последовательность чисел τ (1), τ (2), ..., τ (n) называется перестановкой длины n, если каждое из чисел 1, 2, ..., n встречается в этой последовательности ровно один раз. Например, τ (1)  =  3, τ (2)  =  2, τ (3)  =  1  — перестановка длины 3. Найдите все n, для которых найдётся перестановка τ (1), τ (2), ..., τ (n), удовлетворяющая четырём условиям:

• Числа τ (i) − i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

• Числа τ (i) − 2i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

• Числа τ (i) − 3i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

• Числа τ (i) − 4i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

Решение. Будем решать чуть обобщённую задачу, а именно: зафиксируем натуральное m и будем искать все n, для которых в любом из m множеств $левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус j i | 1 меньше или равно i меньше или равно n правая фигурная скобка$ все остатки различны. Индекс j пробегает значения $1 меньше или равно j меньше или равно m.$

Для начала докажем, что все n, не делящиеся на простые числа меньшие либо равные m + 1, подходят. Рассмотрим перестановку τ: i → (m + 1)i mod n (здесь мы позволим себе вольность считать, что остатки идут от 1 до n, а не от 0 до n – 1 как обычно). Поскольку n взаимно просто с m + 1, остатки не повторяются. Значит, по принципу Дирихле, каждый остаток встречается ровно один раз. Аналогично, каждый остаток встречается ровно один раз и в каждом из множеств

$левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус i \mid 1 меньше или равно i меньше или равно n правая фигурная скобка ,$ $левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус 2 i \mid 1 меньше или равно i меньше или равно n правая фигурная скобка ,$ $\ldots,$ $левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус m i \mid 1 меньше или равно i меньше или равно n правая фигурная скобка .$

Докажем, что перестановки с требуемыми свойствами не существует если $n \vdots p$ и $p меньше или равно m плюс 1.$ Предположим обратное, зафиксируем наименьшее такое p и обозначим через k максимальную степень p, на которую делится n.

Сперва рассмотрим случай p  =  2. Заметим что

$1 плюс 2 плюс умножить на s плюс n = дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби ,$

формула легко доказывается по индукции. Тогда сумма n чисел, дающих остатки 1, 2, ..., n, сравнима с $дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби$ по модулю n. Посчитаем двумя способами остаток суммы $\sum_i=1 в степени n \tau левая круглая скобка i правая круглая скобка минус i$ по модулю n. С одной стороны, все слагаемые дают разные остатки, значит, сумма $дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби .$ С другой стороны, по тем же соображениям у суммы отдельно $\sum_i=1 в степени n \tau левая круглая скобка i правая круглая скобка$ такой остаток, и у суммы $\sum_i=1 в степени n i$ такой же, значит, их разность имеет остаток 0. Заметим, что

$дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби \not \equiv 0 mod n,$

поскольку n + 1 нечетное а $дробь: числитель: n, знаменатель: 2 конец дроби$ не делится на 2^k. Предположение приведено к противоречию.

Попробуем получить решение в том же духе для произвольного p. Небольшой догадкой, которую нужно сделать на этом этапе решения, будет то, что считать надо сумму p  — 1-х степеней. Слабой подсказкой в эту сторону является то, что p – 1  =  1 для двойки p  =  2, и в этом же случае сработал подсчет суммы первых степеней. Гораздо более сильной  — то что p  — 1-е степени по модулю p ведут себя просто  — это 1 если число не равно нулю, 0, если равно.

Итак, далее считаем что $p больше 2,$ обозначим

$S левая круглая скобка m правая круглая скобка =\sum_i=1 в степени m i в степени левая круглая скобка p минус 1 правая круглая скобка .$

Лемма 1. Заметим, что $S левая круглая скобка n правая круглая скобка \vdots p в степени левая круглая скобка k минус 1 правая круглая скобка$ и $S левая круглая скобка n правая круглая скобка / \vdots p в степени k .$ Достаточно доказать этот факт для $n = p в степени k ,$ поскольку

$S левая круглая скобка n правая круглая скобка \equiv дробь: числитель: n, знаменатель: p в степени k конец дроби S левая круглая скобка p в степени k правая круглая скобка mod p в степени k .$

Для S(p^k) проведем индукцию по k. При k  =  1 утверждение следует из Малой теоремы Ферма: среди слагаемых p – 1 единица и один ноль. Пусть доказано для k, докажем для k + 1. Тогда

$S левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка =\sum_i=1 в степени левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка =\sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i плюс jp в степени k правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка \equiv \sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка p минус 1 правая круглая скобка jp в степени k i в степени левая круглая скобка p минус 2 правая круглая скобка правая круглая скобка \equiv$ $S левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка =\sum_i=1 в степени левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка =$
$=\sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i плюс jp в степени k правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка \equiv \sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка p минус 1 правая круглая скобка jp в степени k i в степени левая круглая скобка p минус 2 правая круглая скобка правая круглая скобка \equiv$

$\equiv \sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка левая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка p плюс дробь: числитель: p левая круглая скобка p минус 1 правая круглая скобка в квадрате , знаменатель: 2 конец дроби p в степени k i в степени левая круглая скобка p минус 2 правая круглая скобка правая круглая скобка \equiv pS левая круглая скобка p в степени k правая круглая скобка .$

Все сравнения по модулю p^k+1.

Теперь для каждого j: $1 меньше или равно j меньше или равно p минус 1$ рассмотрим сумму

$S_j левая круглая скобка n правая круглая скобка =\sum_1 меньше или равно i меньше или равно n левая круглая скобка \tau левая круглая скобка i правая круглая скобка минус ij правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка .$

Раскроем все степени по биному Ньютона, получим слагаемые вида

$левая круглая скобка \begin{align p минус 1s \endalign правая круглая скобка левая круглая скобка минус j правая круглая скобка в степени s \sum_1 меньше или равно i меньше или равно n\tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 минус s правая круглая скобка умножить на i в степени s .$

С другой стороны, все члены в S_j(n)  — это переставленные в каком-то порядке остатки по модулю n членов суммы S(n), то есть $S_j левая круглая скобка n правая круглая скобка \equiv S левая круглая скобка n правая круглая скобка mod n.$ Итак, мы хотим найти такой набор α_j, чтобы домножив на него сравнимости $S_j левая круглая скобка n правая круглая скобка \equiv S левая круглая скобка n правая круглая скобка$ и сложив мы смогли бы прийти к противоречию. Сделать это поможет вторая лемма.

Лемма 2. Существуют такие целые числа α₁, ..., α_p – 1, что

$альфа _11 плюс альфа _22 плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка \equiv 0 mod p в степени k ;$

$альфа _11 в квадрате плюс альфа _22 в квадрате плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в квадрате \equiv 0 mod p в степени k ;$

$\ldots$

$альфа _11 в степени левая круглая скобка p минус 2 правая круглая скобка плюс альфа _22 в степени левая круглая скобка p минус 2 правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в степени левая круглая скобка p минус 2 правая круглая скобка \equiv 0 mod p в степени k ;$

$альфа _11 в степени левая круглая скобка p минус 1 правая круглая скобка плюс альфа _22 в степени левая круглая скобка p минус 1 правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка не равно 0 mod p в степени k .$

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

$альфа _1S_1n плюс альфа _1S_1n плюс \ldots плюс альфа _p минус 1S_p минус 1n \equiv левая круглая скобка альфа _1 плюс альфа _2 плюс \ldots плюс альфа _p минус 1 правая круглая скобка S левая круглая скобка n правая круглая скобка mod p в степени k .$ $альфа _1S_1n плюс альфа _1S_1n плюс \ldots плюс$
$плюс альфа _p минус 1S_p минус 1n \equiv левая круглая скобка альфа _1 плюс альфа _2 плюс \ldots плюс альфа _p минус 1 правая круглая скобка S левая круглая скобка n правая круглая скобка mod p в степени k .$

С одной стороны, если раскрыть все S_j по биному Ньютона, и собрать вместе члены вида $\tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 минус s правая круглая скобка умножить на i в степени s ,$ $1 меньше или равно s меньше или равно p минус 2,$ то по Лемме 2 перед каждым членом коэффициент, равный нулю по модулю p^k. Тогда:

$альфа _1 левая круглая скобка \sum_i=0 в степени n плюс \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка плюс альфа _2 левая круглая скобка \sum_i=0 в степени n \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка 2i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка \sum_i=0 в степени n \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка левая круглая скобка p минус 1 правая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка =$
$= левая круглая скобка альфа _1 плюс альфа _2 плюс \ldots плюс альфа _p минус 1 правая круглая скобка S левая круглая скобка n правая круглая скобка .$

Вспомнив, что $\sum_i=1 в степени n \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка =S левая круглая скобка n правая круглая скобка$ видим, что все члены вида $\tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка$ сократились с правой частью, итак

$альфа _1 \sum_i=0 в степени n i в степени левая круглая скобка p минус 1 правая круглая скобка плюс альфа _2 \sum_i=0 в степени n левая круглая скобка 2i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка плюс \ldots плюс альфа _p минус 1 \sum_i=0 в степени n левая круглая скобка левая круглая скобка p минус 1 правая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка \equiv 0 равносильно$
$равносильно левая круглая скобка альфа _1 1 в степени левая круглая скобка p минус 1 правая круглая скобка плюс альфа _2 2 в степени левая круглая скобка p минус 1 правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка S левая круглая скобка n правая круглая скобка \equiv 0.$

Но первая скобка не делится на p по Лемме 2, а S(n) не делится на p^k по Лемме 1. Осталось доказать лемму 2. Сперва отметим, что если вместо набора целых чисел α_j удалось подобрать набор рациональных чисел β_j, таких что их знаменатели не делятся на p, все сравнимости из условия леммы заменились на равенства, а последнее выражение равно целому числу, не делящемуся на p  — то лемма доказана, достаточно все β_j заменить на сравнимые с ними по модулю p^k целые числа. Сравнимость определена корректно поскольку знаменатели не делятся на p.

Теперь осталось взять

$бета _j = левая круглая скобка минус 1 правая круглая скобка в степени j дробь: числитель: 1, знаменатель: j конец дроби левая круглая скобка \begin{align p минус 2j минус 1 \endalign правая круглая скобка .$

Читателю остается упражнение доказать (например, по индукции, поскольку простота p здесь уже не важна), что во всех условиях Леммы 2, кроме последнего, получается 0, а в последнем $\pm левая круглая скобка p минус 2 правая круглая скобка !.$

Ответ: все n, не делящиеся ни на 2, ни на 3, ни на 5.

Критерии оценивания выполнения задания	Баллы
Приведено полное решение	20
Найден пример, работающий для всех n, не делящихся на 2, 3 и 5	12
Доказано, что n — нечётное	8
Решение не соответствует ни одному из перечисленных выше критериев	0
Максимальный балл	20

№ п/п	№ задания	Ответ
1	244	все n, не делящиеся ни на 2, ни на 3, ни на 5.

Ключ