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

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

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

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

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

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

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

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

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

Задача 1#68879

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

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

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

Заметим, что

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 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)

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

Сначала рассмотрим последовательность ${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

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

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