17-я Международная Жаутыковская олимпиада по математике, 2021 год
Комментарий/решение:
Рассмотрим n=2M такое, что 2M>102021. Пусть r является остатком при этом делении, тогда
v2((3n−1)−(r−1))=v2(3n−r)≥n,
но с другой стороны из LTE очевидно следует, что v2(3n−1)=M+2<n, откуда
v2(r−1)=v2(3n−1)=M+2.
Понятно, что r≠0,1, следовательно
r−1≥2M+2>102021⟹r>102021.◼
Пусть 3n≡rn(mod2n) для всех n∈N
Заметим, что 3⋅102021<21000000000
Утверждение: Найдется такой m≥1000000000, что 3rm≠rm+1.
Док-во: От обратного пусть они равны для всех m≥1000000000.
2m∣3m−rm
2m+1∣3m+1−rm+1⟹2m+1∣3m+1−3rm⟹2m+1∣3m−rm
Делая аналогичным образом, получим, что 3m−rm делится на любое число вида 2m+k, где k∈N, такое невозможно поскольку 3m−rm≠0.
Далее легко выходить, что 3rm≡rm+1(mod2m), откуда одно из 3rm или rm+1 больше 2m, что в свою очередь больше 3⋅102021◼
Замечание: Утверждение можно было и не доказывать а воспользоваться им против самой условий задачи следующим образом,
Если брать от обратного, то 3rm=rm+1 для всех m≥1000000000, тогда rm+k=3krm, для большого k число rm+k очевидно больше 102021.
Заметим, что остаток 3k при делении на 2k не меньше, чем остаток при делении 3k на 2n(k≥n). Рассмотрим такие n, что 2n больше 102021. Предположим, что найдётся такое k, что r, остаток 3k(mod2n), удовлетворяет неравенству 102021<r<2n. Используя вышеприведённый факт, получаем, что остаток от деления 3k на 2k больше 102021.
Если такого k не найдется, это будет означать, что r≤102021, откуда 3k принимает не более 102021, следовательно по принципу Дирихле найдутся k,l, такие что 3k≡3l(mod2n)⇔3k−l≡1(mod2n), следовательно d=ord2n(3k)≤102021 при любом n. Поскольку при увеличении n, показатель, очевидно, неубывает, то с одного момента он станет постоянным. Обозначим это конечное значение за l.
3l≡1(mod2n), что неверно, при 2n>3l.
Скажем
3n=2nbn+an где an<2n (т.е. an− и есть остаток)
Предположим, что существует какой то ac который является максимумом среди всех a. (такой обязательно найдется если a-шки не бесконечно растут). Тогда возьмем какой то d−2>c, и понятно, что 2c>ac>ad;ad+1;...;a2c+d−2. Заметим, что среди чисел ad;ad+1;...;a2c+d−2 повторяются хотя бы две. Потому что из 2c>ac>ad;ad+1;...;a2c+d−2 следует, что 2c−2≥ad;ad+1;...;a2c+d−2 и еще количество чисел ad;ad+1;...;a2c+d−2 будет 2c−1. Тогда пусть повторяются какие то ax=ay (2c+d−2≥x>y≥d). Тогда получим −(2xbx−3x)=ax=ay=−(2yby−3y)⇒2xbx−3x=2yby−3y⇒
2xbx−2yby=3x−3y
Тoгда очевидно, что 2y(2x−ybx−by)=3y(3x−y−1)⇒2y∣3x−y−1.
Но по LTE ν2(3x−y−1)=ν2(2)+ν2(4)+ν2(x−y)−1 (сразу взял когда x−y четный, т.к. когда они нечетные там случай легко отпадает, потому что y≠1).Значит ν2(x−y)+2≥y⇔ν2(x−y)≥y−2⇒2y−2∣x−y.
Значит x−y≥2y−2. Вспомним факты (2c+d−2≥x>y≥d) и d−2>c. Объединив получим, что 2c−2≥x−y≥2y−2≥2d−2>2c ⇒ 2c−2≥2c. Противоречие.
Значит нету такого ac. Тогда a-шки растут бесконечно (необязательно монотонно), и когда нибудь точно обойдут 102021
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.