Тема Иннополис (Innopolis Open)

Теория чисел на Иннополисе

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

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

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

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

Подтемы раздела иннополис (innopolis open)

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

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

Задача 1#119891

Даны целое $a> 0,$ не являющееся целой степенью числа $10,$ и целое $b> 0.$ Верно ли, что существует такое целое $n >0,$ что в десятичной записи числа $n a$ встречается десятичная запись числа $b?$ Например, для $a= 2$ и $b= 19$ можно выбрать $n =13,$ т.к. $13 2 = 8192,$ в записи которого есть $19.$

Источники: Иннополис - 2025, 11.5 (см. lk-dovuz.innopolis.university)

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

Подсказки по 119891:

Подсказка 1:

Подсказка 2:

Иными словами, мы хотим подобрать такие целые положительные m и n, что 10^m • b < a^n < 10^m • (b + 1). Это сразу даст реализацию первой подсказки и решение задачи.

Подсказка 3:

В неравенстве довольно много степеней. Почему бы не прологарифмировать его по основанию 10?

Подсказка 4:

На самом деле это неравенство скрывает более общий факт. Запишем его так: lg(b) < nlg(a) - m < lg(b+1). Кстати, а мы же знаем, что a — не степень 10. Что можно сказать про число lg(a)?

Подсказка 5:

Докажите, что для иррационального x и любого интервала (u, v) найдутся целые положительные m, n такие, что u < nx - m < v.

Подсказка 6:

Попробуйте найти две пары чисел (m, n), чтобы разница между числом, соответствующим первой паре и числом, соответствующим второй паре, была меньше длины отрезка (u, v). Рассмотрите разницу t этих чисел, а также числа 2t, 3t, 4t, ..... Не найдётся ли среди них нужное?

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

Докажем, что для любого целого $a≥ 2$ ( $a⁄= 1= 100)$ и любого целого $b> 0$ найдется целое $n> 0,$ для которого десятичная запись числа $n a$ начинается с последовательно записанных цифр числа $b$ — иными словами, найдутся такие целые положительные $m,n,$ что

m n m 10 ⋅b< a < 10 ⋅(b+ 1)

Прологарифмируем последнее двойное неравенство с основанием $10:$

m + lgb <n ⋅lga< m +lg(b+ 1)

lgb< n⋅lga − m < lg(b+1)

Докажем, что $lga$ иррационально: если это не так, то $lga= pq$ для некоторых целых положительных взаимно простых $p,q,$ тогда $10p = aq,$ что невозможно. Итак, $lga$ иррационально.

Для завершения решения задачи можно доказать, что для любого иррационального $x> 0$ и любого выбранного интервала $(u,v)$ $(0< u< v)$ найдутся такие целые положительные $m,n,$ что

u< nx− m <v

Заметим, что для любого целого $n >0$ можно выбрать такое целое $mn > 0,$ что $0< nx− mn < 1.$ Пусть $k= ⌈v1−u⌉,$ т.е. отрезок $[0,1]$ можно разбить на $k$ равных отрезков, длина каждого из которых будет меньше длины интервала $(u,v).$ Рассмотрим бесконечный набор чисел $x− m1,$ $2x− m2,$ $3x− m3,...$ и выберем из него два числа попадающие в один и тот же из упомянутых $k$ отрезков — пусть это числа $ix− mi$ и $jx− mj$ (без ограничения общности будем считать, что первое меньше второго). Тогда

jx− m − (ix− m )= t∈(0;1∕k) j i

Для найденного $t$ рассмотрим числа $t,2t,3t,...$ — ввиду $t< 1∕k$ среди них найдется число, лежащее на интервале $(u,v),$ что и требовалось доказать.

Осталось заметить, что в условиях нашей задачи $x= lg a$ — иррациональное положительное число; $(u,v)=(lgb,lg(b+ 1))$ — положительный интервал (если $b= 1⇒ lgb= 0,$ то в качестве $u$ можно выбрать любое число из интервала $(0;lg(b+1))).$ Итак, найдутся такие целые положительные $m,n,$ что $lgb< n⋅lga− m < lg(b+ 1),$ т.е. десятичная запись числа $an$ будет начинаться с цифр числа $b.$

Ответ:

Да, верно

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

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

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

Задача 2#126633

Бесконечная последовательность $a ,a,a ,a,... 1 2 3 4$ строится следующим образом: $a = 1$ $a =a = 1, 2 3$ и для $n> 3$

an =an−1⋅an−2+ an−3

Докажите, что для любого целого $d> 0$ найдется член этой последовательности, кратный $d.$

Источники: Иннополис - 2025, 10.3 ( см. lk-dovuz.innopolis.university)

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

Подсказка 1

Так как нас интересует остаток при делении на d, логично попробовать рассмотреть последовательность b₁, b₂, b₃, ..., где b_i — остаток от а_i при делении на d. Что мы знаем об этой последовательности?

Подсказка 2

Мы хотим доказать, что в данной последовательности встретится 0. Мы знаем, что остатки могут принимать только конечное число значений, как это может помочь нам в доказательстве?

Подсказка 3

Так как члены исходной последовательности заданы рекуррентно, мы можем рассмотреть тройки последовательных членов нашей последовательности остатков, сколько всего есть таких троек? А сколько из них может быть различными?

Подсказка 4

Всего таких троек бесконечное число, ведь последовательность имеет бесконечное число членов! Но так как остатки при делении на d ограничены, то и различных троек у нас может быть лишь конечное число. О чем нам это говорит?

Подсказка 5

Тройки чисел будут повторяться! Более того, последовательность будет периодической (ведь по тройке чисел мы можем однозначно восстановить следующую тройку). Дополним нашу последовательность членом b₀ — остатком от а₀ = а₃ - а₁а₂ при делении на d, и учтем, что в силу периодичности последовательности этот остаток встретится вновь.

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

Зафиксируем произвольное целое $d> 0$ и рассмотрим последовательность $b ,b ,b,b,..., 1 2 3 4$ где $b i$ — остаток при делении члена $a i$ исходной последовательности на $d$ для всякого $i= 1,2,3,...$ Требуется доказать, что в последовательности ${bi}i=1,2,3,...$ встретится 0.

Заметим, что количество троек $(bi,bi+1,bi+2)$ бесконечно, при этом по каждой такой тройке можно однозначно определить как предыдущую $(bi−1,bi,bi+1),$ так и следующую тройку в последовательности, при этои количество различных троек конечно $($ их не более чем $3 d ),$ т.е. найдутся различные $i,j,$ для которых

bi = bj; bi+1 = bj+1; bi+2 = bj+2

Из вышесказанного следует, что последовательность ${bi}$ является периодической. Дополняя её элементом $b0,$ т.к. $a0 = a3− a2a1 = 1− 1⋅1= 0≡ 0 (mod d),$ делаем вывод, что $b|i−j| =0$ (для найденных ранее различных $i,j),$ откуда $a|i=j|$ кратно $d,$ что и требовалось доказать.

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

Задача 3#68879

Натуральные числа вида $11 ...1 ◟ ◝◜n-◞$ (десятичная запись состоит из $n$ единиц) будем обозначать $R . n$ Докажите, что существует такое натуральное число $k,$ что $Rn$ делится на 41 тогда и только тогда, когда $n$ делится на $k.$

Источники: Иннополис-2023, 10-12 (см. dovuz.innopolis.university)

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

Подсказка 1

Сложно анализировать число только из единиц, т.к. сложно разобрать даже его делители...тогда было бы по хорошему его как-то преобразовать в более приятный вид. И подумаем над вопросом: "А откуда тут вообще 41? Почему не 42, например?"

Подсказка 2

Число, состоящее из единиц, можно записать как (10^n - 1)/9. А использовать 41 хочется только как простое число... Выходит, что (10^n - 1)/9 должно делиться на 41. Когда это возможно?

Подсказка 3

Когда 10^n - 1 делится на 41. Хмм, 41 простое... Какая известная теорема может помочь нам в нахождении хотя бы одного n, удовлетворяющему предыдущему предложению?

Подсказка 4

Малая теорема Ферма утверждает, что при n = 40 10^40 - 1 делится на 41. Теперь хочется как-то найти k из условия... а на что должно делиться n, чтобы 10^n - 1 делилось на 41? Мы не можем найти все такие случаи, но может попробовать найти хотя бы одного такое k и доказать, что утверждение работает в обе стороны.

Подсказка 5

Рассмотрим все такие d, что 10^d - 1 делится на 41 и выберем среди них наименьшее m. Докажем, что если n делится на m, то 10^n - 1 делится на 10^m - 1, а, значит, и на 41. Если это получится, то у нас найдено k, но условие "тогда и только тогда" пока не доказано. Теперь попробуем доказать, что если 10^n - 1 кратно 41, то n кратно m.

Подсказка 6

Мы взяли m наименьшим, т.к. обычно это помогает в поиске противоречий. Для того чтобы доказать утверждение из подсказки 5, попробуем найти НОД(10^n - 1, 10^m - 1).

Подсказка 7

В процессе поиска c помощью алгоритма Евклида можно заметить, что у нас в конце концов появится 10^(НОД(m, n)) - 1. Предположим, что n не делится на m, тогда НОД(n, m) < m. Осталось лишь найти противоречие с тем, что m - наименьшее взятое число из набора.

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

Заметим, что

10n−-1 Rn = 9

Так как числа $9$ и $41$ взаимно просты, то $Rn$ кратно $41$ тогда и только тогда, когда $n 10 − 1$ кратно $41.$ Поскольку $41$ — простое, согласно малой теореме Ферма

1040− 1 ... 41

Рассмотрим все натуральные $d,$ при которых $10d − 1$ кратно $41;$ наименьшее такое $d$ обозначим за $m.$

Если $n$ делится на $m,$ то

10n− 1= 10tm − 1= (10m − 1)(10(t− 1)m +10(t−2)m + ⋅⋅⋅+10m +1)

Значит, $n 10 − 1$ делится на $m 10 − 1,$ а значит, и на $41,$ что и требовалось.

В обратную сторону: если $n 10 − 1$ кратно $41,$ то рассмотрим $n m НО Д(10 − 1,10 − 1).$ Воспользуемся алгоритмом Евклида, т.е. свойством НОД

НО Д(a,b)= НОД(a− kb,b),где a,b,k∈ ℕ

Теперь

НОД(10n− 1,10m− 1)= НОД(10n− 1− 10n−m(10m− 1),10m− 1)

НОД(10n− 1− 10n+ 10n− m,10m − 1)= НО Д(10n−m − 1,10m− 1)

Повторяя эти действия, убеждаемся, что в конце получается число $НОД(n,m) 10 − 1.$

Если $n$ не делится на $m,$ то

НОД(n,m)< m

Значит, $m$ — не минимальное натуральное число, при котором $m 10 − 1$ кратно $41$ — противоречие. Значит, $n$ кратно $m,$ что и требовалось доказать.

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

Задача 4#68880

Пусть $a,b,c$ — взаимно простые в совокупности натуральные числа, и

( 2 2 2 n n n) Dn = a+ b+ c,a + b+ c ,a + b + c

Найдите все возможные значения $D , n$ где $n−$ натуральное число, кратное 3. Запись $(a,a ,a,...,a ) 1 2 3 k$ обозначает наибольший общий делитель целых чисел $a ,a,a ,...,a . 1 2 3 k$ Целые числа $a ,a,a ,...,a 1 2 3 k$ называются взаимно простыми в совокупности, если $(a ,a,a ,...,a )= 1. 1 2 3 k$

Источники: Иннополис-2023 (см. dovuz.innopolis.university)

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

Подсказка 1

А давайте для начала попробуем ручками проверить различные a, b, c - чтобы понять, каким вообще может быть D.

Подсказка 2

Пупупу… а теперь посмотрим внимательно на условие. Каким свойством обладают скобки вида: (aⁿ + bⁿ + cⁿ)?

Подсказка 3

Да, эти скобки симметричны! Если поменять какие-то две переменные местами, то выражение не изменится. А теперь, учитывая, что мы получили какие-то значения D - попробуйте перейти к симметрическим многочленам. К какому противоречию мы придём?

Подсказка 4

Верно, мы придём к тому, что существует какое-то просто p, которое делит произведение abc. Теперь нужно аккуратно доказать, что в таком случае простое p делит каждое из чисел a, b, c! Тогда, мы докажем, что возможны только D = {1, 2, 3, 6}.

Подсказка 5

Остаётся только привести пример чисел a, b, c для каждого возможного D!

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

Пусть $σ,σ ,σ 1 2 3$ — элементарные симметрические многочлены и $n n n sn = a + b + c.$ Воспользуемся формулой Ньютона

sk = σ1sk−1− σ2sk−2+ σ3sk−3

Докажем, что $D ∈ {1,2,3,6}. n$ Предположим, что существуют такие взаимно простые в совокупности $a,b,c$ , что $D n$ отличен от $1,2,3,6.$ Докажем, что тогда $σ ,σ,σ 1 2 3$ имеют общий делитель, больший 1. В самом деле, из формул Ньютона следует, что при разложении $s n$ через $σ ,σ ,σ 1 2 3$ моном, не содержащий $σ 1$ и $σ, 2$ с точностью до знака имеет вид $3σ n3. 3$ Поэтому если $D n$ делит $s = σ 1 1$ и $D n$ делит $2 s2 = σ1 − 2σ2,$ то $Dn$ делит $σ1,2σ2,3σ3.$

При $Dn,$ отличном от $1,2,3,6$ у чисел $σ1,σ2,σ3$ есть общий делитель, больший 1. Пусть $p$ — простой множитель, входящий в этот делитель. Тогда $p$ делит $abc,$ откуда (без ограничения общности) $p$ делит a. Но тогда $p$ делит $(ab+ bc+ ca)$ и $p$ делит $bc,$ т.е. (без ограничения общности) $p$ делит $b.$ Наконец, из того, что $p$ делит $(a+b+ c),$ получаем, что $p$ делит $c.$ Значит, $(a,b,c)≥ p,$ но по условию $(a,b,c)= 1$ — противоречие.

Итак, $Dn ∈ {1,2,3,6}.$ Набор $(1,1,2)$ реализует $Dn = 2,$ набор $(1,1,1)$ — $Dn = 3,$ набор $(1,4,7)$ — $Dn = 6.$ Для $Dn = 1$ возьмем простое число $p >3$ и положим $a =b =1, c =p− 2.$ Тогда $a+ b+c =p$ и $p$ не делит $2 2 2 2 a +b + c =p − 4p+ 6,$ откуда $Dn = 1.$

Ответ:

${1,2,3,6}$

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

Задача 5#74914

Назовём бесконечную числовую последовательность ${a } n$ стабилизирующейся, если при некотором $k 0$ для всех $k ≥k 0$ выполнено $ak = ak+1.$ Тогда $k0$ назовем временем стабилизации, $ak$ $($ при $k≥ k0)$ — стабильным значением.

Пусть $a,b$ — натуральные числа. Дана последовательность ${xn},$ в которой $x1 = x2 = x3 = a$ и для любого натурального $n$ выполнены равенства

x3n+1 = b⋅x3n−2,x3n+2 = x3n−1∘b

$($ здесь $∘b$ — это операция взятия целой части при делении на $b)$ и

x3n+3 =x3n+ x3n−2 ⋅(x3n− 1(modb))

$($ здесь $(modb)$ — операция взятия остатка от деления на $b).$

Какие из последовательностей ${x3n+1},{x3n+2},{x3n}(n∈ ℕ)$ стабилизируются, и чему равны их стабильные значения? Чему равно время стабилизации последовательности ${x3n}?$

Источники: Иннополис-2022 (см. dovuz.innopolis.university)

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

Подсказка 1

Давайте посмотрим, что нам известно из условия? Получается, основная последовательность {Xn} разделяется на три подпоследовательности. Причём первые две, похоже, зависят только от тех элементов основной последовательности, что входят в эту подпоследовательность. Может, для начала рассмотрим их повнимательнее?

Подсказка 2

Верно, мы можем выразить элементы этой последовательности через a, b и n. Третья же подпоследовательность зависит от элементов из других подпоследовательностей, так что здесь так просто не получится расписать. Тогда стоит попробовать выразить x{3n+3} с помощью x{3n+1} и x{3n+2}. Например, записать какое-нибудь равенство с этими тремя переменными.

Подсказка 3

Для составления такого уравнения очень полезно начать с расписывания первых элементов и постепенно находить отношения, которые остаются неизменными. А затем доказать их по индукции

Подсказка 4

Остаётся только проанализировать, при каких значениях b каждая из подпоследовательностей стабилизируется и на каком стабильном значении

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

Сначала рассмотрим последовательность ${x }. 3n+1$ По ее определению имеем $x = a⋅bn 3n+1$ для всех целых $n ≥0$ — значит, при $b= 1$ ее стабильное значение равно $a,$ а при $b >1$ она не стабилизируется.

Теперь рассмотрим ${x3n+2}.$ По определению, если $b= 1,$ то $x3n+2 =a$ для всех целых $n≥ 0,$ а если $b> 1,$ то $-a x3n+2 ≤ bn$ и, поскольку последовательность — целочисленная, имеем $x3n+2 =0$ для всех $n,$ начиная с $⌈logba⌉$ (целая часть от логарифма, взятая с избытком).

Докажем по индукции, что

x3n+1⋅x3n+2+ x3n+3 =a2+ a

для всех целых $n ≥ 0.$

База индукции $(n= 0):$

2 x1⋅x2+ x3 =a + a

по определению.

Индукционная гипотеза: пусть для некоторого $m ≥0$ выполнено

2 x3m+1 ⋅x3m+2+ x3m+3 = a + a

Тогда

x ⋅x +x = (b⋅x3m+1)⋅(x3m+2 ∘b)+ 3(m+1)+1 3(m+1)+2 3(m+1)+3

+(x3m+3+ x3m+1 (x3m+2(modb)))= ((b⋅x3m+1)⋅(x3m+2 ∘b)+

2 x3m+1 (x3m+2(modb)))+ x3m+3 =x3m+1 ⋅x3m+2+ x3m+3 = a + a

Что и требовалось доказать.

Наконец, рассмотрим последовательность ${x3n}$ . В силу доказанного выше, если $b=1$ , то все члены последовательности ${x3n}$ равны $a$ , а если $b> 1$ , то

x = x ⋅0+ x =x ⋅x +x = a2+a, 3n+3 3n+1 3n+3 3n+1 3n+2 3n+3

начиная с $n = ⌈logba⌉,$ следовательно, стабильное значение последовательности ${x3n}$ равно $a2+a.$

Ответ:

Последовательность ${x } 3n+1$ стабилизируется на $a$ при $b =1;$ ${x } 3n+2$ стабилизируется на $a$ при $b= 1$ и на $0$ при $b> 1;$ ${x } 3n$ стабилизируется на $a$ при $b= 1,$ начиная с $n= 1,$ и на $2 a + a$ при $b> 1,$ начиная с $n = ⌈logba⌉.$

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

Задача 6#72736

В таблице $4× 4$ расставлены $16$ различных натуральных чисел. Для каждой строки и каждого столбца таблицы нашли наибольший общий делитель расположенных в нем чисел. Оказалось, что все найденные восемь чисел различны. Для какого наибольшего $n$ можно утверждать, что в такой таблице найдется число не меньше $n?$

Источники: Иннополис-2018

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

Подсказка 1

Давайте для начала удобно переформулируем условие задачи. Если все НОДы различные, то какое наименьшее значение оно может принимать?

Подсказка 2

Верно, так как столбцов и строк в сумме 8, то и наименьшее значение НОДа равно 8. Давайте теперь посмотрим на одну строку или столбец, и пусть НОД чисел равен d. Тогда какое наименьшее число может быть в этой строке?

Подсказка 3

Ага, так как все числа различны, то и наименьшее число будет хотя бы 4d. Тогда совмещая эти два условия, находим, какое в принципе наименьшее число возможно на доске. Это 32. Теперь вспомним, что различные числа у нас расставляются произвольно. Поэтому осталось только придумать пример, в котором все числа будут не больше 32. То есть это будет вашим контрпримером, что больше 32 число взять нельзя. Победа!

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

Если в каком-то ряду наибольший общий делитель равен $n,$ то в нем есть четыре числа, делящихся на $n,$ a, значит, число, не меньшее, чем $4n.$ Поскольку наибольшие общие делители во всех рядах различны, один из них заведомо не меньше $8.$ Тогда в соответствующем ему ряду должно быть число, не меньшее $32.$ Приведем теперь пример таблицы, в которой все числа не больше $32.$ Наибольшие общие делители по строкам равны $5,6,7$ и $8,$ а по столбцам равны $1,2,3$ и $4.$


5	10	15	20

30	6	18	12

7	14	21	28

8	16	24	32

Замечание. Наибольшие общие делители заведомо должны быть числами от $1$ до $8,$ а ряды с НОДами $6,7$ и $8$ должны быть составлены из тех чисел, которые стоят в соответствующих рядах в таблице из примера (возможно в другом порядке).

Ответ: 32