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

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

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

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

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

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

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

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

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

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

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

Для чисел $a,b,c,d$ известно, что $a2+b2 = c2+ d2,$ а также $a+ b$ = $c+d.$ Докажите, что $a2022+ b2022 =c2022+ d2022.$

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

Из первого условия следует, что $(a +b)2− 2ab= (c+d)2− 2cd,$ а значит $ab=cd.$ С помощью индукции покажем, что в данном случае $n n n n a + b = c + d.$ База дана в условии. Заметим, что $n+1 n+1 n n n−1 n− 1 a + b = (a+ b)(a + b)− ab(a + b ),$ а равенства $n n n n a + b = c + d$ и $n−1 n−1 n−1 n−1 a + b = c + d$ верны по предположению. Таким образом, мы получили требуемое, в том числе и при $n =2022.$

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

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

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

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

Сумма положительных чисел $x ,x ,...,x 1 2 n$ равна $1. 2$ Докажите, что

1−-x1 1−-x2 1−-xn 1 1+ x1 ⋅1+ x2 ⋅...⋅1+ xn ≥ 3

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

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

База при $n= 1$ справедлива.

Переход: рассмотрим произвольный набор из $n+ 1$ положительных переменных, сумма которых равна $1 2.$ Положим $xn+ xn+1 =b,$ тогда для набора $x1,...,xn−1,b$ по предположению выполнено неравенство

1 − x1 1− x2 1− b 1 1-+x1 ⋅ 1+x2-⋅...⋅1+b-≥ 3

тогда имеем:

1-− x1⋅ 1-− x2 ⋅...⋅ 1− xn−1-≥ 1⋅ 1+-b 1 +x1 1 +x2 1+xn−1 3 1− b

Значит имеет место следующая оценка:

1−-x1⋅ 1−-x2⋅...⋅ 1-− xn+1 ≥ 1 ⋅ 1+-b⋅ 1−-xn⋅ 1−-xn+1 1+ x1 1+ x2 1 +xn+1 3 1− b 1+ xn 1+ xn+1

Теперь понятно, что для доказательства перехода достаточно доказать неравенство:

1 1+ b 1− xn 1− xn+1 1 3 ⋅1−-b ⋅1+-xn ⋅ 1+xn+1-≥3

Чтобы его доказать, достаточно заменить $b$ на $xn+ xn+1,$ домножить на знаменатели и привести подобные.

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

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

Дано число $0 <u <1.$ Определим последовательность:

1- 1- -1-- u1 =1 +u,u2 = u1 + u,u3 = u2 + u,...,un = un−1 +u

Докажите, что $un > 1.$

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

Докажем индукцией по $n$ , что $1 <u < -1-. n 1− u$

База. $u1 = 1+ u.$ Действительно, $1+ u> 1$ и $-1- 1+u < 1−u ,$ так как $2 1− u < 1.$

Шаг индукции. Пусть $-1- 1 <un < 1− u.$ Тогда

1 1 un+1 = un +u >-1-+ u= 1 1−u

un+1 = 1-+ u< 1+ u<--1- un 1− u

Переход индукции доказан. Осталось заметить, что доказанное утверждение даёт решение задачи.

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

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

Докажите, что для любого натурального $n$ справедливо неравенство:

---1--- ---1--- ---1--- 2- 12 +2019 + 22+ 2019 + ...+ n2+ 2019 < 45

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

Подсказка 1

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

Подсказка 2

Можно реализовать так: правую часть заменить на 2/45-2/(n+45). База индукции остаётся верной, а доказательство перехода сводится к сравнению 2/(45+n)-2/(46+n) с 1/((n+1)²+2019).

Подсказка 3

Из выражений выше разумеется больше 2/(45+n)-2/(46+n), поскольку неравенство тождественными преобразованиями можно свести к квадратному трехчлену от n с отрицательным дискриминантом и старшим коэффициентом 1.

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

Докажем индукцией по $n$ более сильное неравенство:

---1--- ---1--- ---1--- -2 --2-- 12+ 2019 +22+ 2019 +...+ n2+2019 < 45 − n +45

База $1 2 2 2020 < 45 − 46$ верна.

Переход: пусть $12+12019 + 22+12019 + ...+ n21+2019 < 245 − n2+45,$ тогда имеем:

12-+12019 + 22+12019 + ...+ n2+12019 +(n+-1)12+2019 < 425 − n-2+45 + (n+-11)2+-2019

Для доказательства перехода покажем, что:

2-− --2--+ -----1------< 2-− -2--- 45 n+ 45 (n +1)2+ 2019 45 n+ 46

После тождественных преобразований при натуральных $n$ получим неравенство:

2 0< n − 87n+ 1970

которое верно, так как дискриминант отрицательный. Таким образом, более сильное неравенство доказано, а значит исходное тоже.

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

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

Последовательность целых чисел $a n$ задается следующим образом:

2 an+1 =an − an+ 1,a1 =100.

Докажите, что любые два различных члена последовательности взаимно просты.

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

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

Подсказка 1

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

Подсказка 2

Можно посмотреть остаток любого члена последовательности по модулю предыдущего... и тут он оказывается равным единице! А что это значит?

Подсказка 3

А это значит, что единица должна делиться на потенциальный общий множитель, ведь мы имеем равенство по типу a₂ = a₁ * k + 1. Но ведь 1 делится только на 1, так что числа взаимнопросты! Теперь как-то надо обобщить это на все члены последовательности...

Подсказка 4

Ага, можно же воспользоваться индукцией!

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

Пусть $a n$ и $a n+m$ — два произвольных члена последовательности $(n,m ∈ℕ)$ . Докажем по индукции, что

an+m − an ⋅Nnm =1,

где $Nnm ∈ ℕ,$ то есть что $an+m− 1$ делится нацело на $an$ , а в терминах сравнения по модулю: $an+m ≡ 1. an$

Из этого будет следовать, что если нашлись два различных не взаимно простых члена последовательности $ak$ и $ak+l$ $(k,l∈ℕ )$ , которые имеют общий множитель $d ∈ℕ,d> 1,$ то в равенстве

ak+l− ak⋅Nkl = 1

левая часть делится на $d >1,$ а правая не делится, так что приходим к противоречию, которое доказывает взаимную простоту любых двух различных членов.

База индукции: для $m = 1$ имеем

2 an+1 =an − an+ 1a≡n 1

Шаг индукции:

an+m+1 = a2n+m − an+m +1 ≡an 1− 1 +1 =1

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

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

На доску записали три рациональных положительных числа. Каждую минуту числа на доске $x,y,z$ стираются, а вместо них выписываются числа $1- -1 1- x + yz,y+ zx,z+ xy.$ Докажите, что начиная с некоторого момента на доске не будет появляться целых чисел.

Источники: Всеросс., 2021, РЭ, 11.10(см. olympiads.mccme.ru)

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

Заметим сразу, что все числа, появляющиеся на доске, положительны и рациональны. Пусть $x ,y ,z n n n$ — числа на доске после $n$ минут, а $a =x0,b= y0,c= z0$ — исходные числа.

Положим $--1--- Fn =1+ xnynzn .$ Тогда $xn+1 =xnFn,yn+1 = ynFn$ и $zn+1 = znFn.$ В частности, $yn+1 yn b xn+1 = xn =...= a$ и, аналогично, $-zn+1 -c xn+1 =a.$

Положим $Pn =xnynzn,$ и пусть $Pn = pqnn$ — представление этого числа в виде несократимой дроби. Тогда $Fn = pn+pqnn,$ и потому

3 Pn+1 =PnFn3= (pn-+2qn)- pnqn

где последняя дробь также несократима (ибо $pn$ и $qn$ взаимно просты). Итак, $pn+1 = (pn +qn)3$ и $qn+1 =p2qn.$ В частности, $pn = (pn−1+qn−1)3 ≥(1+ 1)3 =8$ при $n≥ 1,$ и потому $qn ≥ 82qn−1 > qn−1$ при $n ≥ 2.$ Иными словами, последовательность $q1,q2,q3,...$ строго возрастает.

Обозначим через $D$ произведение всех числителей и знаменателей чисел $a,b$ и $c.$ Тогда при некотором $N$ имеем $qN >D2.$

Докажем, что с $N$ -й минуты все числа на доске нецелые. Действительно, пусть, скажем, $xn$ — целое при $n> N.$ Тогда $y = x ⋅-b,z = x ⋅ c, n n a x n a$ и потому

∏ 3 bc n = xn⋅a2

Знаменатель этого числа в несократимой записи делит $D2;$ но это невозможно, ибо $qn >qN >D2.$ Противоречие.

Курсы

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

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

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

Доказать, что при всех натуральных $n$ число $32n+3+ 40n− 27$ делится на 64.

Источники: САММАТ - 2021, 11.1 (см. sammat.samgtu.ru)

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

Подсказка 1

Для начала давайте преобразуем наше выражение, 3²ⁿ⁺³ можно представить как 27*3²ⁿ. То есть можно вынести что-то за скобочки!

Подсказка 2

Да, после несложных преобразований получим, что исходное выражение преобразуется в 27*(9ⁿ-1) + 40n. Остаётся доказать, что это выражение делится на 64 при любом натуральном n. Каким методом для доказательства лучше воспользоваться?

Подсказка 3

Верно, это может сделать через индукцию! Но перед этим введём вспомогательную лемму. Попробуйте доказать, что 9ⁿ-1 делится на 8 для любого натурального n.

Подсказка 4

Да, 9 сравнимо с 1 по модулю 8, так что доказывается несложно. Пусть 27*(9ⁿ-1) + 40n делится на 64, попробуйте доказать, что оно делится на 64 при n=n+1

Подсказка 5

Да, при переходе к n+1 получим 27*(9ⁿ⁺¹-1) + 40(n+1) = 27*(9ⁿ-1) + 40n + 40 + 27*8*9ⁿ. Остаётся правильно сгруппировать на слагаемые! То есть так, чтобы каждое из них делилось на 64

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

Воспользуемся методом математической индукции.

2n+3 2n n 3 +40n− 27= 27⋅3 − 27+ 40n =27(9 − 1)+ 40n,

при $n= 1$ выполняется деление на $64.$ Пусть это выражение делится на $64$ при $∀n >1.$

Рассмотрим это выражение при $(n+ 1).$ Имеем

n+1 n 27(9 − 1)+ 40(n +1)= 27(9 ⋅(8+1)− 1)+40n+ 40=

=27(9n − 1)+ 27⋅8⋅9n +40n+ 40=

=(27(9n− 1)+40n)+ 216⋅9n+ 40=

= (27(9n − 1)+ 40n)+ (216(9n − 1))+ 256

Каждое из трех слагаемых делится на $64,$ первое — по предположению, второе — потому что $216$ и $9n−1$ делятся на $8$ каждое ( $9k ≡8 1∀k ∈ℕ.$ ) и $256$ делится на $64$ .

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

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

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

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

Подсказка 1

Нередко задачи на существование решаются конструктивно. Проблема в том, что предъявление конструкции в этом случае бывает слишком громоздким и неудобным для описания. Что может помочь сделать его проще?

Подсказка 2

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

Подсказка 3

Обозначим данное простое за p, тогда разбиение на пары (dp^{2k}, dp^{2k+1}), при всех делителях d свободных от p и чисел 2k, что 2k+1 не превосходит степени вхождения p в n, является корректным. Разбиение на пары в остальных случаях (когда степени вхождения всех простых в n четны) будем строить индуктивно.

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

Решим задачу индукцией по количеству простых делителей в натуральном числе $n.$ Пусть

α1α2 αk n= p1 p2 ...pk

Перед этим докажем, что если какое-то из $α i$ нечётное, то все делители числа разбиваются на пары данным образом. Действительно, каждому делителю $d,$ в который число $p i$ входит в четной степени, можем поставить в пару число $dp . i$ При этом, каждому делителю, степень вхождения числа $p i$ в которое нечетна, будет поставлено пару оно же, деленное на $p, i$ тем самым каждый делитель будет участвовать ровно в одной паре.

База индукции при $k = 1$ выполняется, поскольку в любой паре делителей один из них делится на другой.

Докажем переход индукции. Если каждое $αi$ чётное, то делители числа $α1−1 α2 αk p1 p2 ...pk$ разбиваются на пары, поскольку число $pi$ входит в него в нечетной степени. Остальные делители имеют вид

α α α p11 x, где x |p22...pkk

Все делители числа $α2 αk p2 ...pk ,$ быть может, кроме одного, по индукционному предположению можно разбить на пары требуемым образом, тогда, домножив все делители на $α1 p1 ,$ получим корректное разбиение на пары делителей данного вида.

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

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

Найдите все натуральные числа $n,$ для которых числа от $1$ до $2n$ можно разбить на такие две группы $a ,a ,...,a 1 2 n$ и $b ,b,...,b 1 2 n$ по $n$ чисел в каждой, что $.. a1a2...an +b1b2...bn − 1.2n.$

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

Одно из чисел $a a ...a 1 2 n$ и $b b...b 12 n$ нечётно; примем, не умаляя общности, что это число $aa ...a . 12 n$ Тогда все $a i$ нечётны, таким образом, это числа $1,3,5,...,2n− 1$ в каком-то порядке. Среди чисел $b1,b2,...,bn$ находится число $2n,$ поэтому $a1a2...an− 1$ кратно $2n.$ Это невозможно, если у $n$ есть нечётный делитель, больший $1,$ так как в этом случае он находился бы среди $ai$ и $a1a2...an− 1$ на него бы не делилось. Таким образом, $n$ — степень двойки с целым неотрицательным показателем, $k−1 n =2 .$

При $k= 1$ условие задачи, очевидно, удовлетворяется: $0+ 1− 1$ кратно $2;$ при $k= 2$ число $2⋅4+ 1⋅3− 1$ на $4$ не делится. Докажем индукцией по $k,$ что при $k> 2$ выражение $k k 1⋅3⋅...⋅(2 − 1)+ 2⋅4⋅...2 − 1$ кратно $k 2 ,$ то есть что на $k 2$ делится $k 1⋅3⋅...⋅(2 − 1)− 1.$ При $k = 3$ число $1⋅3⋅5⋅7− 1 =104$ кратно $8.$ Пусть $k k 1⋅3⋅...⋅(2 − 1)= 1+ 2t.$ Тогда получаем, что

(2k+ 1)(2k+ 3)...(2k+1− 1)=1⋅3⋅...⋅(2k− 1)+ 2k(1 +3+ ...+ (2k− 1))+22ku=

= 1⋅3⋅...⋅(2k− 1)+ 2k ⋅22k−2+ 22ku

даёт при делении на $2k+1$ такой же остаток $1+ 2kt.$ Осталось заметить, что $(1+2kt)2 =1+ 2k+1t+ 22kt2$ даёт остаток $1$ при делении на $k+1 2 .$

Ответ:

$n =2k$ при $k= 0$ и $k≥ 2$

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

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

Дано натуральное число $a . 1$ Для каждого натурального $i$ число $a i+1$ получается так: $a i$ умножают на $52021$ , каждую цифру десятичной записи произведения заменяют её остатком при делении на $2,$ и получившуюся последовательность цифр рассматривают как двоичную запись $ai+1.$ Докажите, что $aN = aN+22021$ при всех достаточно больших $N.$

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

Подсказка 1

Как доказывать периодичность? Вообще не очень понятно, поэтому предлагается доказать, что целая часть при делении a_i на 2^2021 стабилизируется. Более того целая часть будет нулем или единицей. Как после этого можно доказать, что остаток будет периодичен?

Подсказка 2

В задаче активно фигурирует двоичная запись числа, поэтому разумно остаток представить в двоичной записи. Так как остаток меньше 2^2021, то слагаемых будет не больше 2021. Как можно доказать, что они периодичны с периодом 2^2021?

Подсказка 3

Давайте доказывать наше предположение по индукции. Начните с последних разрядов, докажите, что слагаемое, помноженное на a_i, периодично с периодом равным 2^i. Примените предположение для всех меньших и решите задачу.

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

Обозначим операцию замены всех цифр числа $n$ в десятичной записи их остатками при делении на $2$ и рассмотрения последовательности цифр, как двоичную запись, за $f(n).$ Т.е. $( 2021 ) ai+1 = f 5 ai .$

Пусть $2021 ak =bk⋅2 + ck,$ где $2021 0 ≤ck < 2 ,bk$ и $ck$ — целые числа. Докажем для начала, что начиная с некоторого $N$ число $bk$ перестаёт меняться и равняется $0$ или $1.$ Действительно, $2021 2021 2021 5 ak = bk ⋅10 + 5 ⋅ck,$ причём $2021 2021 5 ⋅ck < 10 ,$ т.е. цифры (в десятичной записи) чисел $2021 5 ⋅ck$ и $2020 bk⋅10$ не влияют друг на друга. Отсюда следует, что $2021 2021 f(ak)=f(bk)⋅2 + f(5 ⋅ck),$ причём $2021 2021 f(5 ⋅ck)< 2 ;$ заметим теперь, что $f(n)< n$ для всех $n$ кроме $0$ и $1,$ а $f(0)= 0$ и $f(1)= 1;$ значит, начиная с некоторого момента $bk$ стабилизируется.

Докажем теперь, что последовательность $ck$ периодична с периодом $2021 2 .$ Пусть

---------------- ck = dk,2020dk,2019...dk,02 = 22020⋅dk,2020+ ...+ 21 ⋅dk,1 +20⋅dk,0

т.е. посмотрим на двоичную запись числа $ck.$ Докажем, что $dk,i$ периодична с периодом $i 2.$ Доказывать будем индукцией по $i.$ Для $i= 0$ утверждение следует из того, что $2021 5$ нечётно, поэтому $ck$ остаётся всегда одной чётности, поэтому $dk,0$ не меняется. Теперь докажем переход от всех чисел, меньших $i,$ к $i.$

$2021 ( 2021 2022−i i−1 ) 5 ⋅ck = 5 ⋅dk,0+ ...+ 5 ⋅10 ⋅dk,i−1 + ( ) + 52021− i⋅10i⋅dk,i+ 52020−i⋅10i+1⋅dk,i+1 +...+ 5⋅102020⋅dk,2020$

Заметим, что выражение $( 2020−i i+1 2020 ) 5 ⋅10 ⋅dk,i+1+ ...+ 5⋅10 ⋅dk,2020$ не влияет на последние $i+1$ цифру числа $2021 5 ⋅ck,$ а значит не влияет и на $dk+1,i.$ По предположению индукции числа

(2021 2022−i i−1 ) 5 ⋅dk,0+...+5 ⋅10 ⋅dk,i− 1

а с ним и переносы в $i$ -й разряд, периодичны с периодом $i−1 2 ,$ а, значит, при увеличении $k$ на $i 2$ чётность $dk,i$ не изменится.

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

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

Верхней целой частью числа $x$ называют наименьшее целое число, большее или равное $x$ . Существует ли такое число $A$ , что для любого натурального $n$ расстояние от верхней целой части $n A$ до ближайшего квадрата натурального числа всегда равно 2 ?

Источники: ММО - 2021, первый день, 11.6 (см. mmo.mccme.ru)

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

Подсказка 1

Есть два возможных ответа — да или нет. Если нет, то нужно доказывать, что абсолютно для любого числа в последовательность {A^i} найдется не подходящее число, что кажется очень непростой задачей. Тогда будем доказывать, что ответ «да». Если мы хотим, чтобы верхняя целая часть Aⁿ отличалось от ближайшего натурального квадрата на 2, то хотелось бы понять, чему равна эта верхняя целая часть. Вернее, что нам было бы удобнее взять за верхнюю целую часть, чтобы она отличалась от какого-то квадрата на 2? А если вспомнить как возводится число вида t+1/t в квадрат?

Подсказка 2

Хотелось бы сделать так, чтобы число вида Aⁿ + 1/Aⁿ было бы целым и A было некоторым квадратом, чтобы как раз получить t^2n + 1/(t^2n) = (tⁿ + 1/tⁿ)²-2. Осталось только понять, чему должно быть равно t, чтобы каждое выражение вида Aⁿ + 1/Aⁿ при A = t², было бы целым. Здесь вас на поиск подходящего t может натолкнуть либо мысль о процессе построения бесконечных цепных дробей, либо же тот факт, что число вида (a+b√c)^k, где a, b, k - целые, это выражение вида t+l√c. Заметьте, это верно и для отрицательных k.

Подсказка 3

Да, можно просто сказать, что t — корень некоторого уравнения с целыми коэффициентами и отрицательным коэффициентом при x, ведь тогда t+1/t = c, где с — целая положительная константа. Тогда, по модулю факта про возведение таких иррациональностей в степень можно сказать, что задача решена, поскольку мы нашли такое t, что любое выражение вида t^k + 1/t^k — целое, а значит, мы нашли подходящее А.

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

Пусть $t$ — больший корень многочлена $x2− 10x+ 1$ , тогда $t+ 1 =10 t$ .

Докажем по индукции, что число $n 1- t + tn$ целое при любом целом неотрицательном $n$ .

Действительно, это верно при $n = 0,1$ . Кроме того,

n+1 1 ( n 1 )( 1) ( n−1 1 ) t + tn+1 = t + tn- t+ t − t + tn−1- ,

что позволяет проделать шаг индукции.

Положим $A = t2$ , тогда

( )2 An + 1-= tn+ -1 − 2 An tn

-1- An <1

Значит, $n -1 A + An$ и есть верхняя целая часть $n A$ , а ближайший к ней квадрат целого числа равен $(n -1)2 t+ tn$ .

Ответ: да

Интенсивы

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

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

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

Для действительного числа $α ∈(0,1)$ рассмотрим возрастающую последовательность всех натуральных чисел $m i$ , для которых ${miα} <α$ . Может ли для какого-то $α$ соответствующая последовательность начинаться с

a) $2021,4041,6062?$

б) $2021,4042,6062,8082?$

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

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

Подсказка 1

У нас задачка на последовательность, каким методом можем попробовать воспользоваться?

Подсказка 2

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

Подсказка 3

Попробуем доказать, что m_i является таким наименьшим натуральным числом n_i, что α*n_i ≥ i через индукцию. Что нам это даёт в наших пунктах? Отлично, мы на финишной прямой, применим утверждение на конкретных пунктах!

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

Покажем индукцией по $i$ , что $m i$ — это наименьшее натуральное число $n i$ , для которого $n α≥ i i$ .

_________________________________________________________________________________________________________________________________________________________________________________

База: для удобства будем считать 0 натуральным числом, и все последовательности тоже начинать с нулевого члена. Тогда, во-первых, $m0 = 0$ поскольку ${0α} =0 <α$ , и 0 — первое натуральное число с таким свойством, поскольку оно просто первое. С другой стороны, $n0 = 0$ поскольку $n0α≥ 0$ и опять же, 0 — первое натуральное число с этим свойством. Итак, $m0 = n0$ .

_________________________________________________________________________________________________________________________________________________________________________________

Переход. Пусть $mi = ni$ . Тогда для всех натуральных чисел $k$ из отрезка $[ni+ 1,ni+1− 1]$ имеем $[kα]= i$ из определения $ni+1$ . Но тогда ${kα}= {niα}+ (k − ni)α≥ α$ . С другой стороны, $ni+1α= (ni+1− 1)α+ α< i+1 +α$ то есть ${ni+1α <α}$ . Итак, $mi+1 =ni+1$ .

_________________________________________________________________________________________________________________________________________________________________________________

а). Из приведенных выше рассуждений следует система неравенств (самая левая)

( 1 1 ( 1 |{ 2020 >α ≥ 2021 |{ 2020< α ≤ 2021 1 1 1 |( 42040 >α ≥ 42041 ⇔ |( 2020 < 1α ≤ 202012 ⇔ 20203 <α-≤ 20202. 63061 >α ≥ 63062 202013 < 1α ≤ 202023

Преобразуем как написано выше, благо все числа положительны. Имеем, что условие выполняется для любого $α$ , такого что $1 α$ лежит в полуинтервале $( 1 1] 20203,20202$ .

Отметим, что для решения задачи не обязательно описывать множество всех таких $α$ (как сделано выше), достаточно указать одно, например, $2 4041$ , и доказать, что оно подходит.

_________________________________________________________________________________________________________________________________________________________________________________

б) Действуя аналогично, имеем:

( 1 1 ( 1 ||||{ 2020 >α ≥ 2021 ||||{ 2020< α ≤ 2021 42041 >α ≥ 40242 ⇔ 202012 < 1α ≤ 2021 ⇔ 20201 < 1≤ 20201. ||||( 63061 >α ≥ 60362 ||||( 202013 < 1α ≤ 202023 2 α 2 84081 >α ≥ 80482 202014 < 1α ≤ 202012

Приходим к противоречию, что $1 1 20202 <20202$ , что доказывает что такого $α$ не существует.

Ответ:

а) да

б) нет

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

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

В последовательности чисел $20,21,22,...$ некоторые члены умножили на -1 , причем известно, что осталось бесконечно много положительных членов. Докажите, что любое натуральное число представимо в виде суммы нескольких различных членов полученной последовательности.

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

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

Подсказка 1

Будем доказывать по индукции. Рассмотрим операцию сокращения последовательности. Удалим первый элемент, а остальные разделим на 2. Тогда у нас останется последовательность, описанная в условии.

Подсказка 2

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

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

Будем называть последовательность, удовлетворяющую условию задачи ПУУЗ.

Заметим, что следующая операция из ПУУЗ делает ПУУЗ: из последовательности выкидываем первый член, а все остальные делим на 2. В самом деле, все члены остались плюс или минус степенями двойки, и положительных все еще бесконечно. Назовем эту операцию сокращением.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем по индукции утверждение: любое натуральное $n$ для любой ПУУЗ представляется в виде суммы некоторые ее различных членов.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем что в таком виде представляется 1. В самом деле, у любой ПУУЗ есть положительные члены, пусть первый из них $k 2$ . Тогда заметим что

( ) ( ) ( ) − 20 + −21 +⋅⋅⋅+ −2k−1 + 2k = 1

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для всех натуральных чисел, меньших $n$ . Рассмотрим $n ≥ 2$ и ПУУЗ $A$ . Если $n$ четное — представим $n2$ в виде суммы нескольких различных членов сокращения $A$ , этому представлению соответствует представление $n$ в виде суммы различных членов $A$ . Если $n$ нечетное -— вычтем из него первый член $A$ , (который равен 1 или -1 ) и результат поделим пополам. Мы получили одно из чисел $n±21$ , оно натуральное и строго меньше $n$ , значит для него уже доказано, что оно представляется в виде суммы различных членов произвольной ПУУЗ, в частности — сокращения $A$ . Снова строим соответствующее представление $n$ в виде суммы различных членов $A$ .

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

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

$S$ — непустое подмножество множества натуральных чисел. Для любых $a,$ $b∈S$ существует $c∈S$ такое, что $a(a+b)$ делится на $c2.$ Докажите, что в $S$ найдется элемент, на который делятся все элементы $S.$

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

Подсказка 1

Единственным кандидатом на число, которое делит все остальные является самое маленькое число множества. Рассмотрите его в качестве a, какое число можно взять в роли b?

Подсказка 2

В качестве b рассмотрите b₀ наименьшее число, которое не делится на a. Что вы можете сказать про b?

Подсказка 3

Рассмотрите последовательность b₀, b₁, …, где b_{k+1} | a(a+b_k). Что вы можете сказать про результаты частного? В каких степенях могут входить простые делители a в b_i?

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

Пусть $a$ — наименьший элемент в множестве, $b 0$ — наименьший элемент множества не кратный $a.$ По условию существует $b 1$ такой, что делит $a(a+b0),$ аналогично определим ${bk}.$

Докажем по индукции, что $bi < 2a.$ Заметим, что $b1$ не может делиться на $a,$ иначе $a|b0,$ тогда

2 2 b1 ≥ b0 ⇒ a(a+ b0) ≥b0 ⇒ a ≥ b0(b0− a)⇒ b0 < 2a

то есть база индукции проверена.

Докажем, что $b < 2a. k+1$ Аналогично

2 2 2 a(a+ bk)≥ bk+1 ⇒ 3a > bk+1 ⇒ bk+1 < 2a

то есть переход выполнен и $a(a+ b )=b2 k k+1$ или $a(a+ b)= 2b2 . k k+1$ Пусть $p|a,$ обозначим за $α$ степень вхождения $p$ в $a,$ за $β i$ степень вхождения $p$ в $b. i$ Пусть $⊕1$ означает $+ 1$ или $+0.$ Тогда имеем $α +min(α,β)= 2β ⊕ 1. i i+1$ Пусть существует $β > α, i+1$ тогда $min(α,β)> α i$ — противоречие. Пусть существует $β <α ⇒ β >β , i i+1 i$ если $a(a +b) =b2 , i i+1$ такого бесконечно быть не может, так как $2a> bi,$ значит, с какого-то момента $2 a(a+bk)= 2bk+1,$ откуда, с какого-то момента $bk+1 > bk$ — противоречие, так как $bk ∈ ℕ.$ Тогда $βi+1 = α,$ откуда выходит, что $min(α,βi)= α,$ и $β0 = α.$ Значит, $a|b0$ — противоречие.

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

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

В ряд записаны $10$ различных натуральных чисел. Начиная со второго каждое равно сумме цифр предыдущего. Могут ли все числа быть точными квадратами?

Источники: Европейский математический турнир - 2020, автор Шаповалов А.В.

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

Начнём с числа $9$ и будем добавлять числа слева по одному так, чтобы выполнялись условия задачи.

Пусть у нас уже есть ряд из нескольких чисел, удовлетворяющий условию задачи, и пусть в нём первое число кратно $9.$ Обозначим его $9m.$ Добавим в начало ряда квадрат числа из $m$ девяток (в частности, в первый раз добавим $81$ ). Покажем, что оно удовлетворяет условиям.

Добавленное число имеет вид $m 2 2m m (10 − 1) = 10 − 2⋅10 + 1.$ Если вычесть из $2m 10 + 1$ число $m 2⋅10$ в столбик, будет очевидно, что сумма цифр числа $m 2 (10 − 1)$ равна $9m.$ То есть мы смогли добавить в начало ряда новое число.

Будем добавлять так до тех пор, пока не получим ряд из $10$ чисел.

Ответ:

Да, могут

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

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

Задана последовательность

2 a1 = 18,an = an−1 +6an−1

при $n> 1.$ Докажите, что в этой последовательности не встретятся степени (выше первой) натуральных чисел.

Источники: КМО - 2020, третья задача первого дня для 8-9 классов, автор Лучинин С.А. (cmo.adygmath.ru)

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

1 2 18= 2 ⋅3

a2 = 182 +6⋅18= 432= 24 ⋅33

Докажем индукцией по номеру члена последовательности, что каждый член последовательности, начиная со второго, можно представить в виде

ak = 2k+2⋅3k+1 ⋅tk

где $tk$ — целое, не делящееся на $2$ и на $3.$

База для $k= 2$ верна. Переход:

По предположению индукции, $ai =2i+2⋅3i+1⋅ti,$ где НОД $(ti,6)= 1.$

По условию,

ai+1 = a2i + 6ai =ai(ai+ 6)= 2i+3⋅3i+2 ⋅ti(2i+1⋅3i⋅ti+ 1)

Так как $i≥ 2,$ то последний множитель не делится ни на $2,$ ни на $3,$ то же верно для $ti.$ Значит, степени вхождения $2$ и $3$ в разложение на простые множители увеличились ровно на $1.$

Осталось заметить, что число вида $2s+1⋅3s⋅m,$ где НОД $(m,6)=1,$ не может быть степенью натурального числа выше первой. Ведь если бы оно было $p$ той степенью натурального числа, то все простые множители входили бы в него в степени, кратной $p.$ Тогда и числа $s+ 1$ и $s$ должны были бы делиться на $p,$ что невозможно при $p> 1.$

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

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

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

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

В последовательности чисел Фибоначчи $1,1,2,3,5,8,13,21,...$ каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Докажите, что среди чисел Фибоначчи нет ни одной натуральной степени числа $7.$

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

Подсказка 1

Какое первое число в последовательности чисел Фибоначчи кратно 7? Чему равен его индекс?

Подсказка 2

Первое число Фибоначчи, кратное 7 - это 21, которое является 8 числом Фибоначчи. Продолжив выписывать элементы данной последовательности можно заметить, что первые несколько членов, индексы которых кратны 8, делятся на 7. Докажите, что на 7 делятся те и только те члены последовательности чисел Фибоначчи, индексы которых кратны 8. Как можно доказать, что никакое из данных чисел не является степенью 7?

Подсказка 3

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

Подсказка 4

Да, достаточно показать, что на 3 делятся те и только те числа Фибоначчи, номер которых делится на 4.

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

Для начала докажем, что на $7$ делятся те и только те числа Фибоначчи, номер которых делится на $8.$ Докажем это по индукции. База: Первое число Фибоначчи, кратное $7$ — это $21,$ которое является $8$ числом Фибоначчи.

Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от $1$ до $8k.$ Докажем, что он верен для чисел от $8k+1$ до $8k+ 8.$ Пусть число с номером $8k − 1$ имело остаток $a$ от деления на $7(a ⁄=0).$ Тогда числа с номерами $8k +1,...,8k +8$ будут иметь следующие остатки: $a,a,2a,3a,5a,a,6a,0.$

Теперь докажем, что на $3$ делятся те и только те числа Фибоначчи, номер которых делится на $4.$ Доказательство аналогично.

Следовательно, если число Фибоначчи делится на $7,$ то его номер делится на $8.$ Значит его номер делится на $4,$ а значит, само число обязано делиться на $3.$ Значит оно не может быть равно натуральной степени числа $7.$

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

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

Докажите, что для любого натурального числа $n$ выполнено неравенство:

-1- -1- -1- √ - 3 1+ √2 +√3-+ ...+ √n > 2 n− 2

Источники: Муницип - 2020, Калининград, 11.3

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

Подсказка 1

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

Подсказка 2

Сделать это не так просто. Чаще всего это явный намек на то, что рассматриваемая индукция требует усиления. Необходимо придумать неравенство, из которое следовало бы наше, и доказать с помощью индукции уже его. Чего вам не хватало при попытках доказать переход в исходном неравенстве? Скорее всего это будет что-то не очень большое - формально, функция от n, которая монотонно убывает.

Подсказка 3

Будем доказывать, что разность левой и правой части неравенства не меньше, чем 1/2\sqrt(n).

Подсказка 4

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

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

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

-1- 1-- -1- √- 3 --1- 1+ √2-+ √3 + ...+ √n-≥ 2 n− 2 +2√n

Оно более сильное, чем в условии задачи, потому что мы доказываем неравенство для большего числа справа. Если будет верным для него, то и для исходного будет выполняться. База $n = 1$ верна.

Пусть неравенство верно при некотором натуральном $k$

√- 1+ √1-+ √1-+...+√1-≥ 2 k− 3 +-√1- 2 3 k 2 2 k

Используя его, получим

1+ √1-+√1-+ ...+ √1-+ √-1--≥ 2√k− 3 +-√1-+ √-1--- 2 3 k k+ 1 2 2 k k+ 1

Наконец, рассмотрим разность

( √- 3 1 1 ) ( √---- 3 1 ) 2 k −2 + 2√k-+ √k-+1- − 2 k+ 1− 2 + 2√k+-1 =

- = 2√k− 2√k+-1+ -1√-+ -√-1-- = −√---2√-----+ √1-+ -√-1-- = 2 k 2 k +1 k + k+1 2 k 2 k +1

---(√k−-√k-+1)2---- = 2(√k +√k-+1)√k√k-+1 ≥0

поэтому

---- 1+ 1√--+√1-+ ...+ √1-+ √-1--≥ 2√k+ 1− 3+ -√-1-- 2 3 k k+ 1 2 2 k +1

то есть неравенство верно так же при $k +1,$ что доказывает переход.

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

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

Найдите все неотрицательные целые числа $a$ и $b$ , удовлетворяющие равенству

2 2 a + b =841⋅(ab+ 1).

Источники: Межвед - 2020 (см. v-olymp.ru)

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

Пусть пара чисел $(a,b)$ удовлетворяет уравнению

2 2 2 a +b = k (ab+ 1),k= 29 (1)

Предположим, что одно из чисел, например $a$ , равно нулю. Тогда, очевидно, $b= k$ . Поэтому далее будем рассматривать такие решения ( $a,b$ ) уравнения (1), для которых

a⁄= 0,b⁄=0 (2)

Более того, будем предполагать, что

a ≤b (3)

Итак, пусть пара ( $a0,b0$ ) удовлетворяет (1), а также усл. (2), (3). Из (1) находим, что

b2− k2a0b0+a2− k2 = 0 0 0

Это равенство можно трактовать как квадратное уравнение относительно неизвестной $b0$ . По теореме Виета, помимо, собственно, $b0$ , это уравнение еще имеет корень $b′0$ такой, что

b0+ b′0 =k2a0 b0b′0 =a20− k2

________________________________________________________________________________________________________________________________________________________________________________________________________

Утверждение.

Этот новый корень $b′0$ удовлетворяет условиям:

b′0 ≥ 0,b′0 ∈ ℤ, b′0 < a0

Доказательство.

Числа $a0$ и $b′0$ удовлетворяют (1), поэтому $b′0 ≥0$ (иначе правая часть (1) была бы отрицательной, так как, по условию задачи и в силу (2), $a0 > 0$ ). Из (4) следует, что неотрицательное $b′0$ является целым, а из (5) — что

b′0 = a20− k2- b0

Установим, что $b′ <a 0 0$ . Действительно,

′ a20−-k2 2 2 b0 < a0 ⇔ b0 < a0 ⇔ a0− k < a0b0

В силу (3) получаем

a20 ≤ a0b0

Таким образом, пара $(a0,b0)$ , удовлетворяющая уравнению (1) и ограничениям (2), (3), порождает новую пару (см. (4)) вида ( $) ( ) b′0,a0 = k2a0− b0,a0$ , которая также удовлетворяет (1), (2), (3) (если, конечно, $a0 ⁄=k$ ; так как, согласно (5), $b′0$ еще может быть найден по формуле $b′0 =$ $2 2 a0−b0k-$ , так что, если $a0 = k$ , то (3) не будет выполнено). Будем эту новую пару обозначать как $(a1,b1)$ . Затем по тем же формулам можно из пары $(a1,b1)$ получить еще решение $(a2,b2)$ и т.д. Символически полученный результат представим следующим образом:

(a0,b0)→ (a1,b1)= (k2a0− b0, a0)→ (a2,b2)→ ⋅⋅⋅ Здесь am = k2am −1− bm− 1,bm =am−1, при этом am >am−1( см. утверж дение )

Сразу же отметим и формулы обратного преобразования

2 am−1 =bm,bm−1 = k bm − am

с помощью которых можно цепочку (6) продолжить влево. С помощью правила (7), из одного решения $(a0,b0)$ , удовлетворяющего (1), (2), (3), мы можем получить лишь конечное число новых решений уравнения (1), так как, согласно доказанному утверждению, $a > a > a > ⋅⋅⋅≥ 0 0 1 2$ . Значит, на каком-то шаге обязательно получится $a = 0 n$ (тогда, как было показано выше, $b = k n$ ). Чтобы на $n$ -м шаге получить 0 , на предыдущем шаге должно было быть $a = n−1$ $k$ (подставив $a= a = k n−1$ в (1), найдем $b=b = k3 n−1$ ). Таким образом, окончание цепочки (6) выглядит так:

( 3) ...→ (an−1,bn−1)= k,k → (an,bn)= (0,k)

(Цепочку (8) вправо продолжать смысла нет, так как далее $(0,k)→ (−k,0) → (0,k)→ ⋅⋅⋅$ .) А вот что предшествует паре $(an−1,bn−1)= (k,k3)$ ? Согласно $(7′)$ , на предыдущем шаге $an−2 = k3,bn−2 = k5− k−$ и это тоже решение уравнения (1)! Можно продолжить, получая новые решения: $an−2 = k5−$ $k,bn−2 = k7− 2k3$ и так далее. Значит, всего решений у уравнения (1) бесконечно много, так как цепочку (8) можно продолжить влево сколь угодно далеко.

Поясним почему (8) содержит все решения (1), удовлетворяющие условию (3). Пусть ( $a∗,b∗$ ) - какое-то (удовлетворяющее (3)) решение уравнения (1). Было показано, что с помощью формул (7) из решения ( $a∗,b∗$ ) можно получить цепочку новых решений (см. (6)), которая непременно закончится решением $(0,k)$ . Но это и означает, что ( $a∗,b∗$ ) содержится в (8), ведь, приняв теперь решение $(0,k)$ за отправную точку, мы с помощью обратных преобразований ( $′ 7$ ) вернемся к ( $∗ ∗ a ,b$ ) (а цепочка (8) именно так и устроена: начав с $(0,k)$ , мы с помощью ( $′ 7$ ) получаем ее всю).

Чтобы записать ответ несколько поменяем нумерацию: положим $(a0,b0)= (0,k)$ и двинемся с помощью $′ (7)$ по цепочке (8) влево (у нас будет $( 3) (a1,b1)= k,k ,(a2,b2)=$ ( $3 5 k,k − k$ ) и т.д.).

Ответ:

Решениями $(a,b)$ (при условии $a≤ b$ ) служат те и только те пары чисел $(a ,b ) n n$ , которые каждом $n ∈ℕ$ вычисляются по формулам:

2 an =bn−1,bn =k bn−1− an−1, a0 = 0,b0 =k;

здесь $k= 29$ .

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

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

Докажите, что при натуральном $n >2$ числа от 1 до $n$ можно разбить на два множества так, чтобы произведения чисел в множествах отличались не более чем в $n−1 n−2$ раз.

Источники: курчатов - 2020, 11.5 (см. olimpiadakurchatov.ru)

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

Подсказка 1

В задаче фигурирует n, поэтому можно было бы попробовать решать по индукции и аккуратно добавлять по числу. Какие трудности могут возникнуть в таком подходе? Как его скорректировать, чтобы было больше свободы в распределении чисел?

Подсказка 2

Можно вести индукцию с шагом 2. Тогда какие числа хочется добавить в каждое из множеств при доказательстве перехода?

Подсказка 3

Добавим n+2 в множество с меньшим произведением, а n+1 с большим произведением! Но нужно доказать, что оба частных меньше нужной нам дроби ;)

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

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

_________________________________________________________________________________________________________________________________________________________________________________

База при $n= 3,4,5$ .

При $n =3$ разобьём на множества ${1,2}$ и ${3}$ , отношение равно $3 2$ , что меньше $2 1$ .

При $n =4$ разобьём на множества ${1,2,3}$ и ${4}$ . Отношение будет $6 4$ , что как раз равно $3 2$ .

При $n =5$ разобьём на множества ${1,2,5}$ и ${3,4}$ . Отношение равно $12 10$ , что меньше $4 3$ .

_________________________________________________________________________________________________________________________________________________________________________________

Переход индукиии от $n$ к $n+ 2$ при $n≥ 4$ .

Пусть у нас есть разбиение чисел от 1 до $n$ , удовлетворяющее условию. Добавим в множество с меньшим произведением $P1$ число $n +2$ , а в множество с бОльшим произведением $P2$ число $n+ 1$ . Докажем, что произведения отличаются не более чем в $n+2−1 n+1 n+2−2-= -n-$ раз.