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

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

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

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

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

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

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

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

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

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

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

Задача 1#85914

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

5m2−-n n2+ 3m =1

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

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

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

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

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)$ нам подходят.

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

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

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

Задача 2#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.$

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

Задача 3#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$ .

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

Подсказка 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), но для всех меньших мы доказали. Что осталось написать по этой задаче? Является ли это полным решением?

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

Возьмём число $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

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

Задача 4#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

Ответ: да

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

Задача 5#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.$

Ответ: да

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

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

Ответ: нет

Курсы

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

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

Задача 7#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)$ может быть взят многочлен с целыми коэффициентами.

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

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

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

Задача 8#75793

Даны различные натуральные числа $a ,a,...,a . 1 2 n$ Рассматривают всевозможные выражения вида $aa + a a ij k l$ для различных $i,j,k,l.$ Выбрано $m$ из этих выражений, значения которых равны $b1,b2,...,bm$ (эти числа не обязательно различные). Оказалось, что не существует $i⁄= j$ и $k⁄= l$ таких, что $bk+ bl$ делится на $ai+ aj.$ Найдите наибольшее возможное значение $m.$

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

Оценка. Выберем произвольные $i,j,k,l.$ Рассмотрим все $b, t$ образованные этими четырьмя числами. Если таких $b t$ хотя бы 2 (не нарушая общности, $aiak+ajal$ и $aial+ajak$ ), то их сумма будет равна $(ai+ aj)(ak +al),$ то есть будет делиться на $ai+ aj$ — противоречие. И значит, каждые 4 числа образуют вместе не более одного $ct.$ Тогда всего чисел не более $4 Cn.$

Пример. Будем строить пример индукцией по $n.$ Выберем $a1 =100,a2 = 40001 ⋅2023.$ Если уже построены $a1,a2,...,ak,$ то выберем $∏ 2 ak+1 = 2023 1≤i,j≤k(ai+aj) +1,$ а также добавим к ранее выбранным $b$ -шкам все выражения вида $aiaj +atak+1$ для $1 ≤i< j < t<k +1.$ Легко понять, что после построения $ak+1$ будет построено ровно $4 Ck+1$ $b$ -шек. Предположим, что после построения $ak+1$ нашлось выражение $bi+bj,$ делящееся на $at+ al$ для некоторых $1 ≤t< l≤ k+1.$

Пусть $bi = ai1ai2 +ai3ai4$ , $bj =aj1aj2 + aj3aj4.$ Тогда получаем, что выражение

ai1ai2 + ai3ai4 +aj1aj2 + aj3aj4

делится на $at+ al.$ Посмотрим на это выражение по модулю $at+ al.$ Заметим, что $ar ≡ 1 (mod at+al)$ при $r >l,al ≡ −at (mod at+al).$ Тогда, заменив в выражении выше все $au$ при $u≥ l$ по данным правилам, мы получим новое выражение, равное сумме произведений нескольких $ai$ -ых. При этом в каждом произведении будет не более $2$ $a$ -шек, а также индексы всех $a$ -шек будут меньше $l.$ Заметим, что полученное выражение по модулю меньше $al$ (что следует из построения $al$ через предыдущие числа). Тогда новое выражение может делиться на $at+ al$ только если оно равно $0.$ Выберем в этом выражении $ax,$ имеющее наибольший индекс. Вынесем его за скобки из тех слагаемых, в которых оно есть. Если суммарный коэффициент перед ним не равен $0,$ то $ax$ «перебьет» все остальные слагаемые, а значит, наше выражение не будет равно $0.$ То есть суммарный коэффициент перед $ax$ должен быть равен $0.$ При этом, если в коэффициенте снова выделить $ay$ с наибольшим индексом, и не будет такого же $ay$ с противоположным знаком, то по аналогичным соображениям коэффициент перед $ax$ не будет равен $0.$ Тогда $ay$ обязаны сократиться между собой. То есть в коэффициенте перед $ax$ останутся только единицы, чего опять же не может быть. Наконец, если рассмотреть в выражении все слагаемые, не содержащие $ax,$ и выбрать там $az$ c наибольшим индексом, то по аналогичным соображениям коэффициент перед ним должен быть равен $0.$

То есть мы доказали, что наше выражение имеет вид $ax(au − au)+ az(av− av)$ (где $x$ может быть равен $z$ ). При этом $x> u,$ и $z >v.$ Заметим, что в слагаемых со знаком минус один из индексов обязан быть равен $t.$ Посмотрим, с каким слагаемым было $axau$ в одной и той же $b$ -шке (до замены по модулю). Очевидно, что оно может быть в паре с $− axau$ (так как до замены по модулю эта слагаемые точно имели общий индекс, чего не может быть). Также $axau$ не могло быть вместе с $azau$ (эта слагаемые не изменялись, а сейчас имеют общий индекс $l$ ). Значит, изначально $axau$ было в паре с $− azav.$ Вспомнив, что слагаемое $− azav$ изначально было со знаком $+,$ и один из его индексов был равен $l>x,$ получаем, что и второй индекс ( $z$ или $v$ ) строго больше $x,$ чего не может быть, так как $x$ был выбран как наибольший индекс после замены по модулю.

Таким образом, мы показали, что очередной шаг нашего построения корректен. Значит, после построения $an$ мы целиком построим требуемый пример.

Ответ:

$C4 n$

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

Задача 9#75792

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

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

Одно такое $a$ найти легко: например $a= 8$ и $a+ 1= 9$ оба достойны внимания. Будем последовательно строить новые пары достойных внимания соседних чисел. Пусть $a$ и $a+ 1$ такие. Тогда пара $4a(a +1)$ и $2 4a(a+ 1)+1 =(2a+ 1)$ тоже достойны внимания. Так мы последовательно найдем бесконечно много пар нужных нам соседних чисел.

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

Задача 10#75788

Докажите, что существует возрастающая последовательность натуральных чисел $a,a ,a,... 1 2 3$ такая, что для любого натурального $n$ число $a1a2...an+ 1$ делится на $a1 +a2+ a3+ ...+an.$

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

Построим искомую последовательность индукцией по $n.$ В качестве базы для $n= 2$ положим $a =1,a = 2, 1 2$ несложно убедиться, что в этом случае последовательность удовлетворяет условию. Пусть существует искомая последовательность $n−1 {ai}i=1.$ Пусть $a1...an−1 = x,a1+...+an−1 = y,$ тогда $x+ 1$ кратно $y.$ Теперь достаточно показать, что существует натуральное число $z$ такое, что $xz+1$ кратно $y+z.$ Покажем, что $z =(x− 1)y − 1$ удовлетворяет последнему. Действительно тогда

xz+ 1= x((x− 1)y − 1)+ 1= x(xy− y− 1)+ 1= x2y− xy− x +1 =

= (xy− 1)x − (xy− 1) =(xy− 1)(x− 1)

$y+z =xy− 1,$ тогда условие кратности выполнено. Кроме этого $z =(x− 1)y − 1> y,$ поскольку $x >3$ уже при $n =3,$ а значит полученная последовательность является возрастающей.

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

Задача 11#74878

Последовательность натуральных чисел $a,a ,a ,... 1 2 3$ удовлетворяет условию $0 <a − a ≤ 2001 n+1 n$ при всех $n ≥ 1.$ Докажите, что существует бесконечное число пар $(p,q),$ для которых $ap$ делится на $aq.$

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

Разумеется, если $(a ) n n$ удовлетворяет условию задачи, то и $(a ) n+k n$ тоже для всех натуральных $k$ (символом $(a ) f(n)n$ в литературе обозначают последовательность $af(1),af(2),...$ ). Поэтому достаточно найти одну пару $p> q$ в последовательности $(an)n$ такую, что $. ap.. aq$ – далее можно рассмотреть последовательность $(an+p)n ,$ найти в ней пару элементов $. ap1 .. aq1$ и так далее. Отметим, что среди любых $2001$ последовательных чисел, первое из которых не меньше $a1,$ хотя бы одно является элементом последовательности. Теперь, рассмотрим таблицу

a1+ 1 a1+ 2 ... a1+2001 a1 +1+ x1 a1+ 2+ x1 ... a1+2001+ x1 a1+1 +x1+ x2 a1+ 2+ x1+ x2 ... a1+ 2001+ x1+ x2 .. .

где

20∏01 20∏01 20∏01 x1 = (a1+ i), x2 = (a1+ i+x1), x3 = (a1+ x1+x2+ i) i=1 i=1 i=1

и так далее. Отметим, что если два числа $x,y$ находятся в одном столбце и $x >y$ , то $.. x . y.$ Действительно, по индукции нетрудно доказывается, что любое $xi$ делится на все элементы таблицы в строчках $1,...,i,$ поскольку каждое $xi$ есть произведение всех элементов в $i$ -ой строке. При этом $x − y$ является суммой нескольких $xi,$ каждое из которых находится в строчке с большим индекcом, чем $y,$ значит $x− y ... y.$

Рассмотрим теперь первые $2002$ строчки таблицы. По замечанию, в каждой из них есть хотя бы один элемент последовательности, причем, поскольку любые две строчки не пересекаются по элементам, все они различны. Согласно принципу Дирихле, существует столбец, в котором находятся хотя бы два элемента последовательности. По доказанному, один из них делится на другой, что и требовалось.

Интенсивы

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

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

Задача 12#74426

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

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

Начнём с числа $9,$ и будем добавлять числа слева по одному так, чтобы выполнялись условия задачи. Пусть у нас уже есть ряд из нескольких чисел, удовлетворяющий условию задачи, и пусть в нём первое число кратно $9.$ Обозначим его $9m.$ Добавим в начало ряда квадрат числа из $m$ девяток (в частности, в первый раз добавим $81$ ). Покажем, что оно удовлетворяет условиям. Добавленное число имеет вид $m 2 2m m (10 − 1)= 10 − 2⋅10 + 1.$ Если вычесть из $2m 10 + 1$ число $m 2⋅10$ в столбик, будет очевидно, что сумма цифр числа $m 2 (10 − 1)$ равна $9m.$ То есть мы смогли добавить в начало ряда новое число. Будем добавлять так до тех пор, пока не получим ряд из $10$ чисел.

Ответ:

Да, могут

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

Задача 13#74424

Палиндром — это натуральное число, которое читается одинаково слева направо и справа налево (например, $1,343$ и $2002$ — это палиндромы, а $2005$ — нет). Некоторый палиндром увеличили на $110,$ и сумма снова оказалась палиндромом. Сколько цифр могло быть в записи исходного палиндрома?

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

Для $1,2$ и $4$ цифр нетрудно придумать примеры $1,11,1001.$ Для большего количества цифр индукцией по $n$ покажем, что число вида $10999 ...901$ ( $n$ девяток) подходит. В справедливости базы убедиться несложно. Предположим, что это верно для такого числа с $n$ . Это означает, что при прибавлении $1$ к $n$ девяткам на следующий разряд после последней $9$ переходит $1.$ Но тогда если в числе $n +1$ девятка, то единица перейдёт в последнюю девятку, от которой в следующий разряд с $0$ перейдёт $1$ и будет число вида $1100...011$ ( $n+ 1$ ноль).

Покажем, что трёх цифр быть не могло. Предположим, что нашлось такое число $--- x= aba,$ что $x+ 110$ — палиндром. Ясно, что последняя цифра $x+ 110$ равна $a,$ значит и первая равна $a.$ Если число $x +110$ трёхзначное, то такого быть не может, потому что цифра сотен будет явно больше $a.$ Предположим, что $x+ 10$ — четырёхзначное. Предположим, что при сложении $x$ и $110$ не было переноса с второго разряда на третий. В этом случае число $x+ 110$ будет четырёхзначным только если $a= 9,$ но тогда оно точно не палиндром. Предположим, что с второго разряда на третий перенесли $1,$ тогда $x+ 110$ будет четырёхзначным, если $a= 9,8.$ В обоих случаях $x+ 110$ не палиндром.

Ответ:

Любое натуральное число кроме $3$

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

Задача 14#74423

(a) Придумайте набор из $10$ различных натуральных чисел, сумма которых делится на каждое из них.

(b) Существует ли такой набор из $100$ чисел?

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

Докажем индукцией по $n ≥3,$ что можно придумать такой набор из $n$ чисел.

База. Для $n= 3$ возьмём набор $1,2,3.$

Переход. Пусть у нас есть $n> 3$ чисел, удовлетворяющих условию, в качестве $n+ 1$ -го возьмём их сумму. Нетрудно проверить, что такой набор из $n+ 1$ чисел удовлетворяет условию.

Пример для первого пункта: $1,2,3,6,12,24,48,96,192,384.$

Ответ:

$b)$ Да

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

Задача 15#71011

Дана последовательность $a,b ,a ,b,...,a,b 1 1 2 2 k k$ , состоящая из $0$ и $1.$ Пусть $N$ — количество чисел $i$ от $1$ до $k$ таких, что $a = 0 i$ и $bi = 1.$ Докажите, что число последовательностей указанного вида, для которых $N$ нечетно, находится по формуле $2k−1 k−1 2 − 2 .$

Источники: Верченко-2022 (см. v-olymp.ru)

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

Подсказка 1

В задаче есть параметр k, учитывая который строятся последовательности. Увеличив k, несложно построить новую последовательность, не "сломав" старую. Попробуем решить задачу индукцией по k! Докажем, что если утверждение выполняется при k-1, но оно выполняется и при k.

Подсказка 2

Если последовательность из 2k элементов удовлетворяет условию, то какой тогда будет эта последовательность без последнего пары a_k, b_k? Что будет с четностью N?

Подсказка 3

Нам подходят такие последовательности длины 2(k-1), где N четно, а_k = 0 и b_k = 1. А если N нечетно, то какой может быть пара (a_k;b_k)?

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

Применим метод математической индукции по параметру $k$ . При $k= 1$ формула очевидна. Докажем, что если она верна при $k − 1$ , то верна и при $k.$

Искомое число равно числу последовательностей

a1,b1,a2,b2,...,ak−1,bk−1,

(1)

в которых количество $i= 1,2,...k− 1,$ таких, что $ai = 0$ и $bi = 1$ четно (в этом случае пара $(ak,bk)$ может быть только $(0,1))$ плюс количество последовательностей вида (1) в которых количество чисел $i= 1,2,...k− 1,$ таких, что $ai = 0$ и $bi = 1$ нечетно, умноженному на 3 (так как пара $(ak,bk)$ может быть любой из пар $(0,0),(1,0),(1,1)).$ В итоге по предположению индукции нужное число последовательностей будет удовлетворять равенству

( ( )) ( ) 22(k−1)− 22(k−1)−1 − 2k−2 + 3 22(k−1)−1− 2k−2 =22k−1− 2k−1

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

Задача 16#64856

Пусть $n,m > 2$ — натуральные числа. Докажите, что $2n+ 1$ не делится на $2m − 1.$

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

Подсказка 1

Предположите, что n > m. Тогда можно попробовать разделить первое выражение на второе в столбик. Что тогда останется неизменным в записи выражения?

Подсказка 2

Верно, неизменной будет структура записи: вместо того, чтобы доказать кратность числа 2^n+1, мы будем доказывать кратность числа 2^(n-m)+1. И тогда задача будто повторилась, а значит нам нужно посмотреть, что будет, если n <= m, и связать эти два вывода

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

Кратность $2n +1$ эквивалентна кратности $2n−m + 1$ числу $2m− 1$ в силу соотношения $2n +1 =2n−m + 1+2n−m ⋅(2m − 1).$

Тогда мы можем переходить от $n 2$ к $n−m 2$ сколько угодно раз. Такие переходы закончатся, когда $n$ станет меньше $m,$ но если это так, то $n m 2 + 1< 2 − 1$ (не считая случая $m ≤ 2,$ который исключается условием), откуда кратности быть не может. Значит, её быть не может и для произвольного $n.$

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

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

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

Задача 17#88186

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

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

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

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

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

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

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

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

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

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

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

2 0< n − 87n+ 1970

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

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

Задача 18#88185

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

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

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

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

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

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

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

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

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

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

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

Задача 19#88180

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

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

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

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

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

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

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

тогда имеем:

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

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

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

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

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

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

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

Задача 20#88178

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

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

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

Предыдущий раздел

Следующий раздел