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

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

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

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

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

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

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

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

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

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

Задача 61#74423Максимум баллов за задание: 7

(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)$ Да

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

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

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

Задача 62#74424Максимум баллов за задание: 7

Палиндром — это натуральное число, которое читается одинаково слева направо и справа налево (например, $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$

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

Задача 63#74878Максимум баллов за задание: 7

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

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

Задача 64#75788Максимум баллов за задание: 7

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

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

Задача 65#75792Максимум баллов за задание: 7

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

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

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

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

Задача 66#75793Максимум баллов за задание: 7

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

Курсы

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

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

Задача 67#91038Максимум баллов за задание: 7

Даны натуральные числа $m$ и $n$ и два набора попарно различных вещественных чисел $a,...,a 1 m$ и $b ,...,b . 1 n$ Какое наименьшее количество различных чисел может встретиться среди $mn$ всевозможных сумм $ai+ bj?$

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

Докажем оценку на $m+ n− 1$ индукцией по $n.$ База при $n= 1$ очевидна. Пусть у нас есть числа $a < a <...<a 1 2 m$ и $b1 < b2 < ...< bn+1.$ Выкинем $bn+1.$ По предположению среди всевозможных сумм есть хотя бы $m +n − 1$ различных. Вернём $bn+1$ и рассмотрим сумму $am + bn+1.$ В силу упорядочивания $am + bn+1 > ai+ bj$ для любых $i$ и $j,$ следовательно мы нашли ещё одну сумму и теперь их $m +(n+ 1)− 1,$ доказали.

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

am +bn >am +bn−1 > ...> am +b1 > am−1+ b1 > ...> a1 +b1

Ответ:

$m + n− 1$

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

Задача 68#91039Максимум баллов за задание: 7

Несколько детей собрали поровну шишек. Время от времени какие-то дети раздают каждому из остальных поровну из своих шишек. После многократного повторения такой процедуры у Маши осталось $23$ шишки, а у Коли — $6$ шишек. Сколько было детей?

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

Докажем индукции, что разность количеств шишек у любых двух детей всегда делится на количество детей. В самом начале это очевидно. Пусть после какого-то шага количества шишек у детей равны $a1,a2,...,an$ ( $n$ — количество детей) и $ai− aj$ кратно $n$ для всех $i,j.$ На следующем шаге $i$ -й ребёнок раздаст всем по $x$ шишек. Теперь количества шишек у детей равны

a1+ x,a2+ x,...,ai−1+ x,ai− (n − 1)x,ai+1+ x,...,an+ x

Заметим, что $a + x− (a +x)= a − a , k m k m$ то есть кратно $n.$ Также $a + x− (a − (n − 1)x)=a − a +nx, k i k i$ что тоже кратно $n.$ Доказали.

Таким образом, $23− 6 =17$ кратно количеству детей. Ясно, что есть хотя бы $2$ ребёнка, поэтому всего их $17.$

Ответ:

$17$

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

Задача 69#94302Максимум баллов за задание: 7

Докажите, что существует бесконечно много троек различных натуральных чисел $a,b,c >106$ таких, что любые два из них можно выписать друг за другом (в каком-то порядке) так, чтобы полученное число было точным квадратом.

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

Подсказка 1

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

Подсказка 2

Оказывается есть пример связанный со степенями 10 кратными 11. Пусть 11^k+1 = 121*d. Возьмите в качестве одного числа, равное d, а второе, равное 100d. Поймите, что, выписав их подряд, вы получите квадрат. Как подобрать третье число?

Подсказка 3

Подберите магическим образом третье число так, чтобы получались квадраты чисел x и 10x^2. Третье число выписывайте первым.

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

Заметим, что $1011k+ 1=121⋅d,$ где $k− нечетное.$ Выберем $c= d,b= 100d.$ Заметим, что в десятичной записи числа $d$ ровно $k− 2$ цифр. Тогда, если выписать сначала число $b,$ а потом число $c,$ то получим $k−2 2 2 100d⋅10 +d =d ⋅121= (11d).$ Обозначим через $11k−2 1011k+1 x =10 + 11 .$ Выберем

x2− c a= 1011k−2

Заметим, что полученное число не будет равно $b$ и $c,$ при этом оно будет целым так как $x2− c$ дает остаток

22k 11k 11k 11k 10--+-2⋅10--+-1−-10---− 1-= 1011k⋅ 10-+-1≡ 0 (mod 1011k−2) 121 121

При этом, если записать подряд числа $a$ и $c,$ то получим $10k−2⋅1x0211−kc−2 + c= x2.$ Если же записать подряд числа $a$ и $b,$ то получим $1011k⋅-x211−kc−2 + 100c= (10x)2. 10$

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

Задача 70#41306Максимум баллов за задание: 7

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

2n n+2 n 5 + 3 + 3

делится на $11.$

Источники: ОММО-2022, номер 1, (см. olympiads.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Сильнее других выбивается 5^2n. При этом мы рассматриваем выражение по модулю 11(так как хотим, чтобы на 11 делилось выражение). Как исправить 5^(2n), чтобы оно имело такой же вид, как и другие слагаемые?

Подсказка 3

Рассмотреть сравнение 5^2 = 3(mod 11). В таком случае можно возвести сравнение в степень n и подставить в изначальное выражение, то есть заменить 5^(2n) на выражение с тем же остатком по модулю 11

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

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

Поскольку $2 5 ≡113$ , то по модулю $11$ имеем

n n n n 3 + 9⋅3 + 3 = 11⋅3 ≡11= 0

_________________________________________________________________________________________________________________________________________________________________________________

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

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

База: Если $n =0,$ то $52n+ 3n+2 +3n =50+ 32+30 = 11$ — делится на $11.$

Переход: Предположим, что при $n = k$ число $52n +3n+2+ 3n = 52k+ 10⋅3k$ делится на $11,$ и докажем, что при $n= k+ 1$ число $52n+ 3n+2 +3n = 52k+2 +10⋅3k+1$ также делится на $11.$ Заметим, что

( ) 52k+2+10⋅3k+1 = 3⋅ 52k+ 10⋅3k + 22⋅52k

Первое слагаемое в правой части делится на $11$ по предположению индукции, а второе — потому что содержит множитель $22.$ Значит, и вся сумма делится на $11.$ Переход доказан.

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

Задача 71#72040Максимум баллов за задание: 7

Решите уравнение

2 2 x + y +1= 6xy,

где $x$ и $y$ — натуральные числа.

Источники: Межвед-2022, 11.8 (см. www.academy.fsb.ru)

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

Подсказка 1

У нас есть уравнение второй степени относительно x и y в натуральных числах. В таких случаях бывает полезно рассмотреть его как квадратное относительно одной из переменной. Что мы можем сказать про это уравнение относительно x?

Подсказка 2

Если y- натуральное число, то все коэффициенты этого уравнения целые числа. Тогда, чтобы x был целым, необходимо, чтобы четверть дискриминанта была полным квадратом. Может ли такое быть?

Подсказка 3

D/4=8y²-1. Тогда должно существовать целое t такое, что t²=8y²-1. Какие тогда ограничения, связанные с остатками, накладывается на t?

Подсказка 4

t² должен давать остаток -1 при делении на 8. Но может ли такое быть? Переберите квадраты всех остатков при делении на 8 и убедитесь, что это невозможно!

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

Пусть пара натуральных чисел $(x ,y ) 0 0$ удовлетворяет исходному уравнению

2 2 x + y +1 =6xy

(1)

Тогда

1.

Положив $x0 = y0 =a$ и подставив в $(1),$ получим

2a2+ 1= 6a2

Очевидно, что $a ∕∈ ℕ$ . Поэтому $x0 ⁄= y0$ . Без ограничения общности можно считать, что в этой паре $x0 >y0$ . Будем это записывать как $max(x,y )=x . 0 0 0$

2.

По условию, число $x0$ является корнем многочлена

f(x)=x2− 6y0x +y2+ 1 0

(2)

По теореме Виета, этот многочлен еще имеет корень $x2,$ причем

{ x2+ x0 = 6y0 x2x0 = y20 +1

Отсюда следует, что $x2 = 6y0− x0$ и $x2 ∈ ℕ.$ Поэтому уравнение $(1)$ имеет еще одно решение в натуральных числах $(6y0− x0,y0)$

Это означает, что для многочлена $(2)$ справедливы равенства

f(x0)= f(6x0 − y0)= 0

Заметим, что

f(y0)= y20 − 6y20 + y20 + 1< 0

Поэтому число $y0$ лежит между корнями многочлена $(2),$ а именно:

x0 >y0 >6y0− x0

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

max(6y0− x0,y0)= y0 < max(x0,y0)

Итак, для любого решения $(x0,y0)$ существует другое решение, у которого максимальный элемент окажется меньше. Таким образом, мы можем строить новые решения, у которых максимальный элемент становится все меньше. Но при этом этот максимальный элемент, постоянно уменьшаясь, остается натуральным числом, что невозможно. Пришли к противоречию. Значит, исходное уравнение $(1)$ решений в натуральных числах не имеет.

Ответ: решений нет

Интенсивы

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

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

Задача 72#74468Максимум баллов за задание: 7

Докажите, что существует бесконечное множество троек натуральных чисел $x,y,z,$ удовлетворяющих соотношению $x2+y2 = z2022.$

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

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

Подсказка 1

Что напоминает данное равенство?

Подсказка 2

Пифагорову тройку! Степени четны, быть может, стоит попробовать как-то преобразовать самую привычную пифагорову тройку?

Подсказка 3

Чтобы не потерять связь с тройкой (3, 4, 5,, попробуем подставить «подобную ей» вместо х, у и z. Хочется сделать так, чтобы z^2022 было равно 25t^2 при некотором t. Как это сделать?

Подсказка 4

Z должно делиться на 5. Получается, что вместо z нужно взять 5n, а остальные числа подогнать под равенство не составит труда)

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

Возьмем пифагорову тройку, например, $(3;4;5),$ и будем рассматривать соотношения

2 2 2 (3t) + (4t) =(5t)

для различных натуральных $t.$ Если положить

2 2 2 2 2022 2 x = 9t ,y =16t,z = 25t ,

то взяв число $z,$ делящееся на 5, т.е. $z =5n$ для натурального $n,$ получим

25t2 = 52022n2022 ⇔ t= 51010n1011

Таким образом, при любом натуральном $n$ числа вида $x= 3t,y = 4t,$ где $t= 51010n1011,$ и $z = 5n$ удовлетворяют исходному уравнению.

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

Задача 73#76736Максимум баллов за задание: 7

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

2 2 2 n(2n-+1)(n-+1) 1 +2 + ...+ n = 6

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

Подсказка 1

Давайте сначала проверим равенство для маленьких значений n=1, 2. Всё сходится. Запишите переход индукции для n. Что же теперь будет, если записать сумму для n+1 слагаемого?

Подсказка 2

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

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

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

База:

1⋅3⋅2 1 = --6--

Переход:

n(2n +1)(n +1) 12 +22+ ...+ n2 =-----6------ =⇒

12+ 22+...+n2+ (n+ 1)2 = n(2n+-1)(n+-1) +(n+ 1)2 = 6

=(n+ 1)2n2-+7n+-6-= (n+-1)(2(n+-1)+1)((n-+1)+-1) 6 6

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

Задача 74#76737Максимум баллов за задание: 7

На доске в ряд написаны числа 1, 1. За ход между соседними числами на доске вписывается их сумма. Докажите, что после хода номер $n$ сумма всех чисел на доске будет равняться $n 3 + 1$ .

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

Подсказка 1

Давайте попробуем перебрать маленькие значения n и для базы индукции, и для того, чтобы примерно понять, откуда возникает формула. Теперь пусть на n-ом шаге всё хорошо. Пронаблюдайте переход от n к n+1. Сколько раз считаются наши числа?

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

Докажем индукцией по номеру хода.

База при $n= 1$ очевидна.

Переход: Пусть на $n$ -м шаге записаны числа $1;a1;a2;...;ak;1$ . Их сумма равна $n 3 + 1$ , а значит $n a1 +a2+ ...+ ak = 3 − 1$ . Сделаем следующий шаг, тогда каждое $ai$ в новой сумме будет учитываться трижды, а крайние единицы — дважды, а значит сумма имеет вид:

2(1+ 1)+ 3(a1+ a2+ ...+ ak)= 4+ 3n+1− 3 =3n+1+ 1

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

Задача 75#76738Максимум баллов за задание: 7

Известно, что число $x+ 1 x$ — целое. Докажите, что $xn+ 1- xn$ — также целое при любом целом $n$ .

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

Подсказка 1

Выражение какое-то очень знакомое… Возможно, мы умеем выражать число, которое нам надо найти, по-другому?

Подсказка 2

Да, можно выразить его через числа такого же вида, но с меньшей степенью! Например, посмотрите на произведение: (x+1/x)*(xⁿ + 1/xⁿ). В таком случае, чем будет пользоваться при доказательстве?

Подсказка 3

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

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

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

Сделаем это по индукции.

База: при $n =0,n= 1$ утверждение верно.

Переход: Пусть $n 1- x + xn$ и $n−1 -1-- x + xn−1$ целые, тогда заметим, что $n+1 -1-- 1 n 1- n−1 -1-- x + xn+1 = (x+ x)(x + xn)− (x + xn−1)$ , а значит $n+1 -1-- x + xn+1$ является целым как разность целых чисел.

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

Задача 76#76740Максимум баллов за задание: 7

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

2 2 2 (1+ x1)(1+ x2)...(1+ xn)

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

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

Подсказка 1

Ясно, что одну скобку мы можем представить в виде суммы квадратов, ведь её слагаемые это два квадрата. А про две скобки, можно ли их разложить в сумму двух квадратов?

Подсказка 2

Да, две скобки тоже можно! Давайте предположим, что n-1 скобку можно разложить в сумму двух квадратов… То есть, воспользуемся индукцией! И действовать будем точно также, как и в случае с двумя скобками!

Подсказка 3

Верно, мы прибавим и вычтем число, чтобы получилась сумма и разность квадратов!

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

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

База:

2 2 2 1+ x1 = (1) +(x1)

Переход:

2 2 2 2 2 (1 +x1)(1+ x2)...(1 +xn−1)= a +b =⇒

2 2 2 2 2 2 2 2 2 2 2 2 2 (1+ x1)(1+ x2)...(1+ xn−1)(1+ xn) =(a + b)(1+ xn)= a +a xn+ b +b xn =

= a2 +2abx +b2x2+ b2 − 2abx +a2x2= (a+ bx )2+ (b− ax )2 n n n n n n

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

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

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

Задача 77#76741Максимум баллов за задание: 7

Дан отрезок $[0;1]$ . За ход разрешается разбить любой из имеющихся отрезков точкой на два новых отрезка и записать на доску произведение длин этих двух новых отрезков. Докажите, что ни в какой момент сумма чисел на доске не превысит $1 2$ .

Источники: Турнир городов - 2022, осенний тур, базовый вариант, 11.5

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

Подсказка 1

Давайте попытаемся понять, как выглядит сумма чисел на доске в общем виде. Начнём разбивать наш отрезок и записывать числа. На втором разбиении попробуйте заменить один из отрезков на сумму двух. У вас получится просто сумма попарных произведений всех длин. Как тогда наша сумма будет выглядеть в общем виде? Докажите это по индукции.

Подсказка 2

Верно, в итоге, у нас получится сумма всевозможных попарных произведений отрезков. База понятна, а дальше нужно по аналогии в сумме заменить длину вновь разбитого отрезка через сумму двух новых. Отлично, с этим справились! Заметим, что нам известна сумма всех отрезков. Как можно выразить теперь сумму попарных произведений для удобной оценки?

Подсказка 3

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

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

Пусть через $n$ шагов мы поделили отрезок на отрезки $x ,x,...,x 1 2 n$ . Индукцией по $n$ покажем, что сумма чисел, записанных на доске, равна сумме всевозможных попарных произведений чисел $x1,x2,...,xn$ .

База очевидна.

Переход: Пусть на $n−$ шаге сумма равна $x1x2+ ...+ xn−1xn$ . На $n+ 1$ -м шаге мы делим $i$ -й отрезок на отрезки $a$ и $b$ , тогда сумма примет вид:

x1x2+ ...+ xn−1xn+ (a+ b)(x1+ x2+...+xn)+ ab

В данном случае $xx + ...+ x x 1 2 n−1n$ — попарные произведения чисел $x,x ,...,x 1 2 n$ без $x i$ , а $x + x + ...+x 1 2 n$ — сумма этих же чисел без $xi$ . Таким образом, на $n+ 1$ -м шаге также получили всевозможные попарные произведения.

Тогда задача свелась к тому, что нужно доказать, что сумма всевозможных попарных произведений чисел меньше $1 2$ , если их сумма равна $1$ , а это следует, например, из того, что:

(x1+ x2+...+xn)2− (x2+ x2+...+x2) x1x2+ ...+xn−1xn =----------------2--1---2------n- =

2 2 2 = 1−-(x1+-x2+-...+xn)-< 1. 2 2

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

Задача 78#81859Максимум баллов за задание: 7

Докажите, что из множества ${0,1,...,3n− 1}$ можно выбрать $2n$ чисел, никакие три из которых не образуют арифметическую прогрессию.

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

Подсказка 1

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

Подсказка 2

Пусть по предположению индукции для n можно выбрать какие-то 2ⁿ чисел. Нужно их как-то размножить, чтобы получить вдвое больше чисел и притом, мы умели объяснять, что не образовалось арифметической прогрессии из трёх чисел. Отметим, что наша граница теперь увеличена примерно в 3 раза.

Подсказка 3

Тогда можно, например, рассмотреть такой набор чисел: выбранные, умноженные на три и выбранные, умноженные на три, минус два. Осталось пояснить, почему не образовалось арифметической прогрессии.

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

Докажем утверждение задачи индукцией по $n.$ База для $n =1$ верна: можно взять числа $1$ и $2.$ Пусть мы умеем выбирать $2n$ чисел $n a1,a2,a2$ среди чисел $n {0,1,...,3 − 1}$ с выполнением требуемого условия. Рассмотрим числа $n 3a1,3a2,...,3a2$ и числа $3a1− 1,3a2− 1,...3a2n − 1.$ Заметим, что новые $n+1 2$ чисел различны, и все они не превосходят $n+1 3 − 1.$ Предположим, что среди этих чисел некоторые три образуют арифметическую прогрессию. Тогда два из них давали одинаковый остаток при делении на $3.$ Но тогда и третье число обязано давать тот же остаток при делении на $3.$ Если это были числа $3x,3y,3z,$ то тогда бы и числа $x,y,z$ образовывали бы арифметическую прогрессию, что противоречит выбору $a1,a2,...,a2n.$ Аналогично получаем противоречие, если все три числа дают остаток $2$ при делении на $3.$

Значит, новые выбранные числа нам подходят. Переход доказан.

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

Задача 79#83912Максимум баллов за задание: 7

$P$ — некий полином с целыми коэффициентами, $A$ и $M$ — целые числа. Построим последовательность $a n$ , где $a = A 1$ , и $a =P (a) n+1 n$ и пусть $rn$ — остаток от деления $an$ на $M$ .

1. Пусть $P(x)= x2+ x+ 1,A = 1,M = 32022$ . Докажите, что период последовательности $rn$ (то есть, такое наименьшее $t$ , что $rn+t = rn$ при достаточно больших $n$ ) равен 2.

2. Найдите длину предпериода той же последовательности (то есть такое наибольшее $n$ , что $an+t ⁄= an$ , где $t$ — период).

3. Назовем полином стабильным по модулю $M$ , если существует $B$ , такое что для любого $A$ найдется $k$ , для которого $rk = B$ . Докажите, что полином $3 2 f = x − x − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Докажите, что многочлен $P (x)= x2− 3x +12$ стабилен для бесконечного числа натуральных $M$ .

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

Пункт 1, подсказка 1

Если мы докажем, что с какого-то момента a_(n+2) - a_n = a_(n+1) - a_(n-1) (mod 3^2022), то и требуемое тоже будет доказано. Попробуйте выразить a_(n+2) - a_n через a_(n+1) и a_(n-1).

Пункт 1, подсказка 2

Мы получаем, что если a_(n+1) - a_(n-1) делится на 3^k, то и a_(n+2) - an делится на 3^k. Теперь, если мы докажем, что a_(n+1) - a_(n-1) делится на 3^(k+1), то сможем сказать, что с какого-то момента k станет >= 2022. Попробуйте для этого доказать, что a_(n+1) и a_(n-1) имеют одинаковые остатки при делении на 3.

Пункт 1, подсказка 3

Для этого посмотрите на значение a_n по mod 3.

Пункт 2, подсказка 1

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

Пункт 2, подсказка 2

Отлично! Теперь мы знаем, что остатки от деления a_n на 9 и на 27 зацикливаются. Тогда, зная, что степень вхождения 3 в выражение a_(n+1) - a_(n-1) каждый раз растёт, попробуйте вывести рекуррентную формулу для этой степени вхождения.

Пункт 2, подсказка 3

Если v_n - степень вхождения 3 в a_(n+1) - a_(n-1), то v_2 = 1, v_3 = 2, v_(2k+1) = v_2k + 2 и v_(2k+2) = v_(2k+1). Теперь осталось лишь решить неравенство v_k < 2022.

Пункт 3, подсказка 1

Нам нужно определить такое B, чтобы для него нашлось A, такой, что ни один r_k не равен B. Сразу сделать это довольно трудно. Попробуйте для начала подставлять небольшие A и посмотреть на значения полинома.

Пункт 3, подсказка 2

Отлично! Мы знаем, что f(2) = 2. Очень удобно будет доказывать, что есть такое A, что не будет остатка 2, ведь M - квадрат нечётного числа. Осталось лишь подобрать такое A и доказать, что r_k никогда не равен 2. Попробуйте найти A так, чтобы в нём как слагаемое присутствовало q (M = q^2).

Пункт 3, подсказка 3

Можно взять A = 2 + k*q (k и q взаимно просты). Теперь попробуйте рассмотреть f(A) по mod M.

Пункт 4, подсказка 1

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

Пункт 4, подсказка 2

Так, теперь мы знаем, что для 7 многочлен стабилен. Тогда попробуем доказать, что это верно и для 7^k. Легче всего сделать это по индукции. База уже есть, осталось доказать переход. И победа!

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

1. Легко видеть, что остатки $an$ от деления на 3 чередуются с периодом 2 (1, 0, 1, 0, . . .) поэтому период остатков по модулю $M = 32022$ тем более не равен 1.
Покажем что он равен 2.
Заметим, что $an+2 − an =a2n+1− a2n−1+an+1− an−1 = (an+1− an−1)(an+1+ an−1 +1)$
Отсюда следует, что если $an+1 − an−1$ делится на $3k$ , то тем же свойством обладает и $an+2− an$ , а если вдобавок $an+1$ , $an−1$ дают остаток от 1 деления на 3, то $an+2 − an$ делится на $3k+1$ .
Учитывая, что такая ситуация имеет место при каждом четном $n$ , получаем, что соответствующее $k$ может неограниченно увеличиваться, в частности, $an+2− an$ делится на $32022$ при некотором $n= n0$ (а значит и при всех $n >n0$ ). Поэтому период $rn$ равен двум.

2. Выпишем остатки от деления $an$ на 9 и на 27: легко убедиться, что это 2-периодические последовательности $1,3,4,3,4,...$ и $1,3,13,21,13,21,...$ соответственно.
Поэтому число $(an+1+ an−1+ 1)$ не делится на 3 при нечетных $n$ , делится на 3, но не на 9 при $n= 2$ и делится на 9, но не на 27 при четных $n >2$ .
То есть если $v n$ — степень вхождения 3 в число $a − a n+1 n−1$ , то $v = 1 2$ , $v =2 3$ а дальше $v =v + 2 2k+1 2k$ и $v = v 2k+2 2k+1$ .
Отсюда легко видеть, что наибольшее $s$ такое, что $v <2022 s$ равно 2022, то есть $a − a 2023 2021$ — последняя среди разностей вида $an+2− an$ не кратная $M$ .

3. Пусть $M =Q2$ , тогда $Q$ - нечетное число.
Заметим, что $f(2)= 23− 22− 2= 2$ ,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы не получим 2.
Рассмотрим числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$
$f(t)= (2+ kQ)3 − (2+ kQ )2 − 2= Q3k3+ 5Q2k2+8Qk +2$
Нетрудно заметить, что $f(t)≡ 8Qk + 2(mod M )$
То есть числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$ переходят в себя, но число 2 не имеет такого вида, поэтому полином $f = x3− x2 − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Индукцией по $k$ докажем, что для $M = 7k$ многочлен $x2− 3x+ 12$ стабилен.
Обозначим через $a → b$ , то что $P(a)≡b(modM )$
База $k =1$

0→ 5→ 1 → 31 → 3→ 5→ 12 → 3→ 5→ 13→ 5 → 1→ 34→ 2→ 3→ 5→ 15→ 1 → 36 → 5→ 1→ 3

Таким образом, имеем цикл длины 3 везде одинаковый.
Переход $k→ k+ 1$
Пусть по модулю $M = 7k$ многочлен стабилизируется так, что всегда встретится $r$
Тогда по модулю $M = 7k+1$ остаток $r$ будет $7km+ r= r1$
$P (r1)≡r2− 3r+ 12 +7kn(2r− 3)(Mod 7k+1)$ , что не зависит от $n$ , при $0≡ 2r− 3(Mod 7)$
$0 ≡2r− 3(Mod 7)⇔ 5 ≡r(Mod 7)$ , что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю $7k+1$ .

Ответ:

1. что и требовалось доказать

2. 2021

3. что и требовалось доказать

4. что и требовалось доказать

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

Задача 80#88177Максимум баллов за задание: 7

Докажите, что для любого натурального $n$ число $23n +1$ делится на $3n+1,$ но не делится на $3n+2.$

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

Подсказка 1

Будем доказывать по индукции. При переходе от n к n+1 показатель степени двойки умножается на 3, то есть это возведение в куб. Можно применить формулу сокращённого умножения.

Подсказка 2

После разложения на сумму кубов получится произведение двух скобок. К одной можно применить предположение индукции, а другую рассмотреть по модулю 9.

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

Докажем по индукции. База при $n = 1$ справедлива. Предположим, что $3$ входит в $23n + 1$ в $n+ 1$ -й степени. Заметим, что

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

Таким образом, достаточно показать, что $(( n)2 n ) 23 + 23 + 1$ делится на $3,$ но не делится на $9.$ Нетрудно понять, что $23n ≡ −1 (mod 9),$ поскольку $23 ≡− 1 (mod 9),$ а значит всё выражение даёт остаток $3$ при делении на $9,$ а значит делится на $3,$ но не делится на $9.$