Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Метод спуска, индукция и последовательное конструирование в ТЧ

Тема ТЕОРИЯ ЧИСЕЛ

Метод спуска, индукция и последовательное конструирование в ТЧ

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

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

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

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

Подтемы раздела теория чисел

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

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

Задача 21#137742Максимум баллов за задание: 7

Докажите, что натуральное число, цифры которого идут в строго убывающем порядке, не может делиться на $111.$

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

Подсказка 1:

Сделаем интересное наблюдение. Если из числа, подходящего под условие, вычесть 111, то новое число тоже будет подходить под условие, если при вычитании не было переноса в младший разряд.

Подсказка 2:

В каком случае будет перенос? Что можно сделать в этой ситуации?

Подсказка 3:

Он будет только, если изначальное число заканчивалось на 10. Но ведь тогда вместо вычитания 111 можно поделить это число на 10, и оно по-прежнему будет подходить под условие. Какой вывод можно сделать из этих подсказок?

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

Предположим, что найдется число, делящееся на 111, цифры которого идут в строго убывающем порядке. Рассмотрим среди таких чисел наименьшее число $x.$ Ясно, что $x$ хотя бы трёхзначное. Если $x$ оканчивается на 0, то рассмотрим $x- 10,$ делимость сохранилась, а цифры всё ещё идут в порядке убывания — противоречие. Если же $x$ оканчивается не на 0, то рассмотрим $x− 111.$ Поскольку цифры шли в порядке убывания, переходов через разряд не случилось, убывание сохранилось, а число уменьшилось, вновь получаем противоречие. Значит, таких чисел нет, что и требовалось доказать.

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

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

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

Задача 22#137749Максимум баллов за задание: 7

Найдите все последовательности натуральных чисел $a ,a ,... 1 2$ такие, что для любого натурального $n$ выполнено равенство

2 (n + 1)an =n(an2 + 1).

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

Подсказка 1:

Какие наблюдения можно сделать, глядя на равенство из условия? Например, aₙ точно делится на n, потому что (n, n² + 1) = 1.

Подсказка 2:

Кстати, нетрудно заметить, что последовательность aₙ = n подходит. Попробуйте доказать, что это единственный ответ.

Подсказка 3:

Вместо того чтобы доказывать, что aₙ = n, можно ввести другую последовательность bₙ, зависящую от членов a. Для удобства можно подобрать такую bₙ, которая равна константе, если aₙ = n.

Подсказка 4:

Можно взять bₙ = (aₙ / n) – 1. То есть мы хотим доказать, что bₙ = 0. Какой вид примет рекуррентное соотношение?

Подсказка 5:

Обратите внимание, n² + 1 взаимно просто с n. На какую максимальную степень n делится bₙ?

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

Поскольку $(n2 +1,n)=1,$ $a n$ делится на $n.$ Тогда пусть $b = an− 1. n n$ Выражение из условия переписывается в следующем виде:

2 ( 2 ) (n + 1)n(bn +1)= n n (bn2 + 1)+1

2 2 bn(n + 1)= bn2n

Подставляя $n= 1,$ получаем $b1 = 0.$ Теперь пусть $n >1.$ Заметим, что $bn$ делится на $n2,$ тогда $b2 n$ делится на $n4,$ то есть $bn$ делится на $n6.$ Продолжая рассуждения, получаем, что $bn$ делится на сколь угодно большую степень $n.$ Тогда $bn = 0,$ то есть $an =n.$

Ответ:

$a =n n$

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

Задача 23#137751Максимум баллов за задание: 7

Числа вида $n2+ n+ 1,$ где $n$ натуральное, назовём странными. Докажите, что бесконечно много странных чисел являются произведением странных, и бесконечно много странных чисел таковыми не являются.

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

Подсказка 1:

Чтобы найти бесконечное количество странных чисел, представимых в виде произведения странных, попробуйте поперемножать какие-нибудь странные числа.

Подсказка 2:

Например, что будет, если перемножить n – 1 и n странное число?

Подсказка 3:

Чтобы доказать второе утверждение, стоит пойти от противного. Предположим, есть конечное число чисел, непредставимых в виде произведения странных. На самом деле здесь идея примерно такая же, как при доказательстве того, что простых чисел бесконечно много.

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

Пусть $s n$ — $n−$ ое странное число. Тогда покажем, что $s =s s : n2 n n−1$

4 2 2 2 n +n + 1= (n +n +1)(n − n+ 1)

Выходит, что странное число с номером $n2$ при любом $n$ является произведением странных. Следовательно, странных чисел, представимых в виде произведения странных, бесконечно много.

Предположим, что чисел, не представляющихся в виде произведения странных, конечно, и обозначим их за $k ,...,k . 1 n$ Пусть $S =k ...k. 1 n$ Тогда рассмотрим $S−$ ое странное число. Оно должно представляться в виде произведения странных, поскольку больше, чем все $k. i$ Но оно взаимно просто со всеми $k, i$ так что в разложении $S$ на странные вновь все числа представляются в виде произведения странных. Бесконечно спускаться мы не можем, поэтому когда-нибудь найдётся число, не представимое в виде произведения странных, причём оно взаимно просто со всеми $ki,$ противоречие.

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

Задача 24#137759Максимум баллов за задание: 7

Найдите все натуральные $n$ такие, что при всех $k= 0,1,2,4,8,...,$ меньших $n,$ число $2n − k$ делится на $n − k.$

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

Подсказка 1:

Давайте вспомним полезную лемму: (2ᵃ – 1, 2ᵇ – 1) = 2ᵐ – 1, где m = (a, b). Докажите её.

Подсказка 2:

Если взять k = 0, станет ясно, что n — степень двойки.

Подсказка 3:

Если представить n как 2ˣ, а k как 2ʸ, становится ясно, как применить лемму из первой подсказки. Делимость из условия влечёт делимость 2ˣ – y на x – y. Вам не кажется, что для y можно проделать аналогичные рассуждения?

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

При $k= 0$ получаем, что $2n$ делится на $n.$ Значит, $n$ — это степень двойки. Пусть $n= 2x.$ Тогда $22x − 2y$ делится на $2x− 2y.$ Обозначим за $Ek$ число $k 2 − 1$ (в двоичной системе счисления это $k$ единичек). Покажем, что $(En,Ek)= E(n,k).$ Для этого докажем, что при $n≥ k$

(En,Ek)= (En−k,Ek)

Действительно, $E − E = E ⋅2k n k n−k$ и

k (En,Ek)= (En−k⋅2 ,Ek)= (En−k,Ek)

Значит, можно применить алгоритм Евклида для индексов, что и хотели получить. Тогда из делимости $22x − 2y$ на $2x− 2y$ следует, что $2x− y$ делится на $x− y$ для всех целых неотрицательных $y < x.$ Заметим, что мы получили даже более сильное утверждение, чем в условии, так что можно аналогично получить $x= 2z$ и так далее. Тогда все подходящие $n$ имеют вид башенки из степеней двоек: $222....$ Башенки высоты 0, 1, 2, 3 подходят $(n =1,2,4,16).$ Для башенки высоты 4 $(x = 24)$ можно подставить $y = 5.$ Тогда $216− 5$ не делится на $24− 5= 11.$ Но по такой логике для любой более высокой башенки мы сможем спуститься до высоты 4 и получить там противоречие. Значит, они тоже не подходят.

Ответ:

1, 2, 4, 16

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

Задача 25#138245Максимум баллов за задание: 7

Решите в целых числах уравнение $x2 +y2+ z2 = 2xyz.$

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

Заметим, что тройка $(0,0,0)$ является решением. Пусть есть ненулевое решение $(x,y,z).$ Тогда одна из переменных обязательно чётная, так что правая часть делится на 4. Нечётные квадраты по модулю 4 дают остаток 1, так что и две другие переменные должны быть чётными. Тогда пусть $x= 2x1,$ $y = 2y1,$ $z = 2z1.$ Исходное равенство переписывается в виде

2 2 2 x1+ y1 +z1 = 4x1y1z1

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

Ответ:

$(0,0,0)$

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

Задача 26#138246Максимум баллов за задание: 7

Дано натуральное число $m.$ Известно, что для некоторого натурального $n$ число $2n⋅m$ преставимо в виде суммы квадратов двух целых чисел. Докажите, что тогда и $m$ преставимо в таком виде.

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

Пусть $2m = x2+y2.$ Тогда $x$ и $y$ одной чётности, поэтому $a= x+y 2$ и $b= x−y 2$ целые. Тогда $m = a2 +b2,$ то есть мы можем получить представление для числа вдвое меньше. Таким образом, мы можем сделать спуск по $n$ и получить требуемое представления для числа $m,$ что и требовалось доказать.

Курсы

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

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

Задача 27#138247Максимум баллов за задание: 7

(a) Имеется 101 корова, каждая весит целое число грамм. Известно, что любые 100 коров можно разбить на 2 стада одинакового веса, по 50 коров в каждом. Докажите, что все коровы весят одинаково.

(b) А если веса коров рациональны?

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

(a) Заметим, что к весу всех коров можно добавить одно и то же число, тогда задача не изменится. Тогда можно считать, что самая лёгкая корова имеет вес 0. Предположим, что существует корова веса $x> 0.$ Тогда пусть общий вес всех коров $S.$ Числа $S$ и $S− x$ чётные, поскольку после выкидывания коров нулевого веса и веса $x$ оставшиеся коровы должны поделиться на группы равного веса. Тогда $x$ чётно. Аналогично можно получить, что веса всех коров чётны. Тогда разделим их на 2, получим аналогичную задачу. Бесконечно делить на 2 мы не можем, поэтому все коровы имеют одинаковый вес.

(b) Домножим веса всех коров на общий знаменатель. Тогда получим условие пункта (a), так что снова все коровы весят одинаково.

Ответ:

(b) коровы весят одинаково

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

Задача 28#138248Максимум баллов за задание: 7

Существуют ли такие целые числа $x,$ $y$ и $z$ такие, что числа $x+ 2y+ 3z,$ $x +3y+ 5z$ и $3x +4y+ 5z$ — кубы натуральных чисел?

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

Предположим, что такое возможно. Тогда пусть наши кубы — это $a3,b3,c3:$

(| 3 ||{x+ 2y+3z =a ||x+ 3y+5z =b3 |(3x+ 4y +5z = c3

Заметим, что $5a3 =c3+ 2b3.$ Покажем, что у такого уравнения нет решений в целых числах. Для этого рассмотрим его по модулю 9. Если $a$ не делится на 3, то $5a3 ≡ ±5 (mod 9),$ а в правой части $c3$ даёт остатки $0,−1,1,$ $2b3$ даёт остатки $0,−2,2,$ откуда $±5$ получится не может. Значит, $a$ кратно трём. Если $c$ не делится на 3, то в сумме с $2b3$ число, кратное девяти, получиться не может. Значит, $c$ делится на 3. Тогда и $b$ также делится на 3. Тогда уравнение можно сократить на 27 и получить точно такое же. Бесконечно так продолжаться не может, значит, единственное решение — это $(0,0,0).$ Нас интересуют натуральные числа, поэтому таких $x,y,z$ не существует.

Ответ:

нет

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

Задача 29#138249Максимум баллов за задание: 7

Найдите все пары целых чисел $a$ и $b,$ для которых

18 18 18 (19a+ b) +(a+ 19b) +(a+ b)

является квадратом целого числа.

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

Пусть

18 18 18 2 (19a+ b) +(a+ 19b) +(a+ b) = x

Рассмотрим выражение по модулю 19:

18 18 18 18 18 18 (19a+ b) + (a +19b) + (a +b) ≡ a +b + (a+ b) (mod 19)

Заметим, что по малой теореме Ферма это выражение даёт остатки 0, 2 или 3 по модулю 19. Остаток 1 невозможен, поскольку из делимости двух чисел на 19 следует и делимость третьего. Переберём остатки по модулю 19 и поймём, что остатки 2 и 3 квадраты давать не могут, поэтому $a$ и $b$ делятся на 19:


$x$	$x2$	$x2 mod 19$	$x$	$x2$	$x2 mod 19$

0	0	0	10	100	5
1	1	1	11	121	7
2	4	4	12	144	11
3	9	9	13	169	17
4	16	16	14	196	6
5	25	6	15	225	16
6	36	17	16	256	9
7	49	11	17	289	4
8	64	7	18	324	1
9	81	5

Таким образом, можно вынести $1918$ и сократить, получив такое же уравнение. Бесконечно так продолжаться не может, значит, единственное решение нулевое.

Ответ:

$(0,0,0)$

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

Задача 30#77056Максимум баллов за задание: 7

Дано выражение $a xn+ a xn−1+...+a x+ a + a1-+...+ an−1+ an n n−1 1 0 x xn−1 xn$ с вещественными коэффициентами $a. i$

(a) Докажите, что его можно представить в виде $1 P (x+ x),$ где $P(x)$ — некоторый многочлен c вещественными коэффициентами.

(b) Докажите, что если коэффициенты $ai$ — целые, то в качестве $P(x)$ может быть взят многочлен с целыми коэффициентами.

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

Подсказка 1

Давайте действовать по индукции по n. Для начала докажите утверждение задачи для n = 1.

Подсказка 2

Теперь будем делать переход. Какие слагаемые нам достаточно свернуть в многочлен от x + 1/x , если один раз воспользоваться индукционным предположением?

Подсказка 3

Правильно! Достаточно свернуть в многочлен от x + 1/x слагаемые a_n * xⁿ + a_n /xⁿ. Для начала давайте попробуем разобраться с нечетным n. Для этого надо придумать разложение на множители этого выражения. Какое?

Подсказка 4

На самом деле a_n * xⁿ + a_n /xⁿ = a_n (x + 1/x)(xⁿ⁻¹ - xⁿ⁻³ + ... - 1/ xⁿ⁻³ + 1/xⁿ⁻¹). А что же можно сказать про третью скобочку?

Подсказка 5

Верно! Она является многочленом от x + 1/x по предположению, а, значит, для нечетного n разобрались. Попробуем теперь для четного. С четным немного проще. Достаточно дополнить до квадрата некоторого выражения.

Подсказка 6

Для этого попробуйте вычесть и прибавить 2a_{2k}, где n = 2k.

Подсказка 7

Для пункта (b) попробуйте просто немного изменить индукцию.

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

(a) Будем доказывать индукцией по числу $n.$

Проверим базу. При $n =1$ выражение имеет вид $a ( ) a1x+ a0+ x1= a1 x1 +x11 +a0$ — это многочлен нужного вида.

Пусть для любого набора $a0,a1,...,an−1$ и некоторого числа $n− 1$ утверждение задачи верно. Докажем, что оно верно и для числа $n$ с любым набором $a0,a1,...,an.$

По индуктивному предположению имеем:

( ) anxn +an−1xn−1+ ...+a1x+ a0+ a1+ ...+ ann−−11 + ann = Q x+ 1 +anxn+ ann x x x x x

Осталось доказать, что $anxn + axnn$ представим в виде многочлена от $x+ 1x.$ Рассмотрим $2$ случая:

1.

Пусть $n$ — нечетное число. Тогда получаем

an ( 1)( 1 1 ) anxn+ xn = an x + x xn−1− xn−3+ ...− xn−3 + xn−1

По индуктивному предположению получаем:

an ( 1) ( 1) anxn+ xn = an x+ x Q1 x+ x

Это тоже многочлен вида $P (x +-1) . x$ Очевидно, сумма многочленов такого вида есть многочлен такого вида.

2.

Пусть $n$ — четное число. Тогда преобразуем выражение следующим образом (пусть $n= 2k$ ):

2k a2k (( k)2 k 1- ( 1-)2) ( k -1 )2 a2kx +x2k =a2k x + 2x xk + xk − 2a2k = a2k x +xk − 2a2k

По индуктивному предположению $xk + 1-= P(x+ 1). xk x$ Тогда его квадрат — тоже многочлен такого вида.

(b) Для решения этого пункта достаточно усилить индуктивное предположение и допустить, что если изначально все коэффициенты были целыми, то в итоге многочлен $P (x+ 1) x$ будет иметь целые коэффициенты.

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

Задача 31#77252Максимум баллов за задание: 7

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

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

Предположим, что нашлись такие натуральные $n,a ⁄=b,$ что

2 2 n a + b =2

Сумма должна быть чётной, поэтому слагаемые в левой части должны быть одинаковой чётности.

Если оба числа в левой части нечётные, $a= 2x+ 1,b= 2y+ 1,$ то левая часть $a2+b2 = 4(x2+ x+ y2+ y)+ 2$ не делится на 4. Но так как $a2+ b2 ≥ 12 +22 > 4,$ то $n> 2,$ значит, правая часть делится на 4.

Значит, оба числа в левой части чётные $a= 2x,b= 2y,$ получаем

2 2 k x +y = 2 ,

где $k =n − 2 ∈ℕ$ и в силу $a⁄= b$ так же $x ⁄= y ∈ℕ.$ Пришли к той же задаче. Продолжая рассуждения, приходим к противоречию с тем, что натуральное число (показатель степени двойки в правой части) не может уменьшаться на 2 бесконечное число раз.

Ответ: нет

Интенсивы

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

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

Задача 32#79612Максимум баллов за задание: 7

Можно ли утверждать, что если для рациональных чисел $a,b,c$ сумма

√- √- √- a 2 +b 3+ c 6

является рациональным числом, то $a= b=c =0?$

Источники: БИБН - 2024, 11.4 (см. www.unn.ru)

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

Подсказка 1

Давайте предположим, что это возможно, и обозначим нашу сумму за p. Первое, что бросается в глаза, это то, что √2*√3=√6, поэтому хочется отправить с√6 направо и возвести в квадрат. После возведения в квадрат из иррациональных чисел остается только √6, значит можно его выразить через остальные рациональные...

Подсказка 2

После преобразований мы получаем, что √6=(6c²+p²-2a²-3b²)/(2ab+2pc). Казалось бы победа, мы получили выражение иррационального числа через рациональные, что невозможно. Но ведь мы могли поделить на 0. Что делать, если 2ab+2pc=0?

Подсказка 3

Если ab+pc=0, то 6c²+p²=2a²+3b². Рассмотрим случай с≠0: подставим p=-ab/c в равенство 6c²+p²=2a²+3b². После тождественных преобразований получаем (3с²-a²)(2c²-b²)=0. Найдите здесь противоречие и рассмотрите случай с=0!

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

Обозначим $a√2+ b√3+ c√6= p∈ ℚ.$

Тогда $√ - √ - √- a 2+b 3=p − c 6$ . Возведем в квадрат

2 2 √- 2 2 √ - 2a + 3b +2ab 6= p + 6c − 2pc 6

В случае $a= 0$ или $b= 0$ получаем, что левая часть равенства рациональна, а значит и правая тоже, то есть $p= 0$ или $c= 0$ . Если имеет место случай $c= 0$ , то $a =b= c= 0.$

В случае же $p =0$ (не умаляя общности $a =0$ ) получаем

√- √- b 3+ c 6= 0

b+ c√2= 0

И так как $b∈Q$ , равенство возможно только в случае $c =0$ . И тогда также $b= 0.$ То есть если $a =0$ или $b= 0$ , то требуемое верно.

Пусть теперь $a,b⁄= 0$ . Преобразуем:

2 2 2 2 √ - 2a + 3b − p − 6c= − 6(2ab+ 2pc)

Равенство возможно только в случае, если справа рациональное число, то есть $ab= −pc$ . Тогда получаем следующую систему

{ 2a2+ 3b2 = p2+ 6c2 6a2b2 = 6p2c2

Эта система имеет вид

{ x+ y = z+ t=s xy = zt=q

По следствию теоремы Виета $x,y$ и $z,t$ являются корнями уравнения $n2 − sn+ q = 0$ . Но у квадратного уравнения максимум $2$ корня, поэтому либо $x= z$ и $y = t$ , либо $x= z$ и $y = z$ .

В первом случае получаем $2a2 = p2$ , что невозможно, кроме разобранного случая $a= p= 0.$

Во втором случае $2a2 = 6c2$ , также невозможно, если $a,c⁄= 0.$

Ответ: да

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

Задача 33#80738Максимум баллов за задание: 7

Можно ли число 2024 представить в виде $a5+b3$ , где $a$ и $b$ — натуральные числа?

Источники: Высшая проба - 2024, 11.1 (см. olymp.hse.ru)

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

Подсказка 1

Если a ≥ 5, то левая часть уже слишком большая. Остаётся перебрать четыре значения для а и проверить, чему равно b

Подсказка 2

Должен найтись подходящий вариант!

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

3 10 5 3 2024 =1000+ 1024= 10 +2 = 4 +10

Ответ: да

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

Задача 34#82677Максимум баллов за задание: 7

Дана последовательность $a n$ : 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, $...$
(одна единица, две двойки, три тройки, четыре четверки и т.д.) и еще одна последовательность $bn$ такая, что $abn =ban$ для всех натуральных $n$ .

Известно, что $bk = 1$ при некотором $k> 100$ . Докажите, что $bm =1$ при всех $m >k$ .

Источники: СПБГОР - 2024, 11.2 (см. www.pdmi.ras.ru)

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

Подсказка 1

Для начала давайте поймем что-то про последовательность {a_i}. Как минимум поймем на каких местах у нас стоит число k. Это важно для нас, так как если мы хотим выбрать какое-то конкретное m(и посмотреть откуда же может быть получено противоречие), то нам надо понимать, как связан номер и значение a_m. Как зависит значение от m?

Подсказка 2

Для любых номеров m, которые располагаются между t(t + 1)/2 + 1 и (t + 1)(t + 2)/2, a_m = t + 1. Если от нас требуется доказать, что начиная с какого-то номера у нас b_i = 1, не будем мелочиться и докажем, начиная почти для всех(с какого-то маленького), по индукции. Но давайте, для начала, так сказать, для создания благоприятной обстановки, поймем, как все таки делать индукцию. Ведь переход от n к n + 1 здесь кажется странным. Однако переход от k(k + 1)/2 к (k + 1)(k + 2)/2 выглядит более разумно, ведь мы знаем все значения a_i, для i из этого отрезка.

Подсказка 3

Верно, переход такой нам легко дается, так как a_i из этого промежутка равно t + 1, а значит, это b_(t + 1), но для всех меньших мы доказали. Что осталось написать по этой задаче? Является ли это полным решением?

Подсказка 4

Не является, так как t + 1 не всегда входят в уже доказанный промежуток. Для t = 1, 2 - это неверно. Значит, надо в качестве базы использовать t >= 3. Но это подходит под условие нашей задачи, а значит, если у нас b_k = 1, то и все последующие будут равны 1.

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

Возьмём число $m : t(t+1)+ 1≤ m ≤ (t+1)(t+2) 2 2$ , заметим, что для любого такого $m$ $a = t+1 m$ , тогда $b = b = a t+1 am bm$ , тогда если $bm =1$ , то $abm =1$ , тогда $bt+1 =1$ , и наоборот.

Значит, $bt+1 = 1 ⇐⇒ bm = 1$ для $t(t+1) (t+1)(t+2) m ∈ [ 2 + 1; 2 ]$

Значит, и $bt+1 ⁄=1 ⇐⇒ bm ⁄= 1$

Если $b3 =1$ , то

2× 3 3× 4 ∀m ∈ [-2-+ 1;-2--]:bm = 1 т.е. b4 = b5 =b6 = 1

Докажем тогда по индукции, что $∀m > 3 bm = 1.$

База уже есть. Переход будем делать от $m ∈ [3;t(t+21)]$ к $m ∈[3;(t+1)2(t+2)].$

Заметим, что $t+ 1< t(t+21)$ при $t>3 ⇒ bt+1 = 1$ , но по предположению индукции $∀m ∈ [t(t+21)+ 1≤ m≤ (t+1)2(t+2)]:bm =1$ , значит,

∀m ≥3 :bm = 1, если b3 = 1

Аналогичными рассуждениями

∀m ≥3 :bm ⁄= 1, если b3 ⁄= 1

Итого т.к. $bk =1$ , $k> 100$ , то $b3 =1$ , а значит, $∀m > 3$ :

bm = 1⇒ ∀m > k bm =1

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

Задача 35#83138Максимум баллов за задание: 7

Малая теорема Ферма. Для любого простого $p$ и взаимно простого с $p$ числа $a$ верно, что $ap−1 ≡ 1$ (mod $p$ )

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

Подсказка 1

Попробуем доказать по индукции, что a^p − a делится на р. База a=1 очевидна. Как сделать переход от а к а+1?

Подсказка 2

Что мы можем сказать про делимость на p для биномиальных коэффициентов в выражении (а+1)^p?

Подсказка 3

p!/(k!(p-k)!) делится на р для всех k кроме 0 и р, поскольку числитель делится на р, а знаменатель - нет. Что тогда останется, если смотреть на выражение по модулю p?

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

Первое решение.

Давайте возьмем две разные ПрСВ по одному модулю $p$ и перемножим в каждой все числа. Так как наборы остатков одинаковые, то получившиеся произведения будут сравнимы по модулю $p$ .

Тогда рассмотрим две такие ПрСВ: [1, 2, ..., $p− 1$ ] и [ $a$ , $2a$ , ..., $(p− 1)a$ ] (То, что написано справа - это $a⋅$ ПрСВ) и перемножим в каждой все числа.

Получаем, что $1⋅2⋅....⋅(p − 1)≡ a⋅2a⋅....⋅(p− 1)a$ (mod $p$ ) или $p−1 (p− 1)!≡ (p− 1)!a$ (mod $p$ ). Теперь перепишем это через разность, то есть $p−1 p−1 a (p− 1)!− (p− 1)!= (a − 1)(p− 1)!$ делится на $p$ . Из-за того, что НОД( $(p− 1)!$ , $p$ ) = 1 следует, что $p−1 a − 1$ делится на $p$ или $ap−1 ≡ 1$ (mod $p$ )

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Зафиксируем простое число $p.$ Проверим базу индукции: $a= 1.$ Тогда действительно $1p − 1 =0$ — делится на $p.$ Пусть $ap− a$ делится на $p.$ Докажем, что $(a+1)p− (a+ 1).$ делится на $p.$ Докажем, что для $0 <k < p$ число $Ckp$ делится на $p.$ Действительно, $Ckp = k!(pp−!k)!.$ В каждом из факториалов $k!$ и $(p− k)!$ все сомножители меньше $p,$ а потому взаимно просты с $p.$ Тогда, поскольку $p!$ делится на $p,$ то и $Ckp$ делится на $p.$ Благодаря этому утверждению и биному Ньютона, получаем

(a+ 1)p =∑p Ckak ≡ ap+ 1 k=0 p p

По предположению индукции $ap+ 1≡p a+ 1,$ чтд.

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

Задача 36#85458Максимум баллов за задание: 7

Назовём натуральное число шатким, если в нём чередуются нулевые и ненулевые цифры, причём цифра единиц ненулевая. Найдите все натуральные числа, не являющиеся делителями никакого шаткого числа.

Источники: Ломоносов-2016, 11.8 (см. olymp.msu.ru)

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

Если $n$ кратно $10,$ то все числа, кратные $n,$ тоже заканчиваются на $0.$ Значит, они не шаткие. Если $n$ кратно $25,$ то последние две цифры любого числа, кратного $n,$ могут быть $25,50,75$ или $00.$ Значит, они не шаткие. Теперь мы покажем, что только эти числа не являются делителем никакого шаткого числа.

Вначале рассмотрим нечётные числа $m,$ не кратные $5.$ Ясно, что НОД $(m,10)=1,$ также НОД $(( k ) ) 10 − 1 m,10 = 1,$ для любого $k ≥1.$ Значит, существует такое положительное $l$ что $l ( ) k ) ) 10≡ 1 (mod (10 − 1 m ,$ откуда $kl ( ) k ) ) 10 ≡ 1 (mod (10 − 1 m .$ Преобразуем:

( )( ) 10kl− 1 = 10k− 1 10k(l−1)+ 10k(l−2)+⋅⋅⋅+10k− 1

Следовательно $xk = 10k(l− 1)+ 10k(l−2)+ ⋅⋅⋅+ 10k+ 1$ кратно $m$ при любом $k≥ 1.$ В частности, $x2$ — шаткое кратное $m.$ Если $m$ кратно $5,$ то $5x2$ — шаткое кратное $m.$

Теперь рассмотрим степени $2.$ Докажем индукцией по $t,$ что $22t+1$ имеет шаткое кратное $wt$ с $t$ ненулевыми цифрами. Для $t=1$ можно взять $w1 = 8.$ Предположим, что $wt$ существует для некоторого $t≥1.$ Значит, $wt =22t+1d.$ Пусть $wt+1 =$ $102tc+ wt,$ где $c∈{1,2,3,...,9}$ будет выбрано позже. Ясно, что $wt+1$ шаткое и имеет в точности $t+ 1$ ненулевую цифру. Поскольку $( ) wt+1+22t 52tc+2d$ кратно $22t+3$ тогда и только тогда, когда $52tc+ 2d≡ 0( (mod 8))$ или $c≡ 6d( (mod 8)),$ мы всегда сможет подобрать значение $c$ среди $8,6,4$ и $2.$ Доказали. Значит, любая степень $2$ имеет шаткое кратное.

Наконец, числа вида $2tm,$ где $t≥ 1$ и НОД $(m,10)= 1.$ Такие числа име.т шаткие кратные вида $wtx2t.$

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

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

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

Задача 37#85914Максимум баллов за задание: 7

Докажите, что уравнение

5m2−-n n2+ 3m =1

имеет бесконечно много решений в целых числах.

Источники: ФЕ - 2024, 11.6 (см. www.formulo.org)

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

Подсказка 1

Для начала просто решим уравнение 5m^2 - 3m = n^2 + n. У нас есть квадраты обеих переменных, а значит нужно попробовать выделить два полных квадрата.

Подсказка 2

Заменим один получившийся квадрат на х, а другой на y. Должно получиться уравнение x^2 - 5y^2 = 4. Нам нужно доказать, что у уравнения бесконечное число решений. В таком случае, решение уравнения может быть связано с каким-либо бесконечным числовым рядом. Какую известную последовательность чисел вы знаете?

Подсказка 3

Числа Фибоначчи! Подумайте, как через них можно выразить решения этого уравнения. Это можно сделать, например, поподставляя последовательные числа Фибоначчи и их комбинации в уравнение.

Подсказка 4

В конце не забудьте проверить, что m и n получаются целые. Для этого можно заметить, что последовательность остатков чисел Фибоначчи по модулю 10 периодична. Так же нужно понять, зануляется ли в этих случаях знаменатель.

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

Решим сначала уравнение

2 2 5m − n = n +3m

______________________________________________________________________________________________________________________________________________________

5m2 − 3m = n2+ n

Умножим на 4 и прибавим 1 к обеим частям, чтобы выделить полный квадрат справа:

20m2− 12m+ 1= (2n+1)2

Теперь домножим обе части на 5 и выделим полный квадрат слева:

(10m− 3)2 =5(2n+ 1)2+ 4

Сделаем замену $x= 10m− 3,y = 2n +1$ . У получившегося уравнения

x2− 5y2 =4

имеются решения

x= ±(F2k−1+F2k+1),y =±F2k,k≥ 0,

где $Fk$ — числа Фибоначчи (мы пользуемся нумерацией $F0 = 0,F1 = 1,Fk+1 = Fk+ Fk−1$ при всех целых $k$ ). На самом деле

(Fk−1+ Fk+1)2− 5F2k = 4F2k− 1+4Fk−1Fk− 4F 2k

равно $k (−1)4$ для всех $k$ , что легко проверить по индукции: при $k= 0$ это выполняется, а если $2 2 k Fk−1+Fk−1Fk− Fk =(−1)$ , то и

F2k + FkFk+1− F2k+1 =Fk2− Fk−1Fk− F2k−1 = (−1)k+1

(Можно доказать с помощью теории уравнений Пелля, что $2 2 x − 5y = 4$ не имеет других решений.)

Теперь нужно найти бесконечно много $x$ и $y$ таких, для которых соответствующие $x+3 m = 10$ и $y−1 n= 2$ целые. Заметим, что последовательность остатков чисел Фибоначчи по модулю 10 периодична (так как пара ( $Fk−1,Fk$ ) может принимать конечное количество вариантов по модулю 10, а остаток следующего и предыдущего чисел Фибоначчи однозначно определяются по остаткам этой пары). Кроме того, $x =F2 =1$ и $y =F1 +F3 = 3$ подходят, они соответствуют тривиальному решению $m = n= 0$ . Значит, уравнение $5m2 − n =n2 +3m$ имеет бесконечно много решений.

_________________________________________________________________________________________________________________________________________________________________________________

Осталось понять, что они все не могут обнулять знаменатель. Действительно, если $(m,n)$ — решение уравнения $5m2− n= n2+ 3m$ , при котором $n2+ 3m =0$ , то и $5m2− n= 0$ . Следовательно, $25m4 + 3m = 0$ . Так как $m$ целое, то обязательно $m = 0$ (иначе $|| 4|| 25m > |3m|$ ), а значит, и $n= 0$ . Остальные пары $(m,n)$ нам подходят.

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

Задача 38#89081Максимум баллов за задание: 7

Дано натуральное число $k.$ Назовем натуральное число $n$ удачным, если существуют такие целые числа $x,y$ и $z,$ что $x+ y+ z = 2n$ и $n 4 − k = 3(xy+ yz+zx).$ Докажите, что, если существует удачное натуральное число, то все натуральные числа — удачные.

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

Подсказка 1

Какой способ является самым естественным при доказательстве того, что каждый элемент из множества объектов удовлетворяет некоторому условию, если известно, что среди элементов этого множества существует по крайней мере один, удовлетворяющий данному условию?

Подсказка 2

Метод математической индукции. Пусть число n является удачным. Докажем, что тогда n-1 так же является удачным. Каким способом это можно сделать?

Подсказка 3

Существование объекта проще всего доказать, если явно предъявить его. Если число n является удачным, то существуют числа x, y, z, что x+y+z=2^n, 4^n-k=3(xy+yz+zx). Давайте выразим числа a, b, c, которые удовлетворяют условию a+b+c=2^{n-1} и 4^{n-1}-k=3(ab+bc+ca), через уже существующие числа x, y, z. Каким популярным образом можно ввести числа a, b, c, зная, что их сумма ровно в два раза меньше суммы чисел x, y, z.

Подсказка 4

Пусть a=(x+y-z)/2, b=(x-y+z)/2, a=(-x+y+z)/2. Рассмотрение данных чисел естественно, поскольку в треугольнике со сторонами x, y, z, числа a, b, c являются длинами касательных из вершин треугольника ко вписанной окружности. Сумма их длин как раз в два раза меньше суммы длин сторон. Осталось показать, что 4^{n-1}-k=3(ab+bc+ca).

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

Докажем, что если натуральное число $n > 1$ является удачным, то и $n− 1$ является удачным. Возьмем $a= x+z−y,b= z+y−x,c= x+y−z. 2 2 2$ Заметим, что все три таких числа целые, поскольку $x+ y+z$ — четное. Понятно, что $n−1 a+ b+c =2$ и

n 4 − k= 3(xy+ yz+ zx) =3(a+ b)(b+c)+3(b+ c)(c+a)+ 3(b+ a)(a+ c) =

2 2 2 = 3(a + b +c )+ 9(ab+bc+ ac) =

=3(a+ b+c)2+3(ab+bc+ ac)= 3⋅4n−1+ 3(ab+ bc+ ac)

следовательно,

3(ab+ bc+ ca)=4n − k− 3⋅4n−1 = 4n− 1− k

С другой стороны понятно, что если $n$ — удачное, то взяв $a =x +y,b= y+z,c= z+ x,$ по аналогичным соображениям получим, что $n +1$ также удачное. Поскольку увеличениями и уменьшениями исходно числа на $1$ можно получить любое натуральное число, заключаем, что все натуральные числа являются удачными.

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

Задача 39#90310Максимум баллов за задание: 7

Докажите, что для всех натуральных $n$ число, записываемое $3n$ единицами, делится на $3n.$

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

Подсказка 1

Если не получилось явно понять, откуда берётся делимость, имеет смысл попробовать доказать утверждение индукцией по n. База очевидна, осталось придумать, как будем делать переход.

Подсказка 2

Нужно понять, как число из 3ⁿ⁺¹ единиц выразить через число из 3ⁿ единиц. Действительно, первое делится на второе, что можем сказать про частное?

Подсказка 3

И правда, мы понимаем, как выглядит частное, оно состоит из трёх единиц и нулей между ними. Такое число делится на три, а значит, с шагом индукции степень тройки, делящая число, растёт, что и требуется.

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

Докажем утверждение индукцией по $n.$

База индукции: при $n= 1$ утверждение верно, ведь $111$ делится на $3.$

Предположение индукции: пусть для $n= k$ число, записываемое $n 3$ единицами, делится на $n 3 .$

Переход: докажем утверждение для $n= k+ 1.$ Заметим, что число из $k+1 3$ единиц можно разделить на число из $k 3$ единиц, причём в частном будет число в записи которого ровно три единицы, а остальные цифры нули. Тогда наше число делит тройку, в степени на один большую, чем число из предположения индукции. Это и требуется, переход доказан.

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

Задача 40#90311Максимум баллов за задание: 7

Пусть $n >3$ — натуральное число. Докажите, что $n!$ можно представить в виде суммы $n$ попарно различных натуральных делителей $n!.$

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

Подсказка 1

Откуда брать столько различных делителей n! с суммой n! непонятно, потому логично доказывать утверждение по индукции. Вот только всё ещё при переходе нужно где-то брать новый делитель.

Подсказка 2

Например, при переходе можем делители, на которые разбит n!, домножить на n+1 и один делитель разложить в сумму двух меньших. Но почему его можно разложить так, что все делители по-прежнему различны? Хочется усилить доказываемое утверждение.

Подсказка 3

Будем доказывать, что искомое разложение в сумму делителей существует и содержит 1. Тогда из домноженных на n+1 делителей, как раз n+1 можно представить в виде суммы 1 и n.

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

Докажем следующее усиленное утверждение индукцией по $n:$ $n!$ можно представить в виде суммы $n$ попарно различных натуральных делителей $n!,$ один из которых равно $1.$

База индукции: $n= 4.$

4!=24= 12+ 8+3 +1

Предположение индукции: пусть верно, что для $n= k$ существуют попарно различные делители $k!.$ Обозначим их $a1 = 1,a2,...,ak,$ в сумме дающие $k!.$

Переход: докажем утверждение для $n =k +1.$ Заметим, что

(k+1)!=(k+ 1)⋅k!= (k+ 1)⋅(a1+a2+ ...+ ak+1)

Тогда возьмём числа

b =1,b =k,b = (k +1)⋅a, ...,b =(k+ 1)⋅a 1 2 3 2 k+1 k

Они являются делителями $(k+ 1)!$ по предположению (более того, $(kb+1)!= ka!, i≥ 2 i+1 i$ ). Также по предположению индукции их сумма как раз $k+ 1+ (k+ 1)(a2+ ...+ ak)= k+ 1+ (k +1)(k!− 1) =(k+ 1)!,$ среди чисел есть $1,$ а все делители, начиная с $b3,$ как были различны, так и остались. Причём $ai⋅(k+ 1)> k,$ так что они отличаются и от $b1,b2.$ Переход доказан.