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

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

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

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

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

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

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

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

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

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

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

Найдите все тройки попарно взаимно простых натуральных чисел $(a,b,c) (a ≤b≤ c),$ для которых $an +bn+ cn$ делится на $a+b +c$ для всех натуральных $2≤ n≤ 12.$

Источники: Бельчонок - 2020, 11.5 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Сумму n-ых степеней a, b и c стоит попробовать выразить через n-ую степень суммы a+b+c. В связи с этим было бы удобно рассмотреть выражение A(n), которое равно сумме n-ых степеней a, b и c. Можно ли найти связь между A(n), A(n-1) и, возможно, другими A(j) (для некоторых j)?

Подсказка 2

Для A(2) получаем A(2) = A²(1) - 2(ab + bc + ca), при этом A(2) делится на a+b+c если и только если 2(ab + bc + ac) делится на A(1). А какое выражение через A(1) и A(2) получится, скажем, для A(3)?

Подсказка 3

Верно! Получится A(3) = A(1)A(2) - (ab + bc + ac)A(1) + 3abc. Тогда A(3) делится на A(1) тогда и только тогда, когда 3abc делится на A(1). А какое выражение будет для случая произвольного n > 3?

Подсказка 4

Конечно! A(n) = A(1)A(n-1) - (ab+bc+ac)A(n-2) + abcA(n-3). В каких случаях A(n) делится на A(1)?

Подсказка 5

Точно! Необходимо и достаточно, чтобы A(1) было делителем A(2) и A(3). А это верно ровно в тех случаях, которые мы заметили в прошлых подсказках! Тогда нужно найти тройки (a,b,c), обладающие двумя свойствами. Как это сделать?

Подсказка 6

Сначала попробуем исследовать свойства подходящих троек. Напомним, нам необходимо, чтобы 3abc и 2(ab+bc+ac) делились на a+b+c. Может ли тогда a+b+c обладать простым делителем, большим 3?

Подсказка 7

Верно, не может, иначе abc делится на p, поэтому хотя бы одно из чисел a,b,c делится на p (и на самом деле ровно одно в силу взаимной простоты!). Тогда ab+bc+ca не делится на a+b+c! Следовательно, все простые делители a+b+c — это 2 или 3. А может ли a+b+c делиться на 9?

Подсказка 8

Верно, не может, ведь тогда (снова из-за взаимной простоты) ровно одно из чисел a, b, c делится на 3, а потому ab+bc+ca не делится на a+b+c. Рассуждая аналогично, легко прийти к тому, что a+b+c и на 4 не делится. Осталось перебрать всего несколько вариантов чисел a+b+c!

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

Обозначим $A =an+ bn+ cn. n$ Заметим, что $A = A 2− 2(ab+ bc +ac), 2 1$ и $A 2$ делится на $A = a+ b+ c 1$ тогда и только тогда, когда $2(ab+bc+ ac)$ делится на $A1.$ (*)

Аналогично $A3 = A1⋅A2 − (ab+bc+ ac)A1+ 3abc,$ и делится на $A1 = a+ b+ c$ тогда и только тогда, когда $3abc$ делится на $A1.$ (**) Запишем соотношение для $n> 3$ :

An = A1⋅An−1− (ab+bc+ ac)An−2+ abcAn−3.

Отсюда видно, что если $A 1$ — делитель $A , 2$ то $A 1$ — делитель $A , 4$ если $A 1$ — делитель $A 2$ и $A , 3$ то $A 1$ — делитель $A 5$ , $A , 6$ и так далее, то есть делитель $An$ для любого натурального $n.$

Будем искать упорядоченные тройки ( $a,b,c$ ), для которых выполняются условия (*) и (**), то есть $2(ab +bc+ ac)$ и $3abc$ делятся на $a+ b+ c.$ Пусть $a +b+ c$ имеет простой делитель $p≥5.$ Тогда $abc$ делится на $p$ , и в силу взаимной простоты ровно одно из чисел $a,b,c$ делится на $p$ . Но тогда $ab+ bc+ ac$ не может делиться на $p$ , и значит, на $a +b+ c$ . Пусть $a+b+ c$ делится на $2 3$ , тогда $abc$ делится на $3,$ и в силу взаимной простоты ровно одно из чисел $a,b,c$ делится на $3,$ тогда $ab +bc+ac$ не может делиться на $3,$ и значит, на $a+ b+ c$ . Пусть $a +b+ c$ делится на $2 2$ , тогда $abc$ делится на $4,$ и ровно одно из чисел $a,b,c$ , делится на $4,$ тогда $ab+ bc+ac$ нечётное и $2(ab+ bc+ac)$ не может делиться на $4.$ Следовательно, $a+ b+ c$ имеет вид $k m 2 ⋅3 ,$ где $k$ и $m$ принимают значения $0$ или $1,$ при этом $a+b ≥3,$ откуда $3≤ a+ b+c≤ 6.$ Подходят тройки $(1,1,1),(1,1,4).$

Ответ:

$(1,1,1);(1,1,4).$

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

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

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

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

Назовем множество целых чисел $S$ удачным, если для любого натурального $n$ и любых $a ,a,a ,a ,...,a ∈S 0 1 2 3 n$ (не обязательно различных) все целые корни многочлена $n n−1 anx + an−1x +...+ a1x+ a0$ также принадлежат $S.$ Найдите все удачные множества, содержащие все целые числа вида $a b 2 − 2$ для натуральных $a$ и $b.$

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

Ясно, что множество $ℤ$ является удачным. Таким образом, достаточно показать, что любое удачное множество $S,$ содержащее все числа вида $a b 2 − 2$ для любых $a,b∈ ℕ,$ содержит и все целые числа.

Сперва заметим, что $1 1 0 =2 − 2 ∈ S$ и $2 1 2= 2 − 2 ∈ S.$ Теперь $− 1∈S,$ поскольку это корень из $2x+ 2,$ и $1∈ S,$ поскольку это корень из $2 2x − x − 1.$ Кроме того, если $n ∈S,$ то $− n$ является корнем $x+ n,$ поэтому достаточно доказать, что все натуральные числа находятся в $S.$

Теперь мы утверждаем, что любое целое положительное число $n$ является делителем некоторого числа в $S.$ Действительно, пусть $α n =2 ⋅t,$ где $α∈ ℤ≥0$ и $t$ нечетно. Тогда $ϕ(t) t|2 − 1,$ поэтому $α+ϕ(t)+1 α+1 n|2 − 2 ,$ где $ϕ(n),$ как обычно, функция Эйлера. Кроме того, $α+ϕ(t)+1 α+1 2 − 2 ∈ S,$ и поэтому $S$ содержит кратное каждому положительному целому числу $n.$

Теперь по индукции докажем, что все натуральные числа лежат в $S.$ База индукции была доказана ранее. Теперь предположим, что $0,1,...,n−$ $1∈ S;$ более того, пусть $N$ кратно $n$ в $S.$ Рассмотрим разложение $N$ по основанию $n$

N = aknk+ak−1nk−1+ ⋅⋅⋅+a1n+ a0

Поскольку $0≤ ai < n$ для каждого $ai,$ мы получаем, что все $ai$ находятся в $S.$ Более того, $a0 = 0,$ поскольку $N$ кратно $n.$ Следовательно, $aknk+ ak− 1nk−1+ ⋅⋅⋅+ a1n− N = 0,$ поэтому $n$ — корень многочлена с коэффициентами из $S.$ Это говорит нам о том, что $n ∈S,$ завершая индукцию.

Ответ:

Множество всех целых чисел

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

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

Найдите все такие пары натуральных чисел $m$ и $n$ , что $m2019+ n$ делится на $mn$ .

Источники: Лига победителей - 2017, 9 класс (со степенью 2017), Курчатов - 2019, 11.2 (со степенью 2019)

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

Подсказка 1

Сначала не очень понятно, каким должно быть n. Нам интересно именно n, так как оно фиксировано и его степень не меняется. Тогда попробуем понять что-то про n. Для этого посмотрим на выражение, если мы поменяем степень у m.

Подсказка 2

Да, если как-то уменьшать степень у m, то это не особо и меняет картину. А если посмотреть на m + n, при условии, что оно делится на mn? Возможно, отсюда получится вывести общий вид n?

Подсказка 3

Верно, можно действовать по индукции! Причем, индукция будет по степени числа m. Из индукции ясно, что n = km²⁰¹⁹. Остаётся разобраться с тем, каким может быть k

Подсказка 4

Да, k+1 должно делиться на km, из условия задачи. Получается, вариантов не так уж и много, ведь k+1 должно делиться на k, а это возможно только при k = 1.

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

Индукцией по $α$ покажем, что если $m α+ n$ кратно $mn$ , то $n$ представимо в виде $km α$ .

База: если $m +n$ делится на $mn$ , то $n$ делится на $m$ , из этого следует требуемое.

Переход: если $α+1 m + n$ кратно $mn$ , то $n= n1m$ , то есть $α m +n1$ кратно $mn1$ , а по предположению $α n1 =km$ , откуда $α+1 n =km$ .

Теперь, возвращаясь к задаче, имеем: $2019 n = km$ . Тогда условие можно записать в виде: $2019 (k+ 1)m$ кратно $2020 km$ . Таким образом, $k+ 1$ делится на $km$ , это возможно лишь при $k= 1$ и $m = 2$ или $m = 1$ , откуда подходят $m =1,n= 1$ или $2019 m = 2,n = 2$ .

Ответ:

$m = 1,n = 1$ или $m = 2,n =22019$

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

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

Докажите, что существует бесконечно много пар натуральных $p$ и $q$ таких, что $p3+ q3+1$ делится на $pq.$

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

Подсказка 1

Попробуйте рассмотреть какую-нибудь пару, изменив в ней одно число, и получить новую. Так вы построите бесконечную последовательность.

Подсказка 2

На что же можно заменить число в паре? Хочется на что-то удобное. Вот например p^3+1 делится на q, а на что еще делится?

Подсказка 3

Замените взаимнопростые (p,q) на пару ((p^3+1)/q, p). Почему эта пара подходит? Почему мы получили новую пару, а не старую?

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

Рассмотрим пару $(p,q)$ для которой $p3 +q3+ 1$ делится на $pq$ и $(p,q)$ взаимнопросты. Пусть $p≥ q.$ Рассмотрим новую пару $(p3+1- ) q ,p ,$ заметим, что число $p3+1 q$ целое, ведь $3 3 p + q +1$ делилось на $pq,$ то есть

3 3 3 p +q + 1≡ 0 (mod q) ⇐⇒ p +1≡ 0 (mod q)

а еще $p3+1,p q$ взаимнопросты.

Покажем, что новая пара подходит. Действительно

(p3+ 1)3 (1)3 q3+ 1 --q-- + p3+ 1≡ q + 1≡ --q3--≡ 0 (mod p)

( ) p3+1- 3+p3+ 1≡ p3+1 ≡ p3+1-⋅q ≡0 (mod p3+-1) q q q

Мы научились строить новые пары. Осталось лишь найти первую, для нее подойдет $(1,1).$

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

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

Докажите, что существует бесконечно много пар натуральных чисел $(m,n)$ таких, что $(m!)n +(n!)m +1$ делится на $m + n.$

Источники: Жаутыковская олимпиада, 2018

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

Покажем, что пара чисел $(p − 1,(p− 1)!− p+ 2)$ удовлетворяет необходимым условиям при всех простых $p> C,$ где $C$ — фиксированное натуральное число.

Заметим, что $m +n = (p− 1)!+ 1= m!+ 1,$ следовательно

n n (m!) +1≡ (−1) +1 ≡0(mod m!+1)

поскольку число $n = (p− 1)!− p+ 2)$ — нечетно.

Таким образом осталось проверить, что $(n!)m$ кратно $m + n.$ Покажем, что $(n!)2$ кратно $m + n.$ По теореме Вильсона число $m-+-n m!-+1 (p-− 1)!+-1 p = p = p$ является целым. Покажем, что каждое из чисел $m-+-n p, p$ не превосходит $n.$ Действительно $p <(p− 1)!− p+2 =n$ — верно. Так же

(p− 1)!+1< p!− p(p− 2)

p2− 2p+1 <(p− 1)!(p − 1)

(p− 1)2 <(p− 1)!(p− 1)

верно при $p ≥3.$ Наконец, $n!$ кратно $p,n!$ кратно $m-+pn,$ следовательно $(n!)2$ кратно $p ⋅ m+p-n-=m + n,$ что завершает доказательство.

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

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

Докажите, что есть бесконечно много четверок натуральных чисел $(a,b,c,d),$ для которых выполняются равенства $ac− bd =ab+ 1= cd− 1.$

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

Докажем, что четверки вида

(a,b,c,d)= (F2n+2+ F2n,F2n,F2n+1,F2n+1+F2n−1), n∈ ℕ

где $Fn$ — $n$ -ое число Фибоначчи ( $F0 = 0$ , $F1 = 1$ ).

Лемма. Тождество Кассини. $Fn+1Fn−1− Fn2= (−1)n$

Доказательство. $Fn+1Fn−1− F2n = Gn$

Gk+ Gk−1 = (Fk+1Fk−1 − F2)+ (FkFk−2− F2 )= (Fk+1Fk−1− F 2 )+ (FkFk−2− F2)= FkFk−1− FkFk−1 = 0 k k−1 k−1 k

Получаем, $Gk+ Gk−1 = 0.$

$G1 = F2F0− F12= −1.$ Из этого и предыдущего предложения делаем вывод, что для всех нечетных $n$ $Gn = −1,$ а для всех четных — $1,$ что и требовалось доказать.

Вернемся к задаче. Будем доказывать, что $ac− bd =ab+ 1= cd− 1 =F22n +F22n+1.$

$2 2 1) ac− bd− (F2n +F2n+1)= = F2n+2F2n+1+ F2nF2n+1− F2nF2n+1− F2nF2n−1− F22n− F22n+1 = = (F2n+2F2n+1 − F22n+1)− (F2nF2n−1 +F22n)= F2nF2n+1− F2nF2n+1 = 0$

$2) ab+ 1− (F22n+ F22n+1)= = F2n+2F2n+ F2 +1 − F2 − F2 = 2 2n 2n 2n+21n+1 = F2n+2F2n− F2n+1+1 =(−1) + 1= 0$

$3) cd− 1− (F2 + F2 )= 2 2n 2n+12 2 = F2n+1 +F2n−1F2n+1 − 1− F2n− F2n+1 = = F2n−1F2n+1− F22n − 1 =(−1)2n − 1= 0$

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

Курсы

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

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

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

Даны два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $bk− a2$ и $k 2 a − b$ делится на $2018 2 .$

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

Подсказка 1

Попробуйте рассмотреть обобщенную задачу. "Дано натурально число n и два нечетных натуральных числа a и b. Докажите, что существует такое натуральное k, что хотя бы одно из чисел b²ᵏ - a² и a²ᵏ - b² делится на 2ⁿ".

Подсказка 2

Припомните известное утверждение об остатке от деления c²-1 на 2ᵏ⁺², если остаток от деления c-1 на 2ᵏ⁺¹ равен 2ᵏ, где с — некоторое число.

Подсказка 3

Рассмотрим числа a² - 1, которое делится на 2ᵅ и не делится на 2ᵅ⁺¹, и b² - 1, которое делится на 2ᵝ и не делится на 2ᵝ⁺¹. Подумайте, какие ограничения на α и β накладывают приведенные нами условия. Воспользовавшись вышеприведенной леммой, подумайте, какой остаток при делении на 2ᵝ⁺¹ дает число a²ᵐ - 1 (где m = β-α при условии β>α).

Подсказка 4

Примените индукцию по n. Чтобы доказать базу индукции, подумайте, какое число нам подойдет при n ≤ β+1 и почему.

Подсказка 5

Для доказательства шага индукции рассмотрите два случая: когда a²ᵏ - b² делится на 2ⁿ⁺¹ и, соответственно, когда не делится.

Подсказка 6

Если всё ещё испытываете затруднения, положите r = 2ⁿ⁻ᵝ + 1. В очередной раз воспользуйтесь леммой и ответьте на вопрос, какой остаток дает b²ʳ при делении на 2ⁿ⁺¹.

Подсказка 7

Воспользуйтесь формулой разности степеней. Разложив a²ᵏʳ - b²ʳ, Вы получите произведение двух скобок. Оцените делимость какой-либо из них на 2ⁿ⁺¹.

Подсказка 8

a²ᵏʳ - b² = (a²ᵏʳ - b²ʳ) - (b²ʳ - b²). С остатком от деления левой скобки на 2ⁿ⁺¹ разобрались, а что насчёт правой?

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

Будем решать обобщенную задачу. Дано натуральное число $n$ и два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $2k 2 b − a$ и $2k 2 a − b$ делится на $n 2 .$

Воспользуемся следующим известным утверждением: пусть число $c− 1$ дает остаток $k 2$ при делении на $k+1 2 ,$ где $k ≥2.$ Тогда $2 c − 1$ дает остаток $k+1 2$ при делении на $k+2 2 .$

Пусть $2 a − 1$ делится на $α 2$ и не делится на $α+1 2 ,$ а $2 b − 1$ делится на $β 2$ и не делится на $β+1 2 .$ Очевидно, что при этом $α,β ≥ 2.$ Тогда $2 a − 1$ дает остаток $α 2$ при делении на $α+1 2 ,$ а $2 b− 1$ дает остаток $β 2$ при делении на $β+1 2 .$ Пусть $α ≤β,$ положим для краткости $β−α 2 = m.$ По лемме число $2m 22 2 a − 1= (((a) )...)− 1$ даёт остаток $β 2$ при делении на $β+1 2 .$

Будем решать задачу индукцией по $n.$ Если $n≤ β+ 1,$ то нам подойдет $k= m,$ поскольку $2m a$ и $2 b$ дают равные остатки при делении на $2β.$ Сделаем переход от $n$ к $n+ 1.$ По индукционному предположению при некотором $k$ число $a2k− b2$ делится на $2n.$ Если оно делится и на $2n+1,$ то переход сделан. Иначе оно дает остаток $2n$ при делении на $2n+1.$ Пусть $r= 2n−β + 1.$ Тогда по лемме $b2(r−1)− 1$ дает остаток $2n$ при делении на $2n+1.$ Следовательно, $b2r− b2$ дает остаток $2n$ при делении на $2n+1.$ Воспользуемся формулой разности степеней:

a2kr− b2r = (a2k− b2)(a2k(r−1)+ a2k(r−2)b2+ ...+ b2(r−1))

Первая скобка дает остаток $2n$ при делении на $2n+1,$ вторая состоит из $r$ нечетных слагаемых и, значит, нечётна. Стало быть, разность $a2kr− b2r$ дает остаток $2n$ при делении на $2n+1.$ Но тогда $a2kr − b2 = (a2kr− b2r)− (b2r − b2)$ делится на $2n+1,$ поскольку выражения в скобках дают одинаковые остатки при делении на $2n+1.$

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

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

О натуральных числах $x$ и $y$ известно, что $x2$ делится на $2xy +y2− 1.$ Докажите, что $y2− 1$ делится на $2x.$

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

Пусть $x2 = k(2xy +y2− 1)$ при натуральным $k.$ Переписав это равенство в виде

2 2 x − 2kxy = k(y − 1)

заметим, что доказываемое утверждение о делимости $y2− 1$ на $2x$ эквивалентно делимости $x$ на $2k,$ которую и станем доказывать.

Предположим, что $x$ не кратно $2k$ (тогда $y > 1).$ Положим

x1 =x − 2ky, y1 = (4k +1)y− 2x

Очевидно, $x1$ тоже не кратно $2k$ и положительно (потому что $x1 =k(y2− 1)).$ Исключая $k,$ получаем

x = -x(y2−-1)-, y = 2x+-y3− y 1 2xy+ y2− 1 1 2xy +y2− 1

откуда видно, что $y1$ также положительно. Кроме того,

x21 = k(2x1y1+ y12− 1)

то есть $x1$ и $y1$ также удовлетворяют условию задачи.

Продолжая таким образом, мы получим бесконечную убывающую последовательность $x,$ удовлетворяющих условию задачи — противоречие.

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

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

Изначально на доске записаны несколько натуральных чисел (больше одного). Затем каждую минуту на доску дописывается число, равное сумме квадратов всех уже записанных на ней чисел (так, если бы на доске изначально были записаны числа $1,2,2,$ то на первой минуте было бы дописано число $2 2 2 1 + 2 +2$ ). Докажите, что сотое дописанное число имеет хотя бы $100$ различных простых делителей.

Источники: Всеросс., 2017, РЭ, 10.6(см. olympiads.mccme.ru)

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

Подсказка 1

Число 100 в условии намекает на применение индукции. Попробуйте сформулировать утверждение для произвольного n и доказать его именно с помощью индукции.

Подсказка 2

Введём обозначение Sₙ — число, записанное на n-й минуте. Попробуйте выразить Sₙ₊₁ через Sₙ и понять, почему у Sₙ₊₁ появляется как минимум один новый простой делитель.

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

Заменим в условии сто на $n$ и докажем утверждение индукцией по $n.$ Обозначим число, записанное на $n$ -й минуте через $S . n$ Так как $S1 > 1,$ оно имеет хотя бы один простой делитель, то есть база доказана.

Переход. Заметим, что $2 2 2 2 Sn+1 = Sn+ Sn−1+ ...+S1 =Sn +Sn = Sn(Sn+ 1).$ То есть $Sn+1$ делится на все простые делители $Sn$ (по предположению их хотя бы $n$ ), а также оно делится на простой делитель $Sn+ 1,$ отличный от простых делителей $Sn,$ поскольку $(Sn+ 1,Sn)= 1.$ Получили требуемое.

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

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

Среди $99$ натуральных чисел от $1$ до $99$ выбрали $50$ чисел. Известно, что никакие два из них не дают в сумме ни $99,$ ни $100.$ Чему равна сумма выбранных чисел?

Источники: Лига открытий - 2017

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

Разобьём числа на пары, дающие в сумме $100.$ Получим $49$ пар и отдельное число $50.$ Из каждой пары может быть выбрано только одно число, поэтому число $50$ обязательно присутствует. Значит, число $49= 99− 50$ не может быть выбрано, поэтому выбрано парное ему число $51.$ Значит, отсутствует число $48,$ следовательно, присутствует парное ему число $52.$ Продолжая рассуждения, получаем, что выбраны числа $50,51,52,...,99,$ сумма которых равна $3725.$

Ответ:

$3725$

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

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

На доске написано натуральное число. Его можно умножать на $2$ и можно отбрасывать его последнюю цифру. Докажите, что какое бы число ни было изначально написано на доске, из него за несколько таких операций можно получить число $100.$

Источники: Лига открытий - 2017

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

Из любого числа можно, отбросив все цифры, кроме первой, получить однозначное число. Из однозначных чисел $1,2,4,8$ можно умножениями на $2$ получить $256,$ из него $− 25,$ потом $50$ и $100.$ Из тройки можно получить $12$ и потом $1.$ Из пятёрки получается $10$ и $1.$ Из шестёрки получается $12$ и $1.$ Из семёрки получается $14$ и $1.$ Наконец, из девятки получается $18$ и $1.$

Интенсивы

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

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

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

На доске написано несколько цифр (среди них могут быть одинаковые). На каждом шаге две цифры стираются и пишутся цифры, из которых состоит их произведение. (Например, вместо $5$ и $6$ пишется $3$ и $0$ , а вместо $2$ и $4$ пишется $8$ ). Доказать, что через несколько шагов на доске останется одна цифра.

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

Подсказка 1

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

Подсказка 2

Возьмём две произвольные цифры a, b. Не умоляя общности, а ≥ b. b, a ≤ 9, значит, 10b > ab. То есть ab ≤ 10b - 1. Посмотрим внимательно на десятичные записи этих чисел. Какой вывод о них можно сделать?

Подсказка 3

Либо ab < 10 и оно однозначное, либо первая цифра ab < min(a,b) = b. Теперь надо выбрать, полуинвариант или индукция?

Подсказка 4

Допустим, полуинвариант. Нууу, у нас есть цифры на доске, причём перемножаться они могут хаотично. Как тогда следить за первыми цифрами получаемых произведений? Сумма цифр на доске, произведение — не подходят. Остальное тоже странно связано. Интересно, что же там насчёт индукции?

Подсказка 5

Начнём с базовых идей. Попробуем зацепиться за количество цифр на доске. Пусть изначальное количество цифр на доске — n. База для n = 1 тривиальна. Попробуем сделать переход.

Подсказка 6

Пусть мы доказали для n = k, докажем для n = k + 1. Заметим, что если в какой-то момент цифр на доске стало меньше, то в этом случае переход доказан, просто пользуемся предыдущими шагами индукции. Хорошо, а что если цифр не станет меньше? Как быть в этом случае? Напомню, первая цифра ab < min(a,b). На какую мысль нас это наталкивает?

Подсказка 7

Верно! Мы понимаем, что после каждого шага, на доске появляется цифра, которая меньше чем те, что были взяты. Ну предположим, что минимальная цифра не уменьшается бесконечно долго. Значит, она не участвует в операциях. Аналогично посмотрим на минимальную из оставшихся, она тоже бесконечно долго не уменьшается (иначе стала бы меньше глобального минимума). И так далее. Получаем что все цифры бесконечно долго не уменьшаются. Противоречие. (Это надо оформлять в общем виде) И так, что мы имеем?

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

При решении задачи будем использовать свойство уменьшения первого разряда. Оно состоит в том, что при умножении двух цифр $a$ и $b$ получается либо однозначное число (цифра), либо двузначное, и в последнем случае первая цифра двузначного произведения меньше, чем минимальная из цифр $a,b$ .

Действительно, двузначные числа $a0 =10× a$ и $b0 =10× b$ больше, чем $ab$ , так как $a,b< 9$ . Тем самым на каждом шаге либо получается на цифру меньше (первый случай), либо число цифр сохраняется, но минимальная из всех цифр, написанных на доске, не увеличивается.

_________________________________________________________________________________________________________________________________________________________________________________

Будем доказывать утверждение задачи индукцией по числу $n.$ При $n = 1$ утверждение очевидно. Утверждение для $n = 2$ следует из свойства уменьшения первого разряда, в силу которого через несколько шагов останется одна цифра.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для $n =k$ . Пусть $m$ — минимальная из цифр, написанных на доске. Достаточно показать, что через несколько шагов либо число цифр уменьшится, либо минимальная цифра уменьшится: появится цифра меньше $m$ .

Предположим противное. Тогда число цифр не уменьшается и в каждый момент есть цифра $m$ , к которой очередной шаг задачи не применяется: каждый шаг не затрагивает хотя бы одну цифру $m$ . В противном случае, если осталась одна или две цифры $m$ , и к ней (соответственно, к ним обеим) применен шаг задачи, и при этом число цифр не уменьшается, то минимальная цифра уменьшится в силу свойства уменьшения первого разряда.

Вышесказанное эквивалентно тому, что все шаги задачи применяются к меньшему набору цифр: ко всем, кроме одной из цифр $m$ . А тогда по предположению индукции через несколько шагов на доске, кроме цифры $m$ , останется одна цифра. Это сводит шаг индукции к случаю двух цифр, для которого утверждение задачи доказано.

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

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

На доске написаны числа $1,2,...,2015$ . Над ними последовательно проделывают 2014 операций, причём $n$ -я по счёту операция состоит в следующем: произвольные числа $a$ и $b$ (из написанных на доске) стираются и дописывается одно число, равное $ab∕n$ . Что останется на доске в конце?

Источники: ПВГ - 2015, Ставрополь, 11.2 (pvg.mk.ru)

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

Подсказка 1

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

Подсказка 2

Конечно, инвариант! Вместо a и b появляется ab/n. Сама операция намекает на то, что можно рассмотреть.

Подсказка 3

Да, нам нужно именно произведение чисел. Как оно изменяется после каждой операции?

Подсказка 4

Можно рассмотреть первые 2-3 операции и составить гипотезу.

Подсказка 5

Каждый раз произведение изменяется в определенное количество раз. Как же это можно доказать?

Подсказка 6

Отличной идеей будет доказать это в общем виде для k+1-ой операции — каким станет произведение после нее?

Подсказка 7

Осталось найти произведение после 2014 операции. Сколько чисел осталось на доске?

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

Заметим, что произведение после применения $k$ операций равно $2015!. k!$ Действительно, в начале произведение равно $2015!.$ После применения первой операции оно равно $2015! 1 ,$ так как два числа были стерты, а вместо них было написано $ab 1 .$

Пусть на $k−$ ом шаге произведение чисел равно $2015! k! .$ Тогда на $(k+ 1)−$ ом шаге произведение некоторые числа $c,$ $d$ становятся равны $ck+d1.$ Произведение всех чисел, кроме $c$ и $d,$ не изменилось, и оно равно $2015! k!⋅cd.$ Тогда новое произведение равно произведению всех чисел, к которым операция не применялась и нового числа $ckd+1$

2015!⋅--cd- = -2015!- k!⋅cd k +1 (k +1)!

Всего до того, как останется одно число, сделано $2014$ шагов, поэтому в конце будет

2015! 2014! = 2015

Ответ: 2015

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

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

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

Источники: Всеросс., 2015, РЭ, 11.7(см. olympiads.mccme.ru)

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

Подсказка 1

Давайте поймём, какое именно число не равно разности соседей. Очевидно, что наибольшее. Значит, все остальные равны разности соседей.

Подсказка 2

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

Подсказка 3

Верно, давайте попробуем доказать, что числа от наименьшего к наибольшему не убывают(а заодно вы получите ещё кое-какое соотношение). Какой самый простой для этого способ..? Конечно, индукция. Аналогичным образом получится результат для другой дуги. Попробуйте теперь воспользоваться полученными знаниями для получения противоречия.

Подсказка 4

У вас есть две последовательности чисел(пусть a_i и b_i) и рекуррентное соотношение на них. Попробуйте теперь доказать, что на самом деле a_i<b_i≤a_(i+1). Чем нам это поможет? А ведь мы ещё не пользовались всем условием. Что же не так с числом 300..?

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

Предположим, что требуемая расстановка существует. Ясно, что наибольшее из чисел не может равняться разности соседей; значит, каждое из остальных чисел равно разности соседей. В частности, наибольшее число встречается ровно один раз; обозначим его через $m.$

Пусть $d$ — одно из наименьших чисел в круге. Рассмотрим любую из двух дуг между $d$ и $m;$ пусть на ней стоят подряд числа $d =a0,a1,...,ak = m.$ Докажем индукцией по $i= 0,1,...,k− 1,$ что $ai+1 ≥ ai.$ В базовом случае $i= 0$ утверждение верно, ибо $d$ — наименьшее число. Для перехода от $i− 1$ к $i$ предположим, что $i< k$ и $ai−1 ≤ai.$ Тогда равенство $ai = ai− 1− ai+1$ невозможно, ибо $ai+1 > 0,$ и поэтому $ai = ai+1 − ai−1.$ Значит, $ai+1 > ai,$ что и доказывает переход индукции. Мы заодно показали, что $ai+1 = ai+ ai−1$ при всех $i= 1,...,k− 1.$

Аналогично, если на другой дуге между $d$ и $m$ стоят подряд числа $d= b0,b1,...,bℓ = m,$ то $b0 ≤ b1 ≤ ...≤bℓ$ и $bi+1 = bi+bi−1$ при всех $i= 1,2,...,ℓ− 1.$ Наконец, для числа $a0 = b0 = d$ условие задачи также должно выполняться, так что $d= |a1 − b1|.$ Без ограничения общности можно считать, что $d= b1− a1;$ тогда $a2 = a0 +a1 = b1 > a1.$

Продолжим теперь последовательности $a0,a1,...$ и $b0,b1,...$ согласно формулам $ai+1 = ai+ai−1$ и $bi+1 = bi+ bi−1.$ Докажем индукцией по $i= 1,2,...$ , что $ai <bi ≤ ai+1.$ При $i=1$ это уже доказано выше. При $i=2$ из соотношений $b0 = a0 ≤a1 <b1 = a2$ получаем

a2 = a1+a0 <b1+ b0 =b2 ≤ a2+ a1 =a3

Для перехода индукции предположим теперь, что $i≥ 3,$ и утверждение уже доказано для меньших значений $I.$ По предположению индукции, имеем

ai−2 < bi−2 ≤ ai−1 < bi−1 ≤ai

откуда

ai = ai− 1+ai−2 < bi−1+ bi−2 = bi ≤ai+ ai−1 =ai+1

что и требовалось.

Итак, мы получили, что

a0 =b0 ≤ a1 < b1 ≤a2 < b2 ≤ ...

Значит, равенство $bℓ = ak$ возможно лишь при $k= ℓ+1;$ но тогда общее количество чисел в круге равно $k+ ℓ= 2ℓ+1,$ что не может равняться $300.$ Противоречие.

Ответ:

Не могло

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

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

Решите в натуральных числах уравнение

3 4a + b+c= 4abc +2a

Источники: Лига победителей - 2014

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

Домножая на $4a$ для удобства разложения на множители, получаем

4 2 2 16a − 8a = 16a bc− 4ab− 4ac

(4a2− 1)2 = (4ab− 1)(4ac− 1)

Правая часть делится на $4ab− 1,$ значит, и левая часть

4a2− 1≡ 0mod(4ab− 1)

4a2− 4ab ≡0 mod(4ab − 1)

4a(a− b)≡ 0mod (4ab− 1)

a− b≡ 0mod (4ab− 1)

Для каждого целого неотрицательного $k$ среди всех пар $(a,b)$ натуральных чисел, для которых $2 (a− b)= k(4ab− 1)$ рассмотрим такую, у которой сумма $a+ b$ наименьшая.

Предположим, что $a> b,$ и запишем соотношение на $a$ и $b$ в виде квадратного уравнения относительно $a$

( ) a2− (4bk+ 2b)a+ b2+ k = 0

По теореме Виета у уравнения

( ) t2− (4bk+ 2b)t+ b2+ k = 0

кроме корня $t= a,$ есть ещё (очевидно, натуральный) корень $b2+k- t= a .$ Поскольку пара $(b2+k- ) a ,b$ тоже удовлетворяет условию, должно выполняться неравенство

b2+k- a ≥a

то есть

2 2 k ≥a − b

Тогда исходное равенство приводит к неравенству

2 (2 2) (a− b) ≥ a − b (4ab− 1)

a− b≥ (a +b)(4ab− 1)

Пришли к противоречию. Таким образом, $a= b$ и, следовательно, $a =c$ из симметричности изначального выражения.

Ответ:

$(a,b,c)=(t,t,t),t∈ℤ$

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

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

Натуральные числа от $1$ до $2014$ как-то разбили на пары, числа в каждой из пар сложили, а полученные $1007$ сумм перемножили. Мог ли результат оказаться квадратом натурального числа?

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

Подсказка 1

Чтобы понять, стоит ли придумывать пример, или доказывать, что не мог, попробуйте придумать примеры для меньшего количества чисел.

Подсказка 2

Например, можно большинство чисел разбить на чётное количество пар равной суммой.

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

Разбив числа от $7$ до $2014$ на пары

7,2014,8,2013,...,1010,1011

получим чётное число пар с суммой $2021.$ Числа от $1$ до $6$ можно разбить так: $1,5,2,4,3,6.$ Для них в результате получим произведение $62 ⋅9 =182.$ Значит, в итоге получится полный квадрат.

Ответ:

да

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

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

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

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

Ваня записал несколько простых чисел, использовав ровно по одному разу все цифры от $1$ до $9.$ Сумма этих простых чисел оказалась равной $225.$ Можно ли, использовав ровно по одному разу те же цифры, записать несколько простых чисел так, чтобы их сумма оказалась меньше?

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

Подсказка 1

У вас есть конкретный набор цифр. Попробуйте понять, какие у вас могут быть простые числа, какие на них могут быть ограничения?

Подсказка 2

Давайте посмотрим, например, на цифру 4. Она явно не может быть на первом месте в простом числе. Подумайте в эту сторону и с остальными цифрами.

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

Например,

207 =2+ 3+ 5+ 41+67+ 89=

= 2+ 3+ 5+47+ 61+ 89 =2 +5+ 7+ 43+61+ 89

Ответ:

да

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

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

Существуют ли такие натуральные числа $a,b,c,$ большие $1010,$ что их произведение делится на любое из них, увеличенное на $2021?$

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

Выберем некоторое $t> 1010$ и положим

(2 ) a =b= 2021t,c= 2021 t − 1

$c$ делится на $2021(t+ 1)=a +2021= b+2021,$ и $ab= 20212t2$ делится на $2021t2 =c+ 2021.$

Ответ: да

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

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

Докажите, что любое натуральное число $a > 1 1$ можно продолжить возрастающей последовательностью $a , 2$ $a, 3$ …так, чтобы при любом $k$ сумма $2 2 2 a1+a2+ ...+ ak$ делилась на $a1+a2+ ...+ ak.$

Источники: Всеросс., 1995, ЗЭ, 11.5(см. math.ru)

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

Подсказка 1

Давайте добавлять a_(n+1). Пусть A_(n+1) - сумма квадратов, B_(n+1) - сумма чисел. Попробуйте выразить A_(n+1) через a_(n+1), A_n и B_n^2. Для чего мы это хотим сделать? Мы просто хотим выразить a_(n+1).

Подсказка 2

A_(n+1) = A_n + (a_(n+1) - B_n) (a_(n+1) + B_n) + B_n^2. Поймите отсюда какие-нибудь делимости, а затем угадайте, чему может равняться a_(n+1).

Подсказка 3

Возьмите a_(n+1) = A_n + B_n^2 - B_n. Поймите, что оно подходит под все условия в задаче.

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

Докажем, что для любых чисел $a,a ,...,a , 1 2 n$ удовлетворяющих условию задачи, можно найти такое $a , n+1$ что

2 2 2 2 An+1 =a1+ a2+ ...+an +an+1

делится на

Bn+1 =a1+ a2+ ...+an +an+1

Из равенства $An+1 = An +(an+1 − Bn )(an+1+ Bn)+B2n$ следует, что $An+1$ делится на $Bn+1,$ если $An+ B2n$ делится на $Bn+1,$ поскольку $an+1+ Bn =Bn+1.$

Таким образом, достаточно взять

2 an+1 = An +Bn − Bn

(в этом случае $An+ B2n =Bn+1).$ Осталось показать, что тогда $an+1 >an.$ Но так как $B2n − Bn > 0(1< a1 < a2 < ...< an),$ то $an+1 > An ≥a2n >an.$

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

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

Пусть $a$ и $b$ - натуральные числа такие, что $ab+1$ делит $a2+b2$ . Докажите, что $a2+b2 ab+1$ является квадратом целого числа.

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

Решение 1: Выберем целые числа $a,b,k,$ такие что:

2 2 a + b = k(ab+ 1).

Для фиксированного $k$ рассмотрим пару $(a,b)$ с минимальным значением $min(a,b).$ Обозначим $b′ = min(a,b),$ $a′ =max(a,b).$ Тогда квадратное уравнение относительно $a′ :$

′2 ′ ′ ′2 a − kba +b − k= 0.

Если существует другой корень $c′,$ то:

b′c′ ≤a′c′ = b′2− k< b′2 =⇒ c′ < b′.

Если $c′ ∈ ℕ,$ то это противоречит условию минимальности $b′,$ поэтому $c′$ не может быть положительным целым. По формуле Виета:

c′ =kb′− a′,

что делает $c′$ целым. Из неравенства:

(a′+ 1)(c′+1)= b′2+ (b′− 1)k+ 1≥ 1 =⇒ c′ >− 1,

следует $c′ = 0.$ Тогда:

b′2 = k.

Таким образом, $k$ всегда является полным квадратом.

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2: Предположим противное: пусть $a2+b2 c= ab+1$ не является квадратом. Без ограничения общности $a≥ b.$ Выберем пару $(a,b)$ с минимальной суммой $a+ b.$ Рассмотрим квадратное уравнение:

P(a)= a2 − bca+b2− c= 0.

Его корни $r 1$ и $r 2$ удовлетворяют:

2 r1+ r2 =bc и r1r2 = b − c.

Пусть $r1 = a,$ тогда второй корень:

b2−-c r2 = bc− a= a < a, так как c> 0.

Так как $c$ не квадрат, $r2 ⁄= 0.$ Подставляя $r2$ в исходное уравнение:

r2+ b2 c= r22b+1.

Так как $c> 0,$ то $r2b+1 >0 =⇒ r2 > 0.$ Из $r2 <a$ следует $r2+ b< a+ b,$ что противоречит минимальности $a+ b.$ Следовательно, $c$ обязано быть квадратом.