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

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

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

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

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

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

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

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

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

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

Задача 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#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$ будет иметь целые коэффициенты.

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

Задача 10#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 бесконечное число раз.

Ответ: нет

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

Задача 11#79612

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

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

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

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

√- √- b 3+ c 6= 0

b+ c√2= 0

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

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

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

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

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

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

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

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

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

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

Ответ: да

Интенсивы

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

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

Задача 12#80738

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

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

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

Подсказка 1

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

Подсказка 2

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

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

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

Ответ: да

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

Задача 13#82677

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

bm = 1⇒ ∀m > k bm =1

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

Задача 14#83138

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

Задача 15#85458

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

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

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

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

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

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

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

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

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

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

Задача 16#85914

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

5m2−-n n2+ 3m =1

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

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

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

2 2 5m − n = n +3m

______________________________________________________________________________________________________________________________________________________

5m2 − 3m = n2+ n

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

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

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

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

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

x2− 5y2 =4

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Задача 17#89081

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

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

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

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

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

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

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

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

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

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

Задача 18#90310

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

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

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

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

Задача 19#90311

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

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

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

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

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

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

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

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

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

Задача 20#90313

Натуральное число $a$ можно представить в виде $x2− 2y2$ для некоторых целых $x$ и $y.$ Докажите, что для любого натурального $n$ число $n a$ можно представить в таком виде.

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

Подсказка 1

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

Подсказка 2

Давайте сделаем шаг индукции, то есть aⁿ⁺¹ представим в виде произведения двух меньших степеней a, затем воспользуемся предположением индукции.

Подсказка 3

Помочь может следующий факт (x²-2y²)(z²-2t²)=(xz+2yt)²-2(xt+yz)².

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

Докажем утверждение индукцией по $n.$ База индукции собственно в самом условии. Предположение индукции: пусть для $n =k$ утверждение верно, то есть существуют целыe $xk$ и $yk$ такие, что $k 2 2 a = xk− 2yk.$

Переход:

k+1 k 2 2 2 2 a =a ⋅a =(x1− 2y1)⋅(xk − 2yk)=

2 2 2 2 22 22 2 2 =x1xk+ 4y1yk− 2x1yk− 2xky1 =(x1y1+2y1y2) − 2⋅(x1yk+ xky1)

Переход доказан.