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

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

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

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

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

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

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

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

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

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

Задача 1#104691

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

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

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

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

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

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

Ответ: нет

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

Задача 5#79612

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

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

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

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

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

Обозначим $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#80738

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

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

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

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

Ответ: да

Курсы

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

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

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

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

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

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

Задача 8#83138

Малая теорема Ферма. Для любого простого $p$ и взаимно простого с $p$ числа $a$ верно, что $ap−1 ≡ 1$ (mod $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,$ чтд.

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

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

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

Задача 10#85914

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

5m2−-n n2+ 3m =1

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

Источники: ФЕ - 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)$ нам подходят.

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

Задача 11#89081

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

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

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

Интенсивы

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

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

Задача 12#90310

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

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

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

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

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

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

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

Задача 13#90311

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

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

Задача 14#90313

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

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

Докажем утверждение индукцией по $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)

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

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

Задача 15#90320

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

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

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

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

Задача 16#94036

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

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

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

Первое решение. Попробуем телескопировать эту сумму. Для этого надо выразить $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.$

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

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

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

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

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

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

Задача 18#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.$ Переход доказан, следовательно, утверждение верно.