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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: нет

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

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

Ответ: да

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

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

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

Задача 6#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,$ чтд.

Курсы

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

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

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

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

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

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

Задача 9#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$ можно получить любое натуральное число, заключаем, что все натуральные числа являются удачными.

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

Задача 10#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$ единиц, причём в частном будет число в записи которого ровно три единицы, а остальные цифры нули. Тогда наше число делит тройку, в степени на один большую, чем число из предположения индукции. Это и требуется, переход доказан.

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

Задача 11#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.$ Переход доказан.

Интенсивы

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

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

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

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

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

Задача 13#90320

Натуральное число $N$ делится на число $10101010101.$ Докажите, что в десятичной записи $N$ по крайней мере $6$ цифр отличны от $0.$

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

Подсказка 1

Начать логично, рассмотрев маленькие N, то есть 12-значные. Можем ли мы как-то разумно описать вид таких чисел?

Подсказка 2

Действительно, такие числа имеют вид abababababab, в них, очевидно, есть 6 ненулевых цифр a. Тогда давайте будем доказывать утверждение индукцией по величине N, базу доказали. Теперь придумаем, как будем делать переход.

Подсказка 3

Итак, пусть у нас теперь есть N, а для всех меньших утверждение доказали. Можно сделать следующее: вычеркнуть первую цифру и добавить её на 12 разрядов ниже. Осталось понять, что будем использовать в качестве числа, для которого выполняется предположение индукции и почему в N ненулевых цифр больше чем в нём.

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

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

База индукции: для $N$ состоящих из $12$ цифр очевидно, что делящееся на $101010101010$ должно иметь вид $abababababab,a$ не равно $0,$ поэтому база доказана.

Индукционное предположение: пусть для чисел меньше либо равных $N$ доказано, что в десятичной записи хотя бы $6$ цифр отличны от $0.$

Индукционный переход: докажем утверждение для следующего кратного $101010101010,$ то есть для $S = N +101010101010.$ Пусть $---------- S =a1a2...ak+1.$ Вычеркнем первую цифру и прибавим её же на $12$ разрядов ниже. Полученное число будет меньше исходного, ведь мы вычли из $S$ число $k−1 k−13 a1⋅(10 − 10 ).$ В скобках стоит произведение $k−13 12 10 (10 − 1),$ второй сомножитель не делится на $101010101010,$ следовательно на него делится и разность. Теперь заметим, что в получившемся числе ненулевых цифр не больше, чем в исходном.

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

Задача 14#94036

Докажите тождество

(n−-1)n(n+-1) 1 ⋅2 +2⋅3+ ...+ (n − 1)⋅n= 3

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

Подсказка 1

Такие тождества удобно доказывать по индукции. База очевидна. Будем полагать, что при n = p утверждение верно. Как свести доказываемое утверждение при n = p+1 к предположению индукции?

Подсказка 2

Верно! Сумма, в которой последнее слагаемое получается при n = p + 1 содержит в себе сумму всех слагаемых для n = p. Как тогда применить предположение?

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

Первое решение. Попробуем телескопировать эту сумму. Для этого надо выразить $k(k+ 1)$ как разность двух выражений, похожих на то, что должно получиться в ответе. Заметим, что $k(k+1)(k+2)−(k−1)k(k+1) k(k+ 1)= 3 .$ Тогда

n∑−1 n∑−1 k(k+ 1)= 1 (k(k+ 1)(k+ 2)− (k− 1)k(k+ 1))= (n−-1)n(n+-1) k=1 3k=1 3

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. При $n= 2$ в левой части получаем $1⋅2,$ а в правой $1⋅2⋅3 =2, 3$ так что равенство выполнено. Предположим, что равенство верно при $n= p,$ то есть

p∑−1 p−∑1 k(k +1)= 1 (k(k+ 1)(k+ 2)− (k− 1)k(k+ 1))= (p−-1)p(p-+1) k=1 3k=1 3

Тогда при $n= p+ 1$ имеем

p∑ p∑−1 k(k+ 1) = 1 (k(k +1)(k +2)− (k − 1)k(k+ 1))+ p(p +1)= (p−-1)p(p-+1)+ p(p+ 1) k=1 3 k=1 3

после вынесения за скобки $p(p +1)$ и преобразований получается

(p−-1)p(p+-1) p−-1+-3 p(p-+1)(p+-2) 3 +p(p+1)= p(p +1) 3 = 3

Шаг индукции доказан. Значит, утверждение задачи выполнено при любых натуральных $n ≥2.$

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

Задача 15#94049

Докажите тождество

3 3 3 2 1+ 2 + ...+ n =(1+ 2+ ...+ n).

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

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

База. Пусть $n= 1:$ $\text{[math]}$ $3 2 1 = 1 .$ Тождество верно.

Переход. Пусть для $n$ и меньших значений всё доказано, докажем для $n+ 1.$

3 3 3 3 2 1 + 2 + ...+n +(n+ 1) ? (1+2 +...+ n+ (n+ 1))

3 3 3 3 2 1◟-+2-+◝◜...+-n◞+(n+ 1) ? (1 +2+ ...+ n+ (n +1)) (1+2+...+n)2

(n(n+ 1))2 3 ( (n+ 1)(n+ 2))2 ---2--- +(n+ 1) ? -----2-----

Умножим обе части на 4 и поделим на $(n+ 1)2 ⁄= 0:$

n2+ 4(n+ 1) ? (n+ 2)2

n2+4n +4 = (n+ 2)2

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

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

Задача 16#94051

Докажите, что число, состоящее из $3n$ единиц, делится на $3n.$

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

Докажем индукцией по $n.$ Проверим базу $n= 1:$ $111$ делится на $3$ по признаку делимости.

Теперь докажем переход. Пусть $1◟1.◝3.◜n.1◞$ делится на $n 3,$ тогда

3n 2⋅3n 1◟1..◝◜.1◞= 1◟1..◝◜n.1◞1◟1.◝◜n..1◞1◟1.◝◜n..1◞= 1◟1.◝◜n..1◞⋅(1+ 10 +10 )= 3n+1 3 3 3 3

=11...1⋅10...010...01 ◟-◝3◜n-◞ ◟3 ◝n◜− ◞1 ◟3 ◝n◜− ◞1

Заметим, что $10◟. ◝.◜.0 ◞10◟..◝◜.0◞1 3n−1 3n−1$ делится на 3 по признаку делимости, тогда $1◟1.◝..◜1 ◞ 3n+1$ делится на $3n+1.$ Переход доказан, следовательно, утверждение верно.

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

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

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

Задача 17#94058

При любом $n$ найдите сумму (упростите выражение до вида без многоточий и знаков суммирования):

1 2 2 2 n−12 1 − 2 +3 − 4 + ...+(−1) n.

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

Посчитаем, чему равна сумма для $n,$ равного $1,2,3,4,5:$

12 =1 12 − 22 = −3 2 2 2 12 − 22+ 32= 62 12 − 22+ 32− 42= −120 1 − 2 + 3 − 4 + 5 = 15

Внимательно рассмотрев вычисления для малых значений $n,$ можно предположить, что сумма для любого $n$ равна

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

Докажем это с помощью индукции.

База. Для $n =1$ мы уже проверили выше.

Переход. Пусть формула верна для $n,$ докажем её для $n+ 1.$ По предположению индукции

n(n +1) 12− 22 +32− 42+...+(−1)(n−1)n2 =(−1)(n−1)--2----

Запишем сумму для $n+ 1:$

12− 22+ 32− 42 +...+ (−1)(n−1)n2+ (−1)n(n+ 1)2 =(−1)(n−1)n(n-+1)+ (−1)n(n+ 1)2 2

Случай 1: Пусть $n$ нечётное, тогда

n(n-+1)- 2 ( n) (n-+1)(n-+2)- − 2 + (n +1) = (n +1) n+ 1− 2 = 2

Случай 2: Пусть $n$ чётное, тогда

n(n +1) ( n ) (n+ 1)(n+ 2) --2---− (n+1)2 = −(n+ 1)n +1 −2 = −-----2-----

Формула суммы для $n +1$ выполняется, значит, индукционное предположение доказано.

Ответ:

$(−1)(n−1)⋅ n(n-+1) 2$

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

Задача 18#94059

Докажите, что число $(2+ √3)n+ (2 − √3)n$ целое при любом натуральном $n.$

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

Докажем это индукцией по $n.$ Проверим базу индукции при $n= 1:$

√ - √ - (2 + 3)+ (2− 3)=4

Теперь докажем переход, пусть утверждение верно для всех $n ≤ k,$ тогда рассмотрим

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

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

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

Получается,

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

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

Из индукционного предположения следует, что $√- k+1 √-k+1 (2+ 3) +(2− 3)$ является целым числом. Значит, переход доказан, утверждение верно.

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

Задача 19#94060

Любое число $x,$ написанное на доске, разрешается заменить либо на $3x +1,$ либо на $[x]. 2$ Докажите, что если вначале написано число $1,$ то такими операциями можно получить любое натуральное число.

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

Будем доказывать по индукции по натуральным числам.

База для $n= 2:$ $[4] 1→ 3⋅1+1 =4 → 2 = 2.$

Переход:

Докажем, что если мы умеем получать любое число от 1 до $n,$ то сможем получить и $n+ 1.$ Рассмотрим остаток при делении $n+ 1$ на 3:

Пусть $n+1$ представимо в виде $3k+ 1.$ Так как по предположению индукции мы умеем получать $k$ $(0<k < 3k +1= n +1),$ то остаётся только заменить $k$ на $3k +1.$

Пусть $n+1$ представимо в виде $3k.$ Тогда по предположению мы умеем получать $2k,$ так как $0 <2k <3k= n+ 1.$ Остаётся выполнить следующие преобразования:

[ ] 2k→ 3⋅2k +1= 6k+ 1→ 6k+-1 = 3k 2

Пусть $n+1$ представимо в виде $3k+ 2$ . Тогда по предположению мы умеем получать $2k+ 1$ , так как $0< 2k+1 <3k+ 2= n+ 1$ . Остаётся выполнить следующие преобразования:

[6k+-4] 2k +1→ 3 ⋅(2k+ 1)+1= 6k+ 4→ 2 = 3k+ 2

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

Задача 20#94061

Докажите, что для любого натурального числа $n$ существует натуральное число, составленное из цифр $1$ и $2$ , кратное $n 2 .$

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

База для $n = 1:$ $2..21. .$ Тождество верно.

Будем доказывать более сильное утверждение: для любого $n$ существует число ровно из $n$ цифр (все цифры — 1 или 2), кратное $n 2 .$ База проверена.

Переход: $n→ n +1$

По предположению существует $n−$ значное число $A$ такое, что $.. n A.2 .$ Рассмотрим два случая:

Случай 1. Пусть $.. n+1 A .2 .$ Допишем 2 в начало числа $A :$

--- 2A = A+ 2⋅10n

Так как каждое из слагаемых кратно $2n+1,$ то и сумма будет кратна $2n+1.$ Значит, $2A-$ — искомое $(n+ 1)−$ значное число.

Случай 2. Пусть $.. n+1 A ⁄.2 .$ Допишем 1 в начало числа $A :$

--- n 1A = A+ 1⋅10

Так как каждое из слагаемых кратно $2n$ и не кратно $2n+1,$ они имеют вид $2np,$ где $p$ — нечётное. Тогда при их сложении можно вынести $2n,$ а в скобках сумма двух нечётных даст чётное, следовательно, $1A--$ будет кратно $2n+1.$ Значит, $1A-$ — искомое $(n+ 1)−$ значное число.

Ответ:

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

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