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

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

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

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

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

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

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

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

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

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

Задача 1#104691

Можно ли расставить все натуральные числа от 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

Докажите, что для любого натурального $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

Петя выписал на доску два числа: сначала $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

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

Назовём натуральное число ровным, если в его записи все цифры одинаковы (например: 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

Множество $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ₖ делит:

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

Назовём множество $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

Докажите, что для каждого натурального $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

Последовательность ${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

Про натуральные числа $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:

Подсказка 3

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

Подсказка 4

В случае 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

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

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

Подсказка 1

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

Подсказка 2

Составим квадратное уравнение, где a — корень:

Подсказка 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

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

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

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

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

Подсказка 1

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

Подсказка 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

Дано натуральное число $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

Рассмотрим соотношение:

Подсказка 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

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

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

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

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

Подсказка 1

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

Подсказка 2

Рассмотри многочлен:

Подсказка 3

x₂ = bc − a или x₂ = (b² − d)/a

Подсказка 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

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

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

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

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

Не умаляя общности, пусть $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

Докажите, что уравнение $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

Пусть $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

Докажите, что существуют натуральные числа $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

Натуральные числа $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#77056

Дано выражение $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$ будет иметь целые коэффициенты.

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

Задача 20#77252

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

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

Предположим, что нашлись такие натуральные $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 бесконечное число раз.

Ответ: нет