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

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

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

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

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

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

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

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

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

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

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

Натуральное число $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)

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

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

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

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

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

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

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

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

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

(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.$

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

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

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

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

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

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

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

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

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

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

При любом $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$

Курсы

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

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

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

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

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

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

Любое число $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

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

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

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

Ответ:

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

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

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

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

Подсказка 1

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

Подсказка 2

Складывать квадраты произвольных цифр неудобно, а вот складывать единицы удобно. На этом постройте последовательность, приходящую к какому-нибудь интересному числу.

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

Заметим, что число $4$ интересное, поскольку при операции из условия получаем цикл:

4→ 16→ 37→ 58→ 89→ 145→ 42→ 20 → 4

Теперь построим бесконечное число интересных чисел. Заметим, что, если число $k$ — интересное, то и число, состоящее из $k$ единиц, интересное. Начиная такой процесс с числа $4,$ получим бесконечную возрастающую последовательность интересных чисел.

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

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

Докажите, что существует бесконечно много чисел вида $n2+ 1,$ не имеющих делителей вида $k2 +1,$ кроме $1$ и самого себя.

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

Подсказка 1

Если чисел не бесконечно, то их конечно. Тогда их делителей вида k^2+1 тоже конечно. Как построить число не делящееся на все прошлые делители? Зачем это вообще нужно?

Подсказка 2

Постройте число, которое больше всех чисел не имеющих делители вида k^2+1, а так же не имеющих всех прошлых делителей вида k^2+1.

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

Пусть таких чисел конечно, а $m2 +1$ — больший делитель вида $k2+ 1$ у этих чисел, $l2+ 1$ – наибольшее число не имеющее делителей вида $2 k +1.$ Положим $2 2 2 n= max(m;l),m =(0 + 1)(1 +1)...(n +1).$ Рассмотрим $2 m + 1.$ Оно взаимно просто со всеми числами вида $2 k + 1,$ где $k ≤n,$ а еще больше, чем $2 l+ 1$ — противоречие, значит, таких чисел бесконечно.

Интенсивы

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

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

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

Существуют ли $22024$ различных пар натуральных чисел $(a,b), i i$ таких что

-1-- -1-- ----1---- a1b1 + a2b2 +...+ a22024b22024 = 1

a1+ a2 +...+ a22024 +b1+ b2+...+b22024 = 32025?

Напомним, что пары $(a,b)$ и $(c,d)$ считаются одинаковыми в том и только в том случае, если $a= c$ и $b= d.$ В частности, среди чисел $a1,...a22024,b1,...b22024$ могут быть одинаковые.

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

Подсказка 1

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

Подсказка 2

Сделайте индукцию. База за вами. Идея перехода следующая: пару (a,b) замените на пары (a+b,b) и (a, a+b). Поймите, что пары в ходе такого раздвоения не совпадут.

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

Докажем, что существуют $k= 2n$ таких различных пар $(a ,b),(a ,b ),...(a ,b ), 1 1 2 2 k k$ что

n+1 a1+ a2+...+ak+ b1+b2+ ...+ bk =3

-1--+--1-+ ...+ -1--= 1 a1b1 a2b2 akbk

База $n= 2.$ Подберём

(1 +2+ 1+ 1)+(2+ 2+6 +12)= 27

1 1 1 1 1-⋅2 + 2⋅2 + 1⋅6 + 1⋅12 = 1

Переход $n → n+ 1.$ Каждую пару $(a,b)$ заменим на пары $(a+b,b)$ и $(a,a +b).$

$1)$ Докажем, что все пары различные. Предположим, есть две совпадающих пары. У них обеих либо первые числа больше вторых, либо вторые больше первых. Если первые больше, то пары имеют вид $(a+ b,b)$ и $(c+ d,d).$ Если эти пары равны, то и пары $(a,b)$ , $(c,d)$ равны, а они не были равны по предположению индукции.

$2)$ Докажем, что сумма увеличилась ровно втрое. Это очевидно, так как сумма в двух новых парах равна $3a+ 3b,$ что в три раза больше суммы в старой паре-родителе.

$3)$ Докажем, что сумма обратных величин не изменилась. Действительно,

1- --1--- --1--- ab = (a +b)b + a(a+ b)

Тем самым у новых пар все необходимые условия выполнены. Переход осуществлён.

Ответ:

Существуют

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

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

Докажите, что для любого натурального $n$ число $10n +18n− 1$ делится на $27.$

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

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

База. Пусть $n= 1:$ $10+ 18 − 1= 27$ делится на $27.$

Индукционный переход. Пусть утверждение верно для $n,$ тогда докажем утверждение для $n+ 1.$

Раз $n 10 +18n− 1$ делится на $27,$ то

n 10 ≡1 − 18n (mod 27)

Тогда

n+1 10 + 18(n+ 1)− 1≡ 10(1 − 18n)+18(n+ 1)− 1= 27− 81 ⋅2n ≡0 (mod 27)

Переход доказан. Следовательно, утверждение верно.

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

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

По кругу расставлено $299$ положительных чисел. Могло ли случиться так, что каждое из этих чисел, кроме одного, равно разности своих соседей?

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

Подсказка 1:

Не совсем понятно, как можно доказывать отрицательный ответ. Поэтому стоит придумать пример!

Подсказка 2:

Теперь не совсем ясно, как его придумать. Давайте немного преобразуем условие. Если число равно разности соседей, то какой-то сосед равен сумме двух чисел, стоящих перед ним. Где вы видели что-то подобное?

Подсказка 3:

Попробуйте при построении примера использовать последовательность Фибоначчи.

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

Составим пример с помощью чисел Фибоначчи. Разделим круг на две половины, получится по $149$ чисел в каждой части, и одно число не попадёт никуда. Пусть это число будет равно $F150.$ Его соседи будут равны по $F149,$ их соседи по $F148$ и так дальше. Последнее число в обеих половинах будет равно $F1.$

Ответ:

Да

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

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

Существует ли бесконечная последовательность натуральных чисел, в которой нет двух чисел, одно из которых делится на другое, любая пара членов имеет общий делитель, больший $1,$ но при этом НОД всех чисел последовательности равен $1?$

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

Подсказка 1

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

Подсказка 2

Сделайте так, чтобы каждое число делилось на 6, 10 или 15. Это вам даст условие, что все попарные НОДы больше 1. Как теперь добиться остальных условий?

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

Покажем, что искомая последовательность существует. Пусть $p ,p,... 0 1$ — последовательные простые числа, большие $5.$ Пусть

q3i = 6,q3i+1 =10,q3i+2 = 15

и $s = pq i i i$ для всех целых неотрицательных $i.$ Докажем, что последовательность ${s }∞ ii=0$ удовлетворяет условию задачи.

Во-первых, в последовательности ${s}∞ i i=0$ явно не существует двух чисел, одно из которых делит второе, поскольку $s i$ не делится даже на $p j$ при $i⁄= j.$

Во-вторых, $НОД(si,sj)≥Н ОД(qi,qj),$ каждое из чисел $qi,qj$ лежит в множестве ${6,10,15},$ а значит, их $Н ОД$ больше $1.$

Наконец, осталось показать, что $НОД$ всех чисел последовательности равен $1.$ Действительно, $2∤s2,3 ∤s1,5∤s0,$ и никакое простое число больше $5$ не делит более одного элемента последовательности.

Ответ:

Да, существует

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

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

Существует ли натуральное число $n > 10100$ такое, что десятичные записи чисел $n2$ и $(n+ 1)2$ отличаются перестановкой цифр? (Иначе говоря, в десятичных записях чисел $2 n$ и $2 (n+ 1)$ должно быть поровну цифр 0, поровну цифр 1, …, поровну цифр 9.)

Источники: ВСОШ, РЭ, 2024, 9.10 (см. olympiads.mccme.ru)

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

Первое решение. Заметим, что числа $132 = 169$ и $142 = 196$ получаются друг из друга перестановкой цифр.

Пусть теперь

13014 a= --2--=6507.

Положим

n= 10100⋅a+ 13= 10100⋅6507+ 13.

Заметим тогда, что

$pict$

Иначе говоря, десятичная запись числа $2 n$ состоит из блоков $2 a ,$ $182= 14⋅13$ и $2 169= 13$ (дважды), разделённых нулями; у числа же $2 (n +1)$ эти блоки суть $2 a ,$ $182= 13⋅14$ и $2 196 =14$ (дважды). Поскольку блоки $169$ и $196$ отличаются перестановкой цифр, а блоки $2 a$ и $182$ одинаковы в обоих записях. Также количества разделяющих нулей в обоих случаях одинаковы, получаем, что число $n$ удовлетворяет требованиям.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что нам удалось найти такое число $b$ (возможно, с ведущим нулём), что набор цифр в десятичной записи числа $2b$ отличается от набора цифр в десятичной записи числа $b$ выкидыванием цифры $4$ и добавлением цифры $1$ (иначе говоря, если к числу $b$ приписать единицу, а к $2b$ — четвёрку, то полученные числа отличаются перестановкой цифр). Тогда в качестве числа $n$ можно выбрать $n =5 ⋅10d⋅b+ 1$ (где $d >100,$ и $d− 1$ больше количества цифр в числе $2b$ ). Действительно, имеем

$pict$

и мы опять видим, что эти числа состоят из блоков $(1,b,25b2)$ и $(4,2b,25b2),$ разделённых нулями, а блоки получаются друг из друга перестановкой цифр (по условию на $b$ и $2b,$ и так как $25b2$ одинаково в обоих случаях).

Осталось найти такое число $b.$ Если, например, потребовать, чтобы запись числа $2b$ получалась из записи числа $b$ циклическим сдвигом и заменой 4 на 1, то такое число нетрудно найти, выписывая его цифры с конца. Подойдет, например, пара

b= 0526315789473684; 2b= 1052631578947368.

Ответ:

да

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

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

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

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

Дано натуральное число $n> 100.$ Изначально на доске написано число 1. Каждую минуту Петя представляет число, записанное на доске, в виде суммы двух неравных положительных несократимых дробей, а Вася оставляет на доске только одну из этих двух дробей. Докажите, что Петя может добиться того, чтобы знаменатель оставшейся дроби через $n$ минут не превышал $n 2 + 50$ вне зависимости от действий Васи.

Источники: ВСОШ, РЭ, 2024, 11.10 (см. olympiads.mccme.ru)

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

Подсказка 1

Рассмотрим разбиение числа 1 в сумму 2ⁿ различных несократимых дробей вида 1/mᵢ, где mᵢ ≤ 2ⁿ + 50. Можно ли из такого разбиения получить стратегию игры для Пети?

Подсказка 2

Построим двоичное дерево глубины n, где в листьях — эти дроби, а в корне — 1. Каждая внутренняя вершина — сумма двух потомков. При каких условиях это дерево можно использовать в качестве стратегии и гарантирует ли оно нужный результат независимо от выборов Васи?

Подсказка 3

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

Подсказка 4

Докажите ключевую лемму: если есть две четверки попарно различных чисел, их можно разбить на четыре пары (по одному числу из каждой четверки) так, чтобы: числа в парах были различны, суммы пар были различны. Попробуйте доказать разбором случаев, учитывая возможные равенства между четверками.

Подсказка 5

При каких условиях на начальные 2ⁿ дробей можно воспользоваться данной леммой для построения дерева? Очевидно, что среди начальных дробей должно быть хотя бы 4 различных вида дробей, и каждого из них не более 2ⁿ⁻² штук.

Подсказка 6

Очевидный способ для одного представления: возьмите 2ⁿ⁻² дробей вида 1/2ⁿ. Может, поискать представления так же вида 1/m?

Подсказка 7

Для иных представлений: зафиксируем k, где n−k — составное и не степень двойки. Какими k для этих целей можно ограничиться? В этом случае n−k = pt, где t > 1 и нечетно. Правда ли, что тогда 2ⁿ⁻ᵏ + 1 делится на 2ᵖ?

Подсказка 8

Можно ли представить ¼ в виде суммы дробей 1/(2ⁿ + 2ᵏ) и (2ᵏ⁺ᵖ+2ᵏ)/2ᵏ⁺ᵖ·(2ⁿ + 2ᵏ) в правильных пропорциях?

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

Построим двоичное дерево глубины $n$ со значениями в вершинах, следующим образом: представим $1$ в виде суммы $2n$ дробей с числителями $1$ и знаменателями, не превосходящими $n 2 +50,$ поместим данные дроби в листьях; значения остальных вершин это сумма их потомков (следовательно в корне будет $1$ ). Если у каждой вершины (кроме, разумеется, листьев) значения потомков различны, то такое дерево соответствует победной стратегии Пети: каждое число из дерева записывается в виде суммы значений потомков, а Вася, выбирая одно из них, осуществляет спуск по дереву. Через $n$ минут они спустятся в один из листов, то есть будет записана одна из исходных дробей.

Теперь покажем, что такое дерево существует, для этого докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Есть 2 четвёрки чисел

a1 >a2 > a3 > a4 и b1 >b2 > b3 > b4.

Тогда их можно сгруппировать по парам $(ai,bj),$ чтобы числа в каждой паре были различны и суммы чисел в каждой паре были различны.

Доказательство. Разберем несколько случаев:

$∘ 1.$ $a1 = b1,$ $a2 = b2.$ Если $a4 ⁄= b4,$ не умаляя общности $a3 ≥b3$ и можно сгруппировать

a1+b2 > b1+ a3 >a2+ b3 > a4 +b4.

В случае $a =b 4 4$ и н.у.о. $a ≥ b 3 3$ группируем

a1+b2 > b1+ a3 >a2+ b4 > b3+ a4.

$2∘.$ $a3 = b3,$ $a4 = b4$ сводится к предыдущему, если мы перейдем к четверкам чисел $− ai,−bi.$

$3∘.$ Пары $(a1,b1)$ и $(a2,b2)$ разные, а также пары $(a3,b3)$ и $(a4,b4)$ разные. В таком случае покажем как сгруппировать числа первых двух пар между собой, с числами в третьей и четвертой паре поступим аналогично, явно получив две меньшие суммы чем в первой паре. Если $a1 = b1$ или $a2 =b2$ подходит $a1 +b2,$ $a2+ b1,$ в противном случае можно сгруппировать $a1+ b1$ и $a2+ b2.$

Покажем, что описанное в начале решения дерево существует (значения потомков на каждом шаге — различные числа), если исходные $2n$ дробей удастся разбить на четверки так, чтобы в каждой четверке были попарно различные дроби. Действительно, в таком случае на очередном шаге мы разобьем четверки на пары и согласно лемме будем складывать числа из разных четверок. После каждого такого шага получившиеся суммы вновь будут разбиваться на четверки попарно различных чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Построив снизу вверх так первые $n − 2$ уровня дерева, мы в итоге получим четверку различных чисел

x1 <x2 <x3 < x4,

далее рассмотрим вершины со значениями(и соответствующими потомками) $x + x 1 2$ и $x + x, 3 4$ и последнем шаге сложим уже эти два числа, получив $1$ в корне.

Таким образом, достаточно представить $1 4$ в виде суммы $n−2 2$ дробей вида $1- m$ четырьмя разными способами, каждый раз используя разные знаменатели, не превосходящие $n 2 + 50.$

Первый способ — сумма $n−2 2$ одинаковых дробей $-1 2n.$ Построим три других представления. Заметим, что среди чисел

n,n − 1,n− 2,n − 3,n− 4,n − 5

не более одной степени двойки и не более двух простых чисел (потому что простые числа, большие трех, могут давать только остатки 1 и 5 от деления на 6), уберем такие числа из рассмотрения. Любое оставшееся число можно представить в виде $n − k =pt,$ где $p,t>1$ и $t$ нечетно. Тогда $n−k 2 + 1$ кратно $p 2 +1,$ обозначим частное от деления через $q.$ Получаем, что

n k k p 2 +2 = 2 (2 + 1)q.

Возьмем $2n−2− 2k+p−2$ дроби вида $--1-- 2n+2k$ и $2k+p−2$ дроби вида $--1--. 2k+p⋅q$ Поскольку $k≤ 5,$ то

2k+p⋅q < 2n +2k < 2n+ 50.

Посчитаем сумму этих дробей:

n−2 k+p−2 k+p−2 ( n k+p k p ) 2---−n-2-k-- + 2k+p---= 1 2-n− 2-k-+ 2-(2n-+-1k) = 1. 2 + 2 2 ⋅q 4 2 + 2 2 + 2 4

Проделаем так для трех различных значений $k,$ остается убедиться, что полученные представления не содержат одинаковых дробей. Ясно, что с первым выбранным набором три новых не пересекаются, а также дроби вида $-n1k- 2 +2$ могут быть лишь в одном наборе. Остается проверить, что дроби вида $-k1+p 2 q$ различны. Предположим противное, $2k+pq = 2k1+p1q1.$ Поскольку $q$ и $q1$ нечетны, получаем, что $q =q1,$ и это число — общий делитель $2n+ 2k$ и $2n+ 2k1.$ Тогда $2k − 2k1$ кратно $q,$ поэтому $q <32.$ Однако,

n-− k p= t < n∕3,

откуда $p n∕2 2 + 1< 2$ и $n q >2 ∕2> 32,$ противоречие.

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

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

Дано натуральное $n >2.$ Маша записывает по кругу $n$ натуральных чисел. Далее Тая делает такую операцию: между каждыми двумя соседними числами $a$ и $b$ она пишет некоторый делитель числа $a+ b,$ больший 1; затем Тая стирает исходные числа и получает новый набор из $n$ чисел, стоящих по кругу. Всгда ли Тая может выполнять операции таким образом, чтобы через несколько операций все числа оказались равными?

Источники: ВСОШ, ЗЭ, 2024, 10.8 (см. olympiads.mccme.ru)

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

Подсказка 1

Предположим, все числа в круге одинаковой чётности. Что можно сказать о чётности суммы любых двух соседних чисел?

Подсказка 2

В случае, когда все числа нечётные, Тая может победить. Можно ли какие-либо ситуации свести к данной?

Подсказка 3

Допустим, что ни одна сумма соседних чисел не является степенью двойки, как свести данную ситуацию к нечётным числам?

Подсказка 4

Пусть среднее арифметическое s всех чисел не является степенью двойки. Рассмотрим операцию: заменить каждое число на сумму соседей. Можно ли с её помощью уравнять числа в круге?

Подсказка 5

Лемма: После k таких операций числа становятся близки к s · 2ᵏ. Для любого ε > 0 при достаточно большом k все числа попадут в интервал (s − ε)·2ᵏ, (s − ε)·2ᵏ). Как выбрать ε, чтобы этот интервал не содержал целых степеней двойки?

Подсказка 6

Если в наборе есть пара (a, b) с суммой a + b = 2ᵏ (k ≥ 2), мы можем выбрать для неё делитель либо 2, либо 4.

При выборе 2 новое среднее s₁

При выборе 4 новое среднее s₂ = s₁ + 2/n
Почему числа s₁ и s₂ не могут одновременно быть степенями двойки? Может ли Тая победить в данной ситуации?

Подсказка 7

Что делать, если в начальном наборе есть 1?

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

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

(1) Пусть у нас $n$ нечётных чисел. Тогда за одну операцию можно получить $n$ двоек.

(2) Пусть никакая сумма двух соседних чисел не является степенью двойки. Тогда за одну операцию можно получить ситуацию (1).

(3) Пусть среднее арифметическое $s$ всех чисел не равно степени двойки. Покажем, что сможем прийти к ситуации (2). Воспользуемся следующей леммой.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $a1,$ $a2,$ …, $an$ — вещественные числа, $s$ их среднее арифметическое. За один ход меняем набор $a1,$ $a2,$ …, $an$ на

a +a a + a a +a 1-2-2,-22--3,...,-n-2-1.

Тогда для любого $𝜀 >0$ через несколько ходов все числа будут лежать в интервале $(s− 𝜀,s+ 𝜀).$

Доказательство леммы. Сделаем переобозначения, пусть

s+x0,s+x1,...,s+xn

— данные числа, так что

x0+ ...+ xn = 0.

Пусть

M =max{|x0|,...,|xn|}.

Ясно, что после хода $M$ не увеличится. Достаточно понять, что через некоторое количество $k$ ходов этот максимум отклонения станет не более $λM$ для некоторого фиксированного $0< λ< 1.$ Ниже увидим, что можно положить $k= n$ и $λ = 2n−nn−1. 2$

Через $n$ ходов у нас будет набор $s+ y0,$ $s +y1,$ …, $s+yn,$ где

-1 ( 1 2 n−1 ) y0 = 2n x0+ Cnx1+ Cnx2+ ...+ Cn xn−1 +xn и т.д.

Так как

x0+ x1+ ...+xn =0,

имеем

1 2 n− 1 1 2 n−1 x0+ Cnx1+ Cnx2+...+Cn xn−1+ xn = (Cn− 1)x1+ (Cn− 1)x2+ ...+ (Cn − 1)xn− 1.

Отсюда

|y|≤ -1((C1 − 1)+ ...+ (Cn−1− 1))M = 2n− n-− 1M. 0 2n n n 2n

Аналогично все

2n−-n−-1 |yi|≤ 2n M,

что завершает доказательство леммы.

_________________________________________________________________________________________________________________________________________________________________________________

Ясно, что $s >1.$ Выберем $𝜀> 0$ так, чтобы интервал ( $s− 𝜀,s +𝜀$ ) целиком помещался между соседними степенями двойки:

2t−1 < s− 𝜀<s +𝜀< 2t

для некоторого натурального $t.$ Будем проводить много раз операцию замены пары соседей на их сумму. Тогда, согласно лемме, найдётся $N$ такое, что после $N$ операций все числа будут лежать в интервале

N N (2 (s− 𝜀),2 (s+ 𝜀)),

а значит, в интервале между соседними степенями двойки $2N ⋅2t−1$ и $2N ⋅2t.$ Значит, после $(N − 1)$ операции выполнялось условие (2).

(4) Пусть все числа не меньше 2. Если мы не в ситуации (2), то есть пара соседей $a,b,$ сумма которых равна $2t,$ где $t≥ 2$ — натуральное. Попробуем сделать следующую операцию произвольно, только $a$ и $b$ заменим на число 2. Пусть в такой попытке мы не пришли в ситуацию (3), то есть получили ситуацию, в которой среднее арифметическое $s$ равно степени двойки. Тогда сделаем другую попытку, в которой все пары меняются так же, только $a$ и $b$ заменяются на 4. По сравнению с первой попыткой $s$ увеличилось на $-2 n ,$ поэтому мы окажемся в ситуации (3).

(5) Пусть набор исходных чисел произвольный. Тогда после одной операции замены пары чисел на сумму имеем ситуацию (4).

Ответ:

да

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

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

Пусть $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.$

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

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

Дана последовательность $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