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

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

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

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

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

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

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

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

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

Задача 1#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,$ что и требовалось доказать.

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

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

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

Задача 2#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}$

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

Задача 3#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⌉.$

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

Задача 4#72736

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

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

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

Подсказка 1

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

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

Если в каком-то ряду наибольший общий делитель равен $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

Курсы

Всё необходимое для достижения цели

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел