Loading [MathJax]/jax/output/SVG/jax.js

17-я Международная Жаутыковская олимпиада по математике, 2021 год


Қандай да бір натурал n саны үшін 3n санын 2n санына бөлгенде, қалдық 102021 санынан үлкен болатынын дәлелдеңіз. ( А. Голованов )
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 3   7
4 года 1 месяца назад #

Рассмотрим n=2M такое, что 2M>102021. Пусть r является остатком при этом делении, тогда

v2((3n1)(r1))=v2(3nr)n,

но с другой стороны из LTE очевидно следует, что v2(3n1)=M+2<n, откуда

v2(r1)=v2(3n1)=M+2.

Понятно, что r0,1, следовательно

r12M+2>102021r>102021.

пред. Правка 2   8
4 года 3 месяца назад #

Пусть 3nrn(mod2n) для всех nN

Заметим, что 3102021<21000000000

Утверждение: Найдется такой m1000000000, что 3rmrm+1.

Док-во: От обратного пусть они равны для всех m1000000000.

2m3mrm

2m+13m+1rm+12m+13m+13rm2m+13mrm

Делая аналогичным образом, получим, что 3mrm делится на любое число вида 2m+k, где kN, такое невозможно поскольку 3mrm0.

Далее легко выходить, что 3rmrm+1(mod2m), откуда одно из 3rm или rm+1 больше 2m, что в свою очередь больше 3102021

Замечание: Утверждение можно было и не доказывать а воспользоваться им против самой условий задачи следующим образом,

Если брать от обратного, то 3rm=rm+1 для всех m1000000000, тогда rm+k=3krm, для большого k число rm+k очевидно больше 102021.

пред. Правка 4   6
2 года 2 месяца назад #

Заметим, что остаток 3k при делении на 2k не меньше, чем остаток при делении 3k на 2n(kn). Рассмотрим такие n, что 2n больше 102021. Предположим, что найдётся такое k, что r, остаток 3k(mod2n), удовлетворяет неравенству 102021<r<2n. Используя вышеприведённый факт, получаем, что остаток от деления 3k на 2k больше 102021.

Если такого k не найдется, это будет означать, что r102021, откуда 3k принимает не более 102021, следовательно по принципу Дирихле найдутся k,l, такие что 3k3l(mod2n)3kl1(mod2n), следовательно d=ord2n(3k)102021 при любом n. Поскольку при увеличении n, показатель, очевидно, неубывает, то с одного момента он станет постоянным. Обозначим это конечное значение за l.

3l1(mod2n), что неверно, при 2n>3l.

пред. Правка 5   0
2 месяца 15 дней назад #

Скажем

3n=2nbn+an где an<2n (т.е. an и есть остаток)

Предположим, что существует какой то ac который является максимумом среди всех a. (такой обязательно найдется если a-шки не бесконечно растут). Тогда возьмем какой то d2>c, и понятно, что 2c>ac>ad;ad+1;...;a2c+d2. Заметим, что среди чисел ad;ad+1;...;a2c+d2 повторяются хотя бы две. Потому что из 2c>ac>ad;ad+1;...;a2c+d2 следует, что 2c2ad;ad+1;...;a2c+d2 и еще количество чисел ad;ad+1;...;a2c+d2 будет 2c1. Тогда пусть повторяются какие то ax=ay (2c+d2x>yd). Тогда получим (2xbx3x)=ax=ay=(2yby3y)2xbx3x=2yby3y

2xbx2yby=3x3y

Тoгда очевидно, что 2y(2xybxby)=3y(3xy1)2y3xy1.

Но по LTE ν2(3xy1)=ν2(2)+ν2(4)+ν2(xy)1 (сразу взял когда xy четный, т.к. когда они нечетные там случай легко отпадает, потому что y1).Значит ν2(xy)+2yν2(xy)y22y2xy.

Значит xy2y2. Вспомним факты (2c+d2x>yd) и d2>c. Объединив получим, что 2c2xy2y22d2>2c  2c22c. Противоречие.

Значит нету такого ac. Тогда a-шки растут бесконечно (необязательно монотонно), и когда нибудь точно обойдут 102021

пред. Правка 3   0
2 месяца 22 дней назад #

Возьмем такие T,S что 2S>3T>102021

Тогда возьмем n=2S+T

По LTE V2(3n3T)=V2(32S1)=S+2 =>> 3n=3T(mod2S+2) но так как n>S+2=>> 3n=rn(mod2n) где rn3T>102021