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

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

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

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

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

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

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

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

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

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

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

Можно ли расставить все натуральные числа от 1 до 2027 в ряд так, что для любого $k= 1,2,...,2027$ сумма первых $k$ чисел в этом ряду нацело делится на $k$ -е число в ряду?

Источники: ОММО - 2025, номер 1 (см. olympiads.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Для маленьких чисел у нас всё получилось, поэтому попробуем построить пример. Сумма всех чисел делится на 2027, так что 2027 можно поставить в конец. Без 2027 сумма будет 2027*1013, так что предпоследним хочется поставить именно 1013. Что будет дальше?

Подсказка 3

Оставшаяся сумма 2026*1013, так что можно поставить 2026, причем 1013 = (2027-1)/2, то есть половина от 2027. Теперь осталось продолжить пример и доказать, что он работает.

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

Рассмотрим следующую последовательность чисел:

1014,1,1015,2,1016,3,...,1013,2027

На нечетных позициях стоит последовательность чисел от 1014 до 2027, на четных — последовательность чисел от 1 до 1013. Покажем, что этот пример удовлетворяет условию задачи.

Пусть $2027= 2n+ 1,$ тогда перепишем ряд в следующем виде:

n+ 1,1,n+ 2,2,n+ 3,3,...n +k,k,...n,2n+ 1

Покажем делимость на $n +k,$ сгруппируем крайние члены:

(n+ 1)+(k− 1)+(n+ 2)+(k− 2)+⋅⋅⋅+ (n+ k− 1)+ 1

Каждая такая сумма кратна $n+ k,$ что и требовалось.

Покажем теперь делимость на $k,$ вычислим частичную сумму этого ряда:

1+ 2+⋅⋅⋅+(k− 1)+(n+ 1)+(n+ 2)+⋅⋅⋅+ (n+ k− 1)+ (n+ k)

По формуле суммы арифметической прогрессии получаем

nk+ 2⋅ k⋅(k−-1)+k, 2

где каждое слагаемое делится на $k.$

Ответ:

Да, можно

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

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

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

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

Докажите, что для любого натурального $a> 3$ существует бесконечно много натуральных $n$ таких, что $an− 1$ делится на $2 n .$

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

Очевидно, что $n = 1$ удовлетворяет условию. Пусть для некоторого $n$ условие выполняется. Построим новое подходящее число. По условию $an−1 n2 ∈ ℕ.$ Ясно, что $n n 2 a − 1≥4 − 1> n .$ Тогда $an−1 n2 > 1.$ Выберем $p$ — такое простое число, что $an−1- p|n2 .$ Докажем, что $np$ тоже удовлетворяет условию.

np n n(p− 1) n(p−2) a − 1= (a − 1)(a + a +...+1)

По определению числа $p$ знаем, что $an− 1$ делится на $pn2.$ Так как $an ≡ 1, p$ то

n(p−1) n(p−2) a + a + ...+ 1≡p 1◟+-1+◝.◜..+1◞≡p 0 p

Таким образом, $anp− 1$ делится на $n2p2,$ следовательно, $np$ — подходящее число и, следовательно, подходящих чисел бесконечно много, поскольку по любому натуральному $a$ и некоторому первому $n$ можно построить бесконечную возрастающую последовательность $n,$ удовлетворяющих условию задачи.

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

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

Петя выписал на доску два числа: сначала $4,$ затем $6.$ Позже пришёл Толя и стал дальше записывать числа по следующему правилу: очередное число $xn$ — это наименьшее составное число, большее $2xn− 1− xn−2$ , где $xn−1,xn−2$ — это предыдущее и предпредыдущее записанные на доске числа соответственно. Какое число появится на доске $100−$ м?

Источники: Бельчонок - 2025, Вариант 1, 11.2(см. dovuz.sfu-kras.ru)

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

Подсказка 1

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

Подсказка 2

x₁ = 4, x₂ = 6, x₃ = 9, x₄ = 14, x₅ = 20... как связаны, например, 4 и 14? Что нужно сделать с 4, чтобы получить 14?

Подсказка 3

Если к 4 добавить 1 и домножить на кое-что, то получится число, близкое к 14.

Подсказка 4

Докажите, что xₖ = (k+1)(k+2)2 - 1 ! А каким методом мы привыкли доказывать такие утверждения, зависящий от k?

Подсказка 5

Докажите равенство по индукции!

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

Вычислим первые несколько членов: $x = 8+ 1= 9, x = 12+2 =14, x = 19+ 1=20. 3 4 5$ Теперь покажем по индукции, что начиная с четвёртого члена

(k+ 1)(k+ 2) xk =-----2---- − 1

Базу мы уже проверили, пусть

xk−2 = k(k− 1)∕2− 1, xk−1 = k(k +1)∕2 − 1

Тогда $(k+1)(k+2) 2xk−1− xk−2 = 2 − 2.$ Тогда нужно проверить, что $(k+1)(k+2) 2 − 1$ всегда будет составным числом. Но это $k(k+3) 2 ,$ что делится или на $k,$ или на $k+3,$ что точно $>1.$ Тогда сотым числом будет

101⋅102 x100 =---2---− 1= 5150

Ответ:

$5150$

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

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

Бесконечная последовательность $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,$ что и требовалось доказать.

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

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

Назовём натуральное число ровным, если в его записи все цифры одинаковы (например: 4, 111, 999999). Докажите, что любое $n$ -значное число можно представить как сумму не более чем $n +1$ ровных чисел.

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

Подсказка 1

Обратим внимание на число Aₙ = 111...1 (из n единиц в записи). Что произойдет, если умножить его на однозначное число (например, 3 · 111 = 333)?

Подсказка 2

Представим, что число a не больше, чем Aₙ₊₁ − 1. Можно ли выразить a через Aₙ и какие-то остатки так, чтобы существенная часть суммы уже была ровным числом? Обратите внимание, что Aₙ точно остается ровным после домножения на любое однозначное число.

Подсказка 3

Выберем такое наибольшее натуральное q ≤ 9, что a = qAₙ + r для некоторого натурального r. Что тогда можно сказать про величину r?

Подсказка 4

По неравенству a ≤ 10Aₙ верно, что r ≤ Aₙ. Это может быть намек на индукцию, только вести ее надо не по количеству знаков в числе, да и придется предположение немного усилить.

Подсказка 5

Докажем по индукции более сильное утверждение: любое число a ≤ Aₙ можно представить как сумму не более чем n ровных чисел.

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

Пусть

An = 1◟.. ◝.◜1 ◞ nраз

Докажем по индукции более сильное утверждение: любое число $a≤ An$ можно представить как сумму не более чем $n$ ровных чисел.

База $n= 1$ очевидна.

Шаг индукции: Число $An+1$ само ровное. Если же $a ≤An+1 − 1= 10An,$ то $a$ можно записать в виде $qAn +r,$ где $0 ≤q ≤9,$ $0 ≤r≤ An.$ Число $qAn$ ровное, а $r$ можно представить как сумму не более чем $n$ ровных чисел по предположению индукции.

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

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

Множество $S$ состоит из $N ≥ 3$ натуральных чисел, никакое из которых не равно сумме двух других. Докажите, что элементы $S$ можно упорядочить $a1,$ $a2,...,an$ так, чтобы $ai$ не делило сумму $ai−1+ ai+1$ для $i=2,3,...,n − 1.$

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

Подсказка 1

Вспомним про условие "ни одно число не равно сумме двух других". Может ли число b > a, b > c для некоторых a, c делить сумму a + c?

Подсказка 2

Наложим еще одно условие на множество: если нельзя делить сумму соседей, может тогда еще запретим делить их разность?

Подсказка 3

Для шага индукции стоит удалить какой-то элемент и вернуть его обратно. Какой элемент вряд ли будет делить сумму/разность соседей?

Подсказка 4

Из подсказки 1 видно, что наибольший элемент не делит сумму любых соседей. Назовем a максимальный элемент множества S. Теперь попробуем вставить a в одну из n возможных позиций в удовлетворяющую условию последовательность b₁,...,bₙ₋₁: перед первым, между b₁ и b₂, ..., bₙ₋₂ и bₙ₋₁ или после последнего. Что может помешать при вставке?

Подсказка 5

Если при вставке a на позицию j возникают проблемы, то либо bⱼ₋₁ делит сумму/разность с a и bⱼ₋₂, либо bⱼ делит выражение с a и bⱼ₊₁.

Подсказка 6

Предположим, что для каждой позиции j вставки a есть проблема с соседями. Сколько всего позиций? А сколько элементов в S \ {a}?

Подсказка 7

Некоторый элемент bₖ оказывается "виновным" для двух соседних позиций j=k и j=k+1. Тогда bₖ делит:

Либо bₖ₋₁ ± a (для j=k)

Либо a ± bₖ₊₁ (для j=k+1)

Получаем систему сравнений по модулю bₖ. Можно ли получить из нее сравнение без a?

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

Назовём множество $S$ положительных целых чисел хорошим, если ни один его элемент не является суммой двух других различных элементов $S.$ Заметим, что если $a,b,c$ — три различных элемента хорошего множества $S,$ причём $b >a, b> c,$ то $b∤a+ c.$ Иначе, поскольку $b ⁄=a+ c,$ мы имели бы

b≤ (a+ c)∕2< max{a,c}

Докажем более сильное утверждение.

Пусть $S$ — хорошее множество из $n ≥2$ положительных целых чисел. Тогда элементы $S$ можно упорядочить в последовательность $a ,a,...,a 1 2 n$ так, что $a ∤a + a i i−1 i+1$ и $a ∤a − a i i−1 i+1$ для всех $i= 2,3,...,n− 1.$

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

Будем вести доказательство индукцией по $n.$ Базовый случай $n= 2$ тривиален, так как ограничений на упорядочение нет.

Для шага индукции предположим, что $n ≥3.$ Пусть $a= maxS$ и $T = S∖{a}.$ По предположению индукции найдём крутое упорядочение $b1,...,bn−1$ множества $T.$ Покажем, что $a$ можно вставить в эту последовательность так, чтобы получить крутое упорядочение $S.$ Иными словами, покажем, что существует $j ∈{1,2,...,n},$ для которого упорядочение

Nj =(b1,...,bj− 1,a,bj,bj+1,...,bn−1)

является крутым.

Предположим, что для некоторого $j$ упорядочение $Nj$ не является крутым, то есть некоторый элемент $x$ в нём делит либо сумму, либо разность двух соседних элементов. Поскольку в упорядочении $T$ такого не происходило, $x∈ {bj−1,a,bj}$ (если $bj−1$ не существует, то $x ∈{a,bj};$ аналогичное соглашение применяется и к $bj).$ Но случай $x= a$ невозможен: $a$ не может делить $bj−1− bj,$ так как

0 <|bj−1− bj|< a,

и не может делить $bj−1 +bj.$ Следовательно, $x∈ {bj−1,bj}.$ В этом случае сопоставим элементу $x$ индекс $j.$

Предположим теперь, что ни одно $Nj$ не является крутым. Поскольку имеется $n$ возможных индексов $j$ и лишь $n− 1$ элементов в $T,$ один из этих элементов (скажем, $bk$ ) сопоставлен двум различным индексам, которые должны равняться $k$ и $k +1.$ Это означает, что $bk$ делит числа $bk−1 +𝜀1a$ и $a+ 𝜀2bk+1$ для некоторых знаков $𝜀1,𝜀2 ∈{−1,1}.$ Но тогда

bk−1 ≡ −𝜀1a≡ 𝜀1𝜀2bk+1 (mod bk),

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

bk |bk−1− 𝜀1𝜀2bk+1 =bk−1± bk+1,

что означает, что упорядочение $T$ не было крутым. Это противоречие завершает шаг индукции.

Курсы

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

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

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

Докажите, что для каждого натурального $n$ существуют такие целые числа $a n$ и $b n$ , что

(1+ √5)n a + b√5- --2-- = -n-2n---.

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

Докажем индукцией по $n,$ что такие числа $a n$ и $b n$ существуют, причём они будут одной чётности.

База для $n= 1$ очевидна. Докажем переход от $n$ к $n+ 1.$

( √-)n+1 ( √-)n ( √-) 1+--5 = 1+--5 1+--5 2 2 2

По предположению индукции существуют такие $an$ и $bn,$ что

(1 +√5 )n an+ bn√5 --2-- = ----2---

Тогда

( 1+√5-)n+1 (an +bn√5) (1 +√5-) (an+ 5bn)+ (an +bn)√5 --2-- = ----2--- --2-- = ---------4---------

Пусть $an+1 = an+52bn$ и $bn+1 = an+2bn.$ Из предположения индукции $an+1$ и $bn+1$ — целые числа, причём одной чётности. Переход доказан.

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

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

Последовательность ${a} n$ задана по правилу: $a =2, 1$

an+1 = anan−1an−2 ...a1+1.

Докажите, что

1- 1- 1- a1 + a2 + ...+ an < 1.

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

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

-1 -1 -1 ----1--- a1 + a2 + ...+ an +a1a2...an ≤1

База для $n= 2$ очевидна. Докажем переход от $n$ к $n+ 1.$ По предположению индукции:

a1+ a1+ ...+ a1 ≤1− a-a-1...a- 1 2 n 1 2 n

Тогда

1-+ 1-+ ...+ 1-+ -1--+ ----1-----≤ 1− ---1----+ -1--+ ----1-----=1, a1 a2 an an+1 a1a2...an+1 a1a2...an an+1 a1a2...an+1

так как

--1- -----1---- a1a2...an+-1 ----1--- an+1 + a1a2...an+1 = a1a2...an+1 = a1a2...an

Переход доказан. Из доказанного выше следует утверждение задачи.

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

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

Про натуральные числа $a$ и $b$ известно, что $a2+ b2+1$ делится на $ab.$ Докажите, что $a2+b2+ 1= 3ab.$

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

Подсказка 1

Соотношение делимости и требуемое равенство связаны. Можно ли эту делимость переписать иначе, так, чтобы получилось уравнение?

Подсказка 2

Условие a² + b² + 1⋮ab можно переписать как a² + b² + 1 = kab для некоторого натурального k. Попробуйте рассмотреть это соотношение как уравнение относительно a, фиксируя b. На что похоже получившееся уравнение?

Подсказка 3

Составим квадратный трехчлен, одним из корней которого является a:
x² − (kb)x + (b² + 1) = 0
Вспомним, как связаны коэффициенты и корни, и какие техники (вроде индукции и рекурсивного спуска) можно использовать для доказательства утверждений про корни.

Подсказка 4

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

Подсказка 5

В случае b = 1 нельзя совершить очередной прыжок. Стоит исследовать получившееся уравнение.

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

Если $a =b,$ то $a2$ должно делить $2a2+ 1,$ но они взаимно просты. Откуда $a =b =1$ и поэтому $3ab= a2+b2+ 1$ выполняется. В дальнейшем без потери общности считаем, что $a> b.$

Пусть

a2+b2+ 1 k= ---ab---.

Рассмотрим пару $(a,b)$ с минимальной суммой $a +b$ среди всех решений. Рассмотрим

a2− (kb)a+ (b2+ 1)=0,

как квадратное уравнение относительно $a,$ одним из корней которого является $x1 = a.$ По формулам Виета второй корень может быть представлен в виде:

b2+ 1 x2 = kb− a=--a--.

Первое представление показывает, что $x2$ является целым числом, а второе представление, что это число положительно. Неравенство $a >b$ влечёт, что

2 x2 = b-+-1< b< a, a

если $b> 1,$ что противоречит минимальности пары $(a,b).$

Рассмотрим $b= 1.$ При этом значение $a$ должно делить $a2+2,$ и поэтому $a$ равно $1$ или $2.$ Случай $a= 1$ невозможен, поскольку $a ⁄=b.$ В случае $a= 2$ имеем

a2-+b2+-1 6 k = ab = 2 =3.

Получаем, что

a2+b2+ 1 ---ab---= 3,

то есть $3ab= a2+b2+ 1,$ для всех упорядоченных пар $(a,b).$

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

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

Докажите, что если для некоторых натуральных чисел $a$ , $b$ , $k$ выполнено равенство $a2+-b2= k ab+1$ , то $k$ — точный квадрат.

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

Подсказка 1

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

Подсказка 2

Составим квадратное уравнение, где a — корень:
x² - kbx + (b² − k) = 0
Вспомним "прыжки Виета" — как второй корень c связан с исходными числами? Чему он равен по теореме Виета?

Подсказка 3

Второй корень можно выразить как (b² − k) / a. Если k не точный квадрат, что можно сказать о нем, например в сравнении с a?

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

Предположим, что существует какое-то решение, для которого $k$ не является точным квадратом. Для такого значения $k$ рассмотрим решение $(A,B ),$ с минимальной суммой $A+ B.$ Без потери общности можно считать, что $A ≥ B.$ Переписывая выражение для $k$ и заменяя $A$ на $x,$ получаем квадратное уравнение:

2 2 x − (kB)x+ (B − k)= 0.

По построению $x =A 1$ является корнем этого уравнения. По формулам Виета второй корень может быть представлен в виде:

B2-−-k x2 = kB− A = A .

Из первого выражения для $x2$ следует, что $x2$ является целым числом, а из второго — что $x2 ⁄= 0$ (поскольку $k$ не является квадратом). Так как

x2+ B2 k= x2B-+1 > 0, 2

то $x2$ является положительным. Наконец, из $A ≥B$ следует:

x2 = B2−-k< A =⇒ x2+ B <A +B, A

что противоречит минимальности решения $(A,B).$

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

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

Докажите, что уравнение $a2+ b2+ c2 = kabc$ в натуральных числах

(a) не имеет решений при $k= 2;$

(b) не имеет решений при $k> 3;$

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

Подсказка 1

Рассмотрим уравнение a² + b² + c² = 2abc по модулям 2, 4. Что можно сказать о чётности a, b, c?

Подсказка 2

Если все три числа чётные, поделим их на 2. Похоже на новое уравнение. Вспомним про принцип бесконечного спуска — не бывает бесконечно убывающих последовательностей натуральных чисел!

Подсказка 3

Перейдем к пункту b. Рассмотрим квадратный трёхчлен, полученный из исходного уравнения заменой a на x: x² − (kbc)x + (b² + c²) = 0. У него есть корень a, какой второй?

Подсказка 4

Это kbc − a. Можно ли что-нибудь рассказать про их взаимное расположение, если упорядочить a, b, c?

Подсказка 5

Операция (a, b, c) → (kbc − a, b, c) генерирует новые решения из старых. Как получить бесконечную последовательность разных решений? Можно ли этой операцией неограниченно увеличивать/уменьшать максимум среди членов тройки при разных k?

Подсказка 6

При k = 1, 3 если найдем одно решение, то получим бесконечно много других. Как же найти "первое" решение? Можно посмотреть на несложные случаи, например a = b = с, или посмотреть на уравнение относительно а при небольших b, c.

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

a) Усилим утверждение, покажем, что для четных $k= 2m$ нет решений. Предположим, что решение есть, и рассмотрим четверку $(a,b,c,2m )$ с минимальной суммой $a+b+ c:$

2 2 2 a +b + c = 2mabc

по модулю 2, очевидно, что тогда либо $a,b,c$ делятся на $2,$ либо только одно из них, но тогда

a2+b2+ c2 ≡2 ⁄≡2abc≡ 0 (mod 4),

противоречие. Пусть $a= 2a1,b= 2b1,c= 2c1,$ тогда приходим к равенству:

a2+ b2+ c2= 4ma1b1c1, 1 1 1

тогда у решения $(a1,b1,c1,4m)$ сумма меньше, противоречие.

b) Сначала предположим, что существует решение $(a,b,c),$ удовлетворяющее

a2+ b2+c2 = kabc, k >3.

______________________________________________________________________________________________________________________________________________________

Утверждение. Числа $a,b,c$ попарно различны.

Предположим противное: пусть $a= b.$ Тогда:

2b2+ c2 =kb2c =⇒ kc− 2 =z2, z ∈ℕ,

где $z2 = c2∕b2$ — натуральное число, поскольку левая часть натуральна. Это означает:

c2 = b2z2 =⇒ c= bz.

Подставим:

2 kc− 2= k(bz)− 2 =z =⇒ z(kb− z)= 2 =⇒ z |2.

Следовательно, $z = 1$ или $z = 2.$ В обоих случаях:

kb= 3,

что противоречит условию $k> 3.$

______________________________________________________________________________________________________________________________________________________

Теперь можно считать, что $a> b>c ≥1.$ Заметим, что если $(a,b,c)$ — решение, то $(kbc− a,b,c)$ также является решением, так как:

2 2 2 2 2 2 a + b +c = kabc =⇒ (kbc− a) + b +c

=(kbc)2+ kabc− 2kabc= kbc(kbc− a)

Рассмотрим квадратное уравнение:

f(x) =x2− kbc⋅x +(b2+c2)= 0.

Известно, что $f(a)= f(kbc− a)= 0.$ Вычислим:

f(b)= b2− kbc⋅b+ b2+ c2 = 2b2+ c2− kb2c.

Оценим:

f(b)< 2b2+ c2− kb2 < 3b2− kb2 = b2(3− k)<0

Поскольку $f(x)$ — квадратный трёхчлен с положительным старшим коэффициентом, и $f(b)< 0,$ то корни $a$ и $kbc− a$ лежат по разные стороны от $b.$ Учитывая $a> b,$ получаем:

kbc− a< b< a.

Таким образом, для решения $(a,b,c)$ с $max(a,b,c)=a$ мы получаем меньшее решение $(kbc− a,b,c)$ с:

max(kbc− a,b,c)= b<a.

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

c) В предыдущем пункте, доказали, что если $(a,b,c)$ – решение, то и $(kbc− a,b,c)$ – решение. Будем считать, что все решения упорядочены, то есть для любого решения $(a,b,c),$ $a≥ b≥c.$

Пусть $k = 3.$ Тогда из решения $(a,b,c)$ получается решение с большим максимальным элементом $(3ab− c,a,b),$ ведь $3ab> 2a≥ a+ c.$ Тогда для любого натурального $n$ из тройки $(1,1,1)$ можно получить решение $(a,b,c),$ где $a≥n,$ то есть решений бесконечно много.

Аналогично при $k= 1$ из решения $(3,3,3)$ переходами от тройки $(a,b,c)$ к $(ab− c,a,b)$ можно получить решение со сколь угодно большим максимальным элементом, ведь $ab ≥3a> a+ c,$ при $a≥ 3, b≥ 3.$

Интенсивы

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

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

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

Дано натуральное число $k.$ Докажите, что существует бесконечная возрастающая последовательность натуральных чисел ${a} i$ такая, что для любого $n$ число $2 an +k$ делится на $an+1,$ а число $2 an+1+ k$ делится на $an.$

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

Подсказка 1

Из условий aₙ₋₁ ∣ (aₙ² + k) и aₙ₊₁ ∣ (aₙ² + k) следует, что aₙ² + k кратно обоим. Существует соотношение между aₙ₋₁ и aₙ₊₁, которое делает эти делимости эквивалентными.

Подсказка 2

Рассмотрим соотношение:
aₙ₋₁ ⋅ aₙ₊₁ = aₙ² + k
В этом случае условия делимости aₙ² + k на aₙ₋₁ и aₙ₊₁ эквиваленты. Можно ли задать последовательность рекуррентно и показать, что в таком случае будут выполняться требуемые условия?

Подсказка 3

Для доказательства исходных утверждений о делимости, можно ввести новые условия на члены последовательности, например, взаимную простототу с k, НОД(aₙ, k) = 1. Что тогда можно сказать о НОД(aₙ, aₙ₋₁) = 1?

Подсказка 4

Если все члены взаимно просты с k, то какие члены подойдут в качестве начальных?

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

Определим последовательность ${a } n$ рекуррентно:

a2n+-k a1 =1, a2 =k +1, an+1 = an−1 для n ≥2.

Заметим, что

an−1 |a2n+ k ⇐⇒ an+1 ∈ℕ, an+1 |a2n +k.

Докажем по индукции громоздкое утверждение для каждого $n:$ $an ∈ℕ,$ $НОД(an,k)=1,$ $Н ОД(an−1,an)= 1.$

База индукции:
$a1 = 1,$ $a2 =k +1,$ $a3 =(k+ 1)2+ k$ – все очевидно.

Индукционный переход:
Предположим, что $НОД (am,k)= 1,$ $НОД(am,am−1)= 1$ для всех $m≤ n,$ где $n≥ 2.$ Докажем, что

2 an+1 = an+-k ∈ℕ. an−1

Для этого покажем, что $an−1 |(a2n+ k).$
Рассмотрим выражение:

2 ( a2n−1+k)2 (a2n−1+ k)2+ka2n−2 an +k = -an−2-- + k= ------a2n−2------.

Обозначим числитель:

2 2 2 N = (an−1+ k)+ kan−2.

По предположению индукции выполняется:

2 2 an−1 |(an−2+ k) =⇒ an−2 ≡ −k (mod an−1).

Подставляем:

2 2 2 2 N ≡ (an−1+ k) +k ⋅(−k)≡ k − k ≡0 (mod an−1).

0≡N ≡ a2 ⋅(a2 +k) (mod a ), n−2 n n− 1

но $НО Д(a2n−2,an−1)= 1,$ поэтому сравнение можно сократить:

2 an +k ≡0 (mod an−1)

Следовательно, $an−1 |(a2n+ k).$ Таким образом,

a = a2n+-k ∈ℕ. n+1 an−1

Докажем часть про $НОД (an,k)= 1,$ $НОД(an−1,an)= 1.$ Рассмотрим $Н ОД(an+1,an).$ Пусть $d= НОД (an+1,an).$ Тогда $d|an+1$ и $d|an.$ Из рекуррентной формулы:

an+1 ⋅an−1 = a2n+ k.

Так как $d|an,$ то $2 d|an.$ Следовательно, если $d |an+1 :$

2 d |(an+ k) =⇒ d|k.

Таким образом, $d$ — общий делитель $an$ и $k.$
По индукционному предположению $Н ОД(a ,k)= 1, n$ поэтому $d= 1.$

Пусть теперь $d= НОД (a ,k). n+1$ Тогда $d|k$ и $d |a . n+1$
Из определения последовательности:

2 an+1 ⋅an−1 = an+ k.

Так как $d|k,$ то $a2n+ k≡ a2n (mod d).$
Поскольку $d|an+1,$ левая часть сравнима с $0$ по модулю $d:$

a ⋅a ≡0 (mod d). n+1 n−1

Следовательно, $a2n ≡ 0 (mod d),$ откуда $d|a2n.$
По индукционному предположению $Н ОД(an,k)= 1,$ поэтому $d$ взаимно просто с $k.$ Таким образом, $НО Д(an+1,k)= 1.$

Осталось проверить, что последовательность возрастающая. Докажем по индукции, что $an+1 > an$ для всех $n≥ 1.$

База индукции ( $n = 1$ ):
$a1 = 1,$ $a2 =k +1≥ 2> 1,$ так что $a2 >a1.$

Индукционный переход:
Предположим, что $an > an−1$ для некоторого $n≥ 2.$ Докажем, что $an+1 > an.$ Вычислим:

a2n-+k a2n-+k-− anan−1 an+1 − an = an−1 − an = an−1 .

По индукционному предположению $an > an− 1 ≥1,$ поэтому:

an(an − an−1)+ k> 0.

Следовательно, числитель положителен. Знаменатель $an−1 > 0,$ поэтому $an+1− an > 0,$ то есть $an+1 > an.$

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

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

Натуральные числа $a,b,c$ таковы, что

2 2 |a +b − abc− 2|<c.

Докажите, что число $a2+ b2− abc$ является точным квадратом.

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

Подсказка 1

Введем d = a² + b² - abc. Условие |d − 2| < c ограничивает значения d. Тогда стоит пойти от противного, путь d — не полный квадрат.

Подсказка 2

Рассмотри многочлен:
x² − (bc)x + (b² − d) = 0
Вспомним прыжки Виета: второй корень x₂ можно выразить как...

Подсказка 3

x₂ = bc − a или x₂ = (b² − d)/a
Что это даёт, если d — не полный квадрат?

Подсказка 3

Исследуем x₂ на положительность. Используем для этого уравнение x₂² − (bc)x₂ + (b² - d) = 0, можно ли из него получить неравенство без d?

Подсказка 4

Верно ли, что x₂ < a?

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

Обозначим

2 2 d =a + b − abc

Тогда $|d− 2|< c =⇒$

−c+ 3≤d ≤c+ 1.

Зафиксируем $c$ и $d.$ Рассмотрим все пары положительных целых чисел $(a,b),$ удовлетворяющих уравнению

a2+ b2 − abc= d.

Выберем пару $(a,b)$ с минимальным значением суммы $a+ b$ и без ограничения общности будем считать, что $a ≥b.$

Рассмотрим квадратное уравнение относительно $x :$

x2− bc⋅x+ (b2− d) =0.

Очевидно, что $x1 = a$ является корнем. По теореме Виета, второй корень $x2$ удовлетворяет соотношениям:

2 x2 =bc− a x2 = b-− d a

Предположим, что $d$ не является полным квадратом, тогда $x2 ⁄= 0.$ Из представления $x2 =bc− a$ следует, что $x2$ целое.

Покажем, что $x2 >0.$

0= x2 − bc⋅x2+ b2− d≥ x2− bc⋅x2+ b2− c− 1= x2+ b2− c(bx2+ 1)− 1 ⇐⇒ 2 2 2

c(bx2+ 1)+1 ≥b2+ x22 ≥2,

так как $x2 ⁄= 0,$ $b⁄= 0.$

c(bx2+ 1)≥ 1 =⇒ bx2 ≥0,

получаем, что $x2$ – натуральное.

Теперь покажем, что $x2 < a.$

b2−-d b2 b2 x2 = a < a ≤ b = b≤ a.

Теперь рассмотрим пару $(x2,b).$ Она удовлетворяет исходному уравнению:

2 2 x +b − bc⋅x =d.

Тогда получается

x2+ b< a+ b,

что противоречит минимальности суммы $a+ b.$ Следовательно, предположение о том, что $d$ не является точным квадратом, неверно.

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

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

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

2 2 2 a + b+ c = 1+2abc.

Докажите, что хотя бы одно из чисел $a+1- 2$ , $b+1, 2$ $c+1- 2$ является точным квадратом.

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

Подсказка 1.

Попробуйте рассмотреть это соотношение как уравнение относительно a, фиксируя b и c. На что похоже получившееся уравнение?

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

Не умаляя общности, пусть $a ≥b≥ c.$ Рассмотрим уравнение из условия как квадратное уравнение относительно $a :$

2 2 2 a − 2bca+b + c − 1 =0

Так как оно уже имеет один целый корень, то второй его корень рациональный. А так как уравнение приведённое, то второй его корень — тоже целый. Обозначим этот второй корень через $a1$ и запишем теорему Виета:

a = 2bc− a= b2+-c2−-1 1 a

Очевидно, что $a1 > 0.$ Если $c=1,$ то $c+1- 2 =1$ является точным квадратом. Если же $c≥2,$ докажем, что $a> a1.$ Предположим, что $a1 ≥ a.$ Тогда

4b≤ 2bc= a1+ a≤ 2a1

то есть $a1 ≥ 2b.$ Но

2 2 2 2ab≥ 2b >b + c − 1 =aa1 ≥ 2ab

Противоречие.

Следовательно, $a1 <a.$ Заметим, что $a1+21-$ является точным квадратом тогда и только тогда, когда $a+21$ является точным квадратом. Действительно,

2 2 2 a1+1-⋅ a+-1= a1a+-a1-+a+-1 = b-+-c-− 1-+2bc+1 = (b+-c) 2 2 4 4 4

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

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

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

Докажите, что уравнение $a2+ b2+ a+ b= 5ab$ не имеет решений в натуральных числах.

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

Предположим, что это уравнение имеет решения. Выберем из всех решений такое, что сумма $a+b$ минимальна. Не умаляя общности, $a ≥b.$ Рассмотрим исходное уравнение, как квадратное относительно $a:$

2 2 a + a(1− 5b)+ b +b =0

Пусть $L$ — второй корень квадратного уравнения, тогда по теореме Виета:

b2-+b- L= 5b− a− 1 = a

Очевидно, что $L$ — целое и положительное, следовательно, натуральное. Отсюда $(L,b)$ — тоже натуральное решение уравнения, тогда из минимальности $a +b$ получаем, что $L≥ a:$

b2+b --a--≥a

b2 +b≥ a2 ≥ b2

Это возможно лишь при $a =b,$ в этом случае

2a2+ 2a =5a2

2= 3a

Получаем противоречие, ведь $a$ натуральное. Таким образом, исходное уравнение не имеет решений.

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

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

Пусть $n$ — натуральное число такое, что уравнение $x2+ y2+ z2 =n(xyz+1)$ имеет решение в натуральных числах. Докажите, что $n$ представимо в виде суммы квадратов двух целых чисел.

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

Выберем из всех решений $(x,y,z)$ то, при котором сумма $x +y+ z$ минимальна. Не умаляя общности, $x≥ y ≥ z.$ Рассмотрим исходное уравнение, как квадратное относительно $x :$

2 2 2 x − nyzx+ y +z − n= 0

Пусть второй корень равен $L,$ тогда по теореме Виета

y2-+z2−-n- L = nyz− x = x .

Очевидно, что $L$ — целое. Рассмотрим случаи:

1) $L≤ −1.$ Тогда

(x+1)(L+ 1) ≤0

xL+ x+ L+ 1≤0

y2+z2+ n(yz − 1)+ 1≤0

Это неравенство неверно, ведь $yz ≥ 1.$

2) $L= 0.$ Тогда $n= y2+ z2,$ что и требовалось доказать.

3) $L≥ 1.$ Из минимальности $x +y+ z$ получаем, что $L≥ x.$ Тогда $n≥ 2yxz.$ Значит,

2 2 2 n= x-+-y-+z- ≤ x-+ y-+ z-≤ n +1 xyz+1 yz xz xy 2

Последнее верно, иначе $yz + zy ≥ x,$ что возможно лишь при $z = 1$ и $x= y.$ Но тогда

2x2+ 1= n(x2+ 1),

значит, $1 <n < 2$ — противоречие.

Следовательно, $n≤ 2,$ но и $n =1 =12+ 02,$ и $n= 2= 12+ 12$ нам подходят.

Ответ:

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

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

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

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

Докажите, что существуют натуральные числа $a,b,c,d,$ большие $102024,$ такие, что

2 2 2 2 a + b + c+ d = abc+ abd+acd+ bcd.

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

Заметим, что четвёрка (1, 1, 1, 1) является решением уравнения. Будем последовательно строить новые решения $(a,b,c,d),$ увеличивая минимальную переменную, тогда не больше, чем через каждые 4 шага, мы увеличиваем значение минимума, значит, придём к решению, где все переменные больше $2024 10 .$

Пусть на очередном шаге есть решение $(a,b,c,d).$ Не умаляя общности, $a ≤b≤ c≤ d.$ Рассмотрим исходное уравнение как квадратное относительно $a:$

a2 − a(bc+ cd+ bd)+ b2 +c2+ d2 − bcd= 0

Пусть $L$ — второй корень уравнения, тогда по теореме Виета:

L =bc+ cd +bd− a,

значит, $L > a$ и $(L,b,c,d)$ — решение.

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

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

Натуральные числа $a$ и $b$ таковы, что число $a2+-b2- ab− 1$ целое. Докажите, что оно равно $5.$

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

Обозначим

a2+-b2 k= ab − 1 .

По условию $k∈ ℕ.$ Рассмотрим пару $(a,b)$ с минимальной суммой $a+ b$ среди всех решений. Без ограничения общности будем считать, что $a≥ b.$

Запишем уравнение:

a2− kb⋅a+ (b2+ k)=0.

По теореме Виета, если $a$ — корень, то второй корень $′ a$ удовлетворяет:

a+ a′ = kb, aa′ =b2+ k.

Отсюда:

′ ′ b2+k a =kb− a, a = --a--.

Пара $(a′,b)$ также является решением. Из минимальности суммы $a+b$ следует:

2 a′= b-+-k≥ a =⇒ b2+ k≥ a2 =⇒ k≥ a2− b2 ≥ 0. a

Тогда:

a2+ b2 =k(ab− 1)≥ (a2− b2)(ab− 1)= ab(a2− b2)− a2+b2

2a≥ b(a2− b2)= (a − b)(a+ b)b

Случай 1: $a =b.$ Подставим $a =b :$

2a2 =k(a2− 1).

Так как $gcd(a2,a2 − 1)= 1,$ то $a2− 1|2.$ Возможные варианты:

$pict$

Решений нет.

Случай 2: $a >b.$

2a ≥(a− b)(a+ b)b> (a − b)ab =⇒ (a− b)b< 2.

Тогда $b =1,$ $a =2.$

2 2 aab+−b 1-= 5.

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

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

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

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

Подсказка 1.

Попробуем разобрать какой-нибудь простой случай. Пусть n является степенью простого числа. Как тогда можно расположить его делители?

Подсказка 2.

Достаточно просто записать их в порядке возрастания. Теперь попробуем оформить индуктивное рассуждение: как поменяются делители при домножении n на степень нового простого числа?

Подсказка 3.

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

Подсказка 4.

Цепочку, соответствующую одному изначальному делителю, можно поставить подряд, а правильное отношение на стыке цепочек можно получить по предположению индукции.

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

Пусть $n =pα1...pαk, 1 k$ где $p i$ — простые числа. Будем вести индукцию по $k.$ При $k= 1$ запишем ряд $1,p,...,pα.$ Произведём индукционный переход. Пусть для $-n- pαkk$ мы выписали строчку $d1,$ $d2,$ …, $dm.$ Тогда для каждого $di$ создадим цепочку $di,$ $pkdi,$ …, $α pkkdi.$ Цепочки будем чередовать: сначала по возрастанию, потом по убыванию. Тогда получится ряд

d1,pkd1,...,pαkkd1,pαkkd2,...,pkd2,d2,d3,...

Внутри одной цепочки отношение соседних чисел будет $pk,$ а на стыке цепочек отношение будет $d dii+1$ или же $di+1 di-,$ что по предположению индукции является простым числом.

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

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

Докажите, что уравнение $x3− 3y3− 9z3 = 0$ не имеет решений в натуральных числах.

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

Подсказка 1:

Обратите внимание, равенство возможно, только если x кратно 3.

Подсказка 2:

Рассматриваются только натуральные решения. Это значит, что можно попробовать применить каким-то образом принцип крайнего. Подумайте, какой объект для этого стоит рассмотреть.

Подсказка 3:

Например, можно взять сумму переменных и рассмотреть решение с её наименьшим значением. Быть может, получится его уменьшить, используя первую подсказку?

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

Предположим, что решения существуют. Тогда выберем среди них решение $(x,y,z)$ с наименьшей суммой переменных. Очевидно, что $x$ делится на 3. Пусть $x= 3x1.$ Подставим в исходное уравнение:

3 3 3 27x1 − 3y − 9z =0

Рассуждая аналогично, получаем, что $y$ и $z$ делятся на 3. Пусть $y = 3y1,$ $z = 3z1.$ Тогда тройка $(x1,y1,z1)$ также будет решением, что противоречит выбору $(x,y,z).$ Значит, решений нет, что и требовалось доказать.