Тема ЮМШ (олимпиада Юношеской Математической Школы)

Теория чисел на ЮМШ

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела юмш (олимпиада юношеской математической школы)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#83387

Цель этого сюжета — доказательство следующего утверждения:

Пусть $p$ — нечётное простое чисто. Докажите, что существует ровно $(p− 3)∕2$ упорядоченных четвёрок $(a,b,c,d)$ натуральных чисел, для которых $ab+ cd =p$ и $max(c,d)<min(a,b)$ .

Если $r$ — остаток по модулю $p$ , то назовём четвёрку ( $a,b,c,d$ ), удовлетворяющую условиям выше, $r$ -четверкой, если $c ≡ra$ (mod $p$ ).

1. Докажите, что если $r$ -четвёрка существует, то $r∈{2,3,...,p− 2}$ .

2. Докажите, что для данного $r$ существует не более одной $r$ -четвёрки.

3. Докажите, что если $r$ -четверка существует, то $(p − r)$ -четвёрки не существует.

4. Докажите, что для всякого $r∈{2,3,...,p− 2}$ существует либо $r$ -четвёрка, либо $(p − r)$ -четвёрка.

Источники: ЮМШ - 2024, сюжет 1 (см. yumsh.ru)

Показать доказательство

1. Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= 1$ . Тогда $p=ab+ cd≡$ $≡ ab+ rad= a(b+d)$ (mod $p$ ). Получаем, что $. a(b+ d)..p$ . Тогда либо $a$ , либо $b+ d$ делится на $p$ . Тогда либо $a ≥p$ , $b+ d≥ p$ . В первом случаем получаем, что $ab+ cd≥ p+cd> 1$ . Во втором же $ab+cd≥ 2b+d ≥p +1$ . Получаем, что $1$ -четверки не существует.

Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= p− 1$ . Тогда $p= ab+cd≡$ $≡ab+ rad =a(b− d)$ (mod $p$ ). Получаем, что $. a(b− d)..p$ . Тогда либо $a$ , либо $b− d$ делится на $p$ . Тогда либо $a≥ p$ , $b+ d≥ p$ ( $b− d ⁄=0$ , поскольку $b> d$ ). В первом случаем получаем, что $ab+ cd≥p +cd> 1$ . Во втором же $ab+cd≥ b+ d> b− d ≥p$ . Получаем, что $(p− 1)$ -четверки тоже не существует.

2. Пусть $(a,b,c,d)$ , $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с одним и тем же $r$ . Тогда $ac′ ≡ara′ ≡ ca′$ (mod $p$ ), аналогично $bd′ ≡− rdd′ ≡ b′d$ (mod $p$ ). Т.е. $ac′− a′c$ , $bd′− b′d$ кратны $p$ .

Предположим, что эти разности одновременно не равны нулю. Пусть не умаляя общности $ac′− a′c> 0$ , тогда $ac′ >p >ab$ , т.е. $c′ > b$ и тем более $c′ > d$ . Отсюда получаем, что $|bd′− b′d|< max(bd′,b′d) <max(c′d′,b′c′)= b′c′ < a′b′ < p$ откуда (т.к. $|b′d− b′d|$ кратно $p$ ) получаем $bd′− b′d= 0$ — противоречие.

Пусть теперь одна из исходных разностей равна нулю (не умаляя общности $bd′− b′d$ ). Отметим, что из равенств $ab+ cd =p =a′b′+ c′d′$ следует взаимная простота $b$ и $d$ , $b′$ и $d′$ . Поэтому из равенства $bd′ = b′d$ следует, что $b= b′$ и $d =d′$ , а из него — $(a− a′)b= (c′− c)d$ . В силу взаимной простоты $b$ и $d$ имеем $a− a′ =dx$ , $c′− c =bx$ . При $x> 0$ это противоречит условию $c′ < b′ = b$ , при $x< 0$ — условию $c< b$ . Значит $x =0$ , $a =a′$ , $c= c′$ — четверки полностью совпадают.

3. Пусть $(a,b,c,d)$ , $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с $r$ и c $r′ = p− r$ соответственно. Тогда $ac′ ≡− ara′ ≡ −ca′$ (mod $p$ ), аналогично $bd′ ≡ −rdd′ ≡−b′d$ (mod $p$ ). Т.е. $ac′+a′c$ , $bd′+b′d$ кратны $p$ .

Пусть $c′ ≥ b$ , а значит $c′ > c,d$ , тогда, аналогично прошлому пункту, $bd′+b′d< c′d′+b′c′ < c′d′+b′a′ = p$ — противоречие с делимостью на $p$ . Значит $c′ < b$ и, аналогично $c< b′$ , $d′ < a$ , $d< a′$ . Тогда $a′c+ac′ <ab+ a′b′ < 2p$ , поэтому из делимости $ac′+a′c= p$ и аналогично $b′d+bd′ = p$ .

Предположим теперь, не умаляя общности, что $a$ — наибольшее из чисел. Вычитая из $ab+cd$ равное ему $ac′+ ca′$ , получаем $a(b− c′)=c(a′− d)$ , откуда из взаимной простоты $a$ и $c$ получаем, что $a′− d$ делится на $a$ — противоречие с тем, что $a< a′$ , $a′− d> 0$ .

4. Рассмотрим на плоскости множество всех векторов $(x,y)$ с целыми координатами $x,y$ такими, что $y ≡ rx$ (mod $p$ ) или $y ≡(p− r)x$ . Отметим, что это множество вместе с каждым вектором $(x,y)$ содержит также и $(±x,±y)$ . Рассмотрим в нашем множестве вектор с минимальной суммой координат. В силу замечания выше можно считать, что вектор $u:= (a,c)$ , где $a,c>0$ , $a ⁄=c$ (на осях координат и на биссектрисах углов между ними такой вектор лежать не может, поскольку $2≤ r≤p − 1$ ), если $c ≡(p− r)a$ (mod $p$ ), то переобозначим $r$ и $p− r$ . Предположим пока, что $a> c$ . Рассмотрим прямую $ℓ$ с уравнением $xc− ya= p$ . Будем искать точку $(d,−b)$ на этой прямой такую, что $d> 0,d <a,d< b,c <b$ — тогда четверка $(a,b,c,d)$ и будет искомой. Заметим, что если $(x,y)∈ℓ$ , то $(x− a,y − c)∈ℓ$ .

Прямая $ℓ$ где-то пересекает прямую $y+ x= 0$ . Пусть точка $(x0,y0)∈ ℓ$ с целыми $x0,y0$ лежит выше прямой $y+ x= 0$ , а точка $v0 :=(x0− a,y0− c)$ — (нестрого) ниже.

Во-первых, проверим, что $x0− a >0$ . В самом деле, в противном случае $x0 ≤ a$ . Из выбора вектора $u$ имеем $a+ c≤ |x0− a|+|y0− c|= a− x0 +|y0 +c|$ . Если $c≥y0$ , то $a− x0+ |y0− c|= a+ c− x0− y0 < a+ c$ — противоречие. Если же $y0 >c$ , то $p =x0c− y0a <ac− ac= 0$ — снова противоречие.

Итак, $x0− a> 0$ . Поскольку $(x0− a)+ (y0− c)≤ 0$ , имеем $y0 − c< 0$ . Если $y0 ≥ 0$ , то $0< x0− a ≤c− y0 ≤ c$ и обе координаты вектора $v0$ по модулю не больше, чем $c$ — это опять противоречит выбору $u$ . Значит, $y0 < 0$ и $c− y0 > c$ . Теперь выберем наибольшее целое неотрицательное $m$ , при котором $x0− a− ma≥ 0$ . Ясно, что это неотрицательное значение строго меньше, чем $a$ . Тогда вектор $v0− mu =(x0− a− ma, y0− c− mc)$ и есть искомый вектор. Действительно, все нужные неравенства уже установлены, осталось только исключить случай $x0 − a− ma =0$ , но в таком случае из уравнения прямой $ℓ$ получаем $xc− ya= p$ , $− (y0− c− mc)a =p$ , что невозможно в силу того, что $a> c> 0$ , $− y0+c +mc ≥1 +c+ mc≥ 2$ .

Наконец обратимся к случаю $c> a$ . В этом случае обозначим $a′ =c$ , $c′ = a$ и построим точно так же четверку $(a′,b′,c′,d′)$ со всеми нужными свойствами, но такую, что, наоборот $a′ ≡rc′$ (mod $p$ ). В этом случае, очевидно, $(b′,a′,d′,c′)$ будет $p − r$ -четверкой, что нам подходит.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#83912

$P$ — некий полином с целыми коэффициентами, $A$ и $M$ — целые числа. Построим последовательность $a n$ , где $a = A 1$ , и $a =P (a) n+1 n$ и пусть $rn$ — остаток от деления $an$ на $M$ .

1. Пусть $P(x)= x2+ x+ 1,A = 1,M = 32022$ . Докажите, что период последовательности $rn$ (то есть, такое наименьшее $t$ , что $rn+t = rn$ при достаточно больших $n$ ) равен 2.

2. Найдите длину предпериода той же последовательности (то есть такое наибольшее $n$ , что $an+t ⁄= an$ , где $t$ — период).

3. Назовем полином стабильным по модулю $M$ , если существует $B$ , такое что для любого $A$ найдется $k$ , для которого $rk = B$ . Докажите, что полином $3 2 f = x − x − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Докажите, что многочлен $P (x)= x2− 3x +12$ стабилен для бесконечного числа натуральных $M$ .

Подсказки к задаче

Пункт 1, подсказка 1

Если мы докажем, что с какого-то момента a_(n+2) - a_n = a_(n+1) - a_(n-1) (mod 3^2022), то и требуемое тоже будет доказано. Попробуйте выразить a_(n+2) - a_n через a_(n+1) и a_(n-1).

Пункт 1, подсказка 2

Мы получаем, что если a_(n+1) - a_(n-1) делится на 3^k, то и a_(n+2) - an делится на 3^k. Теперь, если мы докажем, что a_(n+1) - a_(n-1) делится на 3^(k+1), то сможем сказать, что с какого-то момента k станет >= 2022. Попробуйте для этого доказать, что a_(n+1) и a_(n-1) имеют одинаковые остатки при делении на 3.

Пункт 1, подсказка 3

Для этого посмотрите на значение a_n по mod 3.

Пункт 2, подсказка 1

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

Пункт 2, подсказка 2

Отлично! Теперь мы знаем, что остатки от деления a_n на 9 и на 27 зацикливаются. Тогда, зная, что степень вхождения 3 в выражение a_(n+1) - a_(n-1) каждый раз растёт, попробуйте вывести рекуррентную формулу для этой степени вхождения.

Пункт 2, подсказка 3

Если v_n - степень вхождения 3 в a_(n+1) - a_(n-1), то v_2 = 1, v_3 = 2, v_(2k+1) = v_2k + 2 и v_(2k+2) = v_(2k+1). Теперь осталось лишь решить неравенство v_k < 2022.

Пункт 3, подсказка 1

Нам нужно определить такое B, чтобы для него нашлось A, такой, что ни один r_k не равен B. Сразу сделать это довольно трудно. Попробуйте для начала подставлять небольшие A и посмотреть на значения полинома.

Пункт 3, подсказка 2

Отлично! Мы знаем, что f(2) = 2. Очень удобно будет доказывать, что есть такое A, что не будет остатка 2, ведь M - квадрат нечётного числа. Осталось лишь подобрать такое A и доказать, что r_k никогда не равен 2. Попробуйте найти A так, чтобы в нём как слагаемое присутствовало q (M = q^2).

Пункт 3, подсказка 3

Можно взять A = 2 + k*q (k и q взаимно просты). Теперь попробуйте рассмотреть f(A) по mod M.

Пункт 4, подсказка 1

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

Пункт 4, подсказка 2

Так, теперь мы знаем, что для 7 многочлен стабилен. Тогда попробуем доказать, что это верно и для 7^k. Легче всего сделать это по индукции. База уже есть, осталось доказать переход. И победа!

Показать ответ и решение

1. Легко видеть, что остатки $an$ от деления на 3 чередуются с периодом 2 (1, 0, 1, 0, . . .) поэтому период остатков по модулю $M = 32022$ тем более не равен 1.
Покажем что он равен 2.
Заметим, что $an+2 − an =a2n+1− a2n−1+an+1− an−1 = (an+1− an−1)(an+1+ an−1 +1)$
Отсюда следует, что если $an+1 − an−1$ делится на $3k$ , то тем же свойством обладает и $an+2− an$ , а если вдобавок $an+1$ , $an−1$ дают остаток от 1 деления на 3, то $an+2 − an$ делится на $3k+1$ .
Учитывая, что такая ситуация имеет место при каждом четном $n$ , получаем, что соответствующее $k$ может неограниченно увеличиваться, в частности, $an+2− an$ делится на $32022$ при некотором $n= n0$ (а значит и при всех $n >n0$ ). Поэтому период $rn$ равен двум.

2. Выпишем остатки от деления $an$ на 9 и на 27: легко убедиться, что это 2-периодические последовательности $1,3,4,3,4,...$ и $1,3,13,21,13,21,...$ соответственно.
Поэтому число $(an+1+ an−1+ 1)$ не делится на 3 при нечетных $n$ , делится на 3, но не на 9 при $n= 2$ и делится на 9, но не на 27 при четных $n >2$ .
То есть если $v n$ — степень вхождения 3 в число $a − a n+1 n−1$ , то $v = 1 2$ , $v =2 3$ а дальше $v =v + 2 2k+1 2k$ и $v = v 2k+2 2k+1$ .
Отсюда легко видеть, что наибольшее $s$ такое, что $v <2022 s$ равно 2022, то есть $a − a 2023 2021$ — последняя среди разностей вида $an+2− an$ не кратная $M$ .

3. Пусть $M =Q2$ , тогда $Q$ - нечетное число.
Заметим, что $f(2)= 23− 22− 2= 2$ ,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы не получим 2.
Рассмотрим числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$
$f(t)= (2+ kQ)3 − (2+ kQ )2 − 2= Q3k3+ 5Q2k2+8Qk +2$
Нетрудно заметить, что $f(t)≡ 8Qk + 2(mod M )$
То есть числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$ переходят в себя, но число 2 не имеет такого вида, поэтому полином $f = x3− x2 − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Индукцией по $k$ докажем, что для $M = 7k$ многочлен $x2− 3x+ 12$ стабилен.
Обозначим через $a → b$ , то что $P(a)≡b(modM )$
База $k =1$

0→ 5→ 1 → 31 → 3→ 5→ 12 → 3→ 5→ 13→ 5 → 1→ 34→ 2→ 3→ 5→ 15→ 1 → 36 → 5→ 1→ 3

Таким образом, имеем цикл длины 3 везде одинаковый.
Переход $k→ k+ 1$
Пусть по модулю $M = 7k$ многочлен стабилизируется так, что всегда встретится $r$
Тогда по модулю $M = 7k+1$ остаток $r$ будет $7km+ r= r1$
$P (r1)≡r2− 3r+ 12 +7kn(2r− 3)(Mod 7k+1)$ , что не зависит от $n$ , при $0≡ 2r− 3(Mod 7)$
$0 ≡2r− 3(Mod 7)⇔ 5 ≡r(Mod 7)$ , что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю $7k+1$ .