Тема ММО (Московская математическая олимпиада)

Теория чисел на ММО

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

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

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

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

Подтемы раздела ммо (московская математическая олимпиада)

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

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

Задача 1#122411

Между двумя восьмёрками в числе $88$ вписали несколько нулей. Докажите, что можно всегда дописать слева в начало нового числа ещё несколько цифр так, чтобы получилось число, которое является полным кубом.

Источники: ММО - 2025, второй день, 11.1(см. mmo.mccme.ru)

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

Подсказка 1

На что должно заканчиваться число x, чтобы в кубе оно заканчивалось на 80....08?

Подсказка 2

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

Подсказка 3

Попробуйте рассмотреть число 40...02.

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

Рассмотрим выражение

3 3 2 (x +2) = x +6x + 12x +8

Заметим, что если натуральное число $x$ оканчивается на $40...0$ (всего $n+ 1$ нуль, где $n$ — натуральное), то это выражение примет значение, оканчивающееся на $80...08$ ( $n$ нулей между восьмёрками):

n+1 3 3n+3 2n+2 n+1 (4 ⋅10 + 2)= 64⋅10 + 96⋅10 + 48⋅10 + 8.

Поэтому можно дописать несколько цифр в начало нового числа так, чтобы получилось число $40...023.$

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

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

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

Задача 2#129301

Существуют ли такие натуральные числа $m$ и $n$ и такой многочлен $f(x)$ с целыми коэффициентами, что $f(m)$ не делится на $n,$ но $( k) f p$ делится на $n$ для любого простого числа $p$ и любого натурального $k$ ?

Источники: ММО - 2025, 10.4 (см. mmo.mccme.ru)

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

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

Приведём несколько примеров таких многочленов.

1) Пусть

2 5 f(x)= (x− 2)(x − 4) (x+ 1)

и $n= 32,$ $m =6.$ Проверим, что $f(6)$ не делится на 32. Действительно

2 5 5 f(6)= 4⋅2 ⋅7 = 16⋅7

не делится на 32. Теперь проверим, что $f(pk)$ делится на 32 для любого простого числа $p$ и любого натурального $k.$ Если $pk =2$ или $pk = 4,$ то многочлен тождественно равен 0. Для $pk = 2k,$ где $k≥ 3,$ имеем

k k k 2 k 5 k−1 k−2 k 5 f(2)= (2 − 2)(2 − 4)(2 + 1)= 32(2 − 1)(2 − 1)(2 + 1).

Наконец, если простое число $p$ нечётно (а значит, и $pk$ нечётно), то $f(pk)$ делится на 32, так как при любом нечётном $s= 2l− 1$ значение $f(s)$ делится на $(s+ 1)5 =(2l)5,$ а значит, и на 32.

2) Пусть

f(x)= x18(3x− x2)+ x2− 3x

и $n= 27,$ $m =6$ . Сначала проверим, что $f(pk)$ делится на 27 при всех простых $p$ и натуральных $k.$ Начнём со случая $p= 3.$ Заметим, что первое слагаемое делится на $318,$ а значит, и на 27. Остаётся проверить, что $x(x − 3)$ делится на 27 для чисел вида $3k,$ где $k ≥1.$ При $k= 1$ и $k= 2$ это проверяется непосредственно; при $k≥ 3$ число $k k 3 (3 − 3)$ также делится на 27. Теперь проверим утверждение для простых чисел $p⁄= 3.$ В этом случае $k p$ взаимно просто с $n,$ а значит, достаточно доказать утверждение $f(s)$ кратно $n$ при любом $s,$ взаимно простом с $n$ . Для этого заметим, что при всех таких $s$ по теореме Эйлера выполняется соотношение

s18 = sφ(27) ≡1 (mod 27)

Тогда

18 2 2 2 2 x (3x− x )+x − 3x≡ (3x − x )+ x − 3x≡ 0 (mod 27).

Остаётся проверить, что $f(6)$ не делится на 27. Для этого снова заметим, что число $618$ делится на 27, а число $62− 3 ⋅6 =18$ не делится на 27.

_________________________________________________________________________________________________________________________________________________________________________________

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

Пусть $q ≥2$ — простое, $m = 2q,$ $n= q3,$ и пусть $r,r,...,r 1 2 t$ — все не кратные $q$ натуральные числа, меньшие $q3.$ Положим

f(x)= x(x− q)⋅(x− r1)(x − r2)...(x − rt)

Действительно, тогда

2 f(m )=q ⋅2⋅(2q− r1)(2q− r2)...(2q− rt)

не кратно $q3.$ При $p ⁄=q$ число $pk$ имеет остаток от деления на $q3,$ не кратный $q,$ поэтому один из множителей в определении $f(x)$ будет кратен $q3$ при $x= pk.$ При $p =q$ и $k≥ 2$ уже число $pk(pk− q)$ будет кратно $q3.$ Наконец, при $p= q,$ $k= 1$ значение $f(p1) =0$ делится на $q3.$

Ответ:

Существуют

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

Задача 3#129304

Около таверны стоят 100 эльфов, 100 гномов и 100 орков. Сначала в неё заходят 10 эльфов, 10 гномов и 10 орков. Затем каждую минуту из неё выходит одно существо и тут же заходит другое, причём всегда после выхода эльфа заходит гном, после выхода гнома — орк, а после выхода орка — эльф. Могло ли оказаться так, что в какой-то момент в таверне побывали все возможные компании из 30 существ ровно по одному разу? Все 300 существ различны.

Источники: ММО - 2025, 10.6 (см. mmo.mccme.ru)

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

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

Назовём типом компании остаток разности количества эльфов и количества гномов при делении на три. Заметим, что компаний типа 1 и 2 одинаковое количество, так как между ними можно построить взаимооднозначное соответствие: пронумеруем эльфов и гномов от 1 до 100 и поменяем одних на других с теми же номерами. Далее заметим, что компании меняются по циклу $0→ 1→ 2 → 0,...,$ причём, так как компаний типов 1 и 2 поровну, мы не можем закончить на 1, то есть количество всех компаний не может давать остаток 2 при делении на 3. Вычислим $30 C 300$ по модулю 3.

300⋅299⋅298⋅...⋅273⋅272 ⋅271 299⋅298⋅296⋅...⋅274⋅272⋅271 100⋅99⋅...⋅92⋅91 C33000 =----30⋅29⋅28-⋅...⋅3-⋅2-⋅1---- =----29⋅28⋅26-⋅...⋅4⋅2-⋅1---- ≡ -10⋅9⋅...⋅2⋅1--=

= 100⋅99⋅...⋅92⋅91= 100⋅98-⋅...⋅94⋅92⋅91⋅ 33⋅32⋅31≡ 10⋅9⋅...⋅2⋅1 10⋅8⋅...⋅4⋅2⋅1 3 ⋅2 ⋅1

≡ 10⋅8⋅...⋅4⋅2⋅1⋅ 33⋅32⋅31-= 11 ⋅16⋅31≡ 2 (mod 3) 10⋅8⋅...⋅4⋅2⋅1 3⋅2⋅1

Противоречие, значит, так оказаться не могло.

Замечание. Есть другой способ посчитать остаток $C30 300$ при делении на 3. Теорема Люка утверждает, что если $p$ — простое число, а числа $n$ и $k$ записываются в $p$ -ичной системе счисления как $n = ∑ nipi$ и $k= ∑ kipi,$ то $Ck≡ ∏ Ckni(mod p). n i$ Запишем 300 и 30 в троичной системе счисления: $300= (102010)3$ и $30= (1010)3.$ Таким образом,

30 1 0 1 0 1 0 C 300 ≡ C1C0C2C0C1C0 ≡2 (mod 3)

_________________________________________________________________________________________________________________________________________________________________________________

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

Как и в прошлом решении разделим все компании на три типа. Если описанное в задаче возможно, то количества компаний разных типов отличается не более чем на 1, так как типы компаний меняются по циклу. Пронумеруем представителей всех рас от 1 до 100. Разобьем на тройки все компании, в которых множества номеров хотя бы каких-то двух рас различны, следующим образом. Возьмем некую компанию данного вида и рассмотрим максимальный номер, представленный хотя бы одной, но не всеми расами. Дважды прокрутим всех существ с этим номером, поменяв каждое существо на существо следующей расы с таким же номером. Легко видеть, что исходная и две полученные компании различных типов, причем с помощью данной операции они могут быть получены только друг из друга. При этом все компании не данного вида, коих всего $C10 , 100$ имеют тип 0, то есть компаний типа 0 ровно на $C10 100$ больше, чем других — противоречие.

Ответ:

Не могло

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

Задача 4#85484

Докажите, что если при $n∈ ℕ$ число $2+ 2√12n2+-1$ целое, то оно точный квадрат.

Источники: ММО - 2024, второй день, 11.3 (см. mmo.mccme.ru)

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

Подсказка 1

Внимательно посмотрим на выражение. Если наше выражение целое при любых натуральных n, то оно четное. Обозначим его за 2k.

Подсказка 2

Что можно сказать про k после возведения в квадрат полученного уравнения на n и k?

Подсказка 3

Что k — чётное, то есть k = 2m. Получили, что произведение взаимно простых равно квадрату числа. А часто ли такое происходит?

Подсказка 4

Нужно разобрать 2 случая, один из которых не подойдет из-за остатков по модулю 3

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

Если число $2+ 2√12n2+1-$ целое при $n∈ ℕ$ , то оно чётное. Обозначим $2 +2√12n2+-1=$ $2k,k ∈ℕ$ . Тогда $√12n2+-1= k− 1$ . Возводя это равенство в квадрат, получаем

2 2 12n = k − 2k

Число $k$ чётное: $k= 2m$ , где $m ∈ ℕ$ .

Тогда

2 2 12n = 4m − 4m

3n2 =(m − 1)m

Поскольку числа $m$ и $m − 1$ взаимно просты, следует рассмотреть два случая:

1) $m− 1= u2,m = 3v2$ , где $u,v ∈ ℕ,u⋅v = n$ ;

2) $m− 1= 3u2,m = v2$ , где $u,v ∈ ℕ,u⋅v = n$ .

В первом случае имеем $3v2− 1= u2$ , то есть $u2$ даёт остаток 2 при делении на 3 . Это невозможно, так как точный квадрат может давать при делении на 3 только остатки 0 или 1.

Во втором случае получаем $2+ 2√12n2+-1= 4m =(2v)2$ - точный квадрат.

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

Задача 5#72975

Некоторые неотрицательные числа $a,b,c$ удовлетворяют равенству $a+ b+c =2√abc.$ Докажите, что $bc≥ b+c.$

Источники: ММО-2022, 11.1 (см. mmo.mccme.ru)

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

Подсказка 1

Числа неотрицательны, присутствует и произведение, и сумма... Как их можно связать?

Подсказка 2

Неравенством о средних!

Подсказка 3

Также можно попробовать рассмотреть равенство из условия как квадратный трëхчлен относительно чего-нибудь.

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

Первое решение. По неравенству о средних:

√ --- a+ bc≥ 2 abc= a+ b+ c⇒ bc≥b+ c

Второе решение. Числа $a,b$ и $c$ неотрицательны, поэтому исходное равенство можно рассматривать как квадратное уравнение относительно $√a:$

(√a)2+ 2√bc√a +b+ c= 0

По условию это уравнение имеет хотя бы одно решение, а значит, $D ∕4=bc− b− c≥0.$

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

Задача 6#72978

Таня последовательно выписывала числа вида $n7− 1$ для натуральных чисел $n= 2,3,...$ и заметила, что полученное при $n= 8$ число делится на $337.$ А при каком наименьшем $n >1$ она получит число, делящееся на $2022?$

Источники: ММО-2022, 11.5, (см. mmo.mccme.ru)

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

Подсказка 1

Никому ещё не вредило разложение чисел на простые множители в задачках на теорию чисел. Давайте разложим 2022 и поймём, какие условия накладывает каждый из множителей.

Подсказка 2

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

Подсказка 3

Попробуйте подумать, какое максимальное кол-во решений может иметь сравнение n^7 = 1 (mod 337) на отрезке [0;336], а ещё подумать, что происходит с решением сравнения, если его возвести в произвольную положительную степень?

Подсказка 4

Мы понимаем, что решений не больше 7 и что возведение решения в положительную степень не портит сравнение, остаётся перебрать маленькие n, пока мы не сможем применить эти 2 факта, проверить, что хотя бы одно из них удовлетворяет остальным условиям, полученным из сравнений по mod 2 и mod 3, и выбрать из них наименьшее.

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

Пусть натуральное число $n$ таково, что $n7− 1$ делится на $2022 =2⋅3⋅337.$ Тогда $n7− 1$ делится на $2$ и на $3,$ поэтому $n$ — нечётное число, имеющее остаток $1$ при делении на $3.$ Помимо того, $7 n − 1$ делится на $337.$ Заметим, что если два числа сравнимы по модулю $337$ (т.е. дают одинаковые остатки при делении на $337$ ), то седьмые степени этих чисел также сравнимы по модулю $337.$ Это означает, что для нахождения искомого числа достаточно рассмотреть все целые числа $n$ из промежутка $[0;336],$ удовлетворяющие сравнению $7 n ≡ 1(mod337).$

Мы будем пользоваться следующим утверждением. Пусть $p$ — простое число, $Pk$ — многочлен степени $k$ с целыми коэффициентами, старший коэффициент которого не делится на $p;$ тогда сравнение $Pk(n) ≡0(modp)$ имеет не более $k$ решений среди целых чисел $0 ≤n <p.$

Найдём теперь все решения сравнения $7 n ≡ 1(mod337)$ на отрезке $[0;336].$ Нам известны два решения: $n1 =1$ , $n2 = 8.$ Заметим, что если $n$ — решение сравнения $n7 ≡ 1$ $(mod337),$ то для любого натурального $s$ числа $ns$ также являются решениями. Следовательно, решениями данного сравнения являются числа

82 = 64≡ 64(mod337) 83 = 512 ≡175(mod337) 84 ≡ 8⋅175 ≡52(mod337) 5 8 ≡ 8⋅52≡ 79(mod337) 86 ≡ 8⋅79≡ 295(mod337)

Итак, мы нашли семь решений на отрезке $[0;336]:n1 = 1,n2 =8,n3 = 52,n4 = 64,n5 =79,n6 = 175,n7 = 295.$ Так как число $337$ простое, по сформулированному выше утверждению других решений на этом отрезке нет. Из них нечётными и имеющими остаток $1$ при делении на $3$ являются $n1 =1,n5 = 79,n6 =175$ и $n7 = 295.$ Из них наименьшее, большее $1,$ есть $n5 = 79.$

Ответ:

$79$

Курсы

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

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

Задача 7#79881

На доске записано натуральное число. Если у него стереть последнюю цифру (в разряде единиц), то останется ненулевое число, которое будет делиться на $20,$ а если первую — то на $21.$ Какое наименьшее число может быть записано на доске, если его вторая цифра не равна $0?$

Источники: ММО-2021, 11.1(см. mmo.mccme.ru)

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

Подсказка 1

Раз у нас число без последней цифры делится на 20, то и предпоследняя цифра равна 0. Тогда что можно сказать про кол-во цифр в числе, если учитывать второе условие на наше число?

Подсказка 2

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

Подсказка 3

Отлично! Мы получили, что 100, 120, 140 не подходят. В случае же с 160 найти противоречие не получается. Тогда попробуем построить пример.

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

Предпоследняя цифра числа равна $0,$ так как число без последней цифры делится на $20.$ Значит, число хотя бы четырехзначное. Заметим, что число, оставшееся после стирания последней цифры, не может равняться $100$ по условию. Также это число не может равняться $120$ и $140,$ так как числа вида $--- 20a$ и $--- 40a$ не делятся на $21.$ Для $160$ существует единственный пример: $1609.$

Ответ:

$1609$

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

Задача 8#79883

Найдите наименьшее натуральное число $N > 9,$ которое не делится на $7,$ но если вместо любой его цифры поставить семёрку, то получится число, которое делится на $7.$

Источники: ММО-2021, 11.3 второй день(см. mmo.mccme.ru)

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

Подсказка 1

Подумаем, какие цифры не могут входить в искомое число. А если ещё использовать и то условие, что наше число минимальное из возможных?

Подсказка 2

Теперь, когда понятно, какие цифры могут входить в искомое число, можно рассмотреть две соседние цифры. Если заменить k-ую или (k+1)-ую цифру на 7, то получатся кратные семи числа, но тогда и их разность будет кратна 7. Значит можно найти эту разность и попробовать связать между собой соседние цифры (по модулю 7).

Подсказка 3

Должно получиться, что 10*a_k и а_(k+1) сравнимы по модулю 7, где a_k и а_(k+1) — k-ая и (k+1)-ая цифры числа. Заметим также, что если отбросить последнюю цифру от искомого числа, получится число, кратное 7. Теперь, используя это, можно преобразовать искомое число без последней цифры (преобразования по модулю 7) и с помощью этого получить оценку на количество цифр в нашем числе.

Подсказка 4

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

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

Пусть наименьшее подходящее число имеет вид $a-a-...a-. 1 2 n$ Из условия следует, что среди его цифр нет $0$ и $7.$ Если в числе есть цифры $8$ или $9,$ то их можно заменить на $1$ или $2$ соответственно и получить меньшее число с тем же свойством. Таким образом, искомое число состоит из цифр от $1$ до $6.$

Рассмотрим соседние цифры $ak$ и $ak+1.$ По условию числа с замененными семеркой цифрами $--------------- a1a2 ...7ak+1...an$ и $------------- a1a2...ak7...an$ делятся на $7,$ следовательно, их разность также кратна $7,$ то есть $10ak ≡ak+1 (mod 7)$ для любого $k.$ Значит, запись числа может быть устроена только следующим образом: за $1$ следует $3,$ за $3$ следует $2$ (поскольку цифры $9$ в числе нет) и так далее.

По условию исходное число, у которого вместо последней цифры стоит $7,$ делится на $7.$ Следовательно, исходное число без последней цифры делится на $7.$ Используя несколько раз сравнение $10ak ≡ ak+1 (mod 7),$ получаем:

a1a2...an−1-=a110n− 2+a210n− 3+a310n−4+...+an−1 ≡ 10a1⋅10n−3+ a210n−3+ a310n−4+

n−3 n−4 + ...+an−1 ≡ 2a2⋅10 +a310 +...+ an−1 ≡ ...≡ (n− 1)an−1 (mod 7)

Поскольку $a n−1$ не делится на $7,$ заключаем, что $n− 1$ делится на $7,$ поэтому наименьшее возможное $n$ равно $8.$ Таким образом, наименьшее возможное число состоит не менее чем из восьми знаков. Остается заметить, что число $13264513$ удовлетворяет условию задачи, а поскольку оно начинается с $1,$ то это число и будет наименьшим.

Ответ:

$13264513$

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

Задача 9#92164

Верхней целой частью числа $x$ называют наименьшее целое число, большее или равное $x$ . Существует ли такое число $A$ , что для любого натурального $n$ расстояние от верхней целой части $n A$ до ближайшего квадрата натурального числа всегда равно 2 ?

Источники: ММО - 2021, первый день, 11.6 (см. mmo.mccme.ru)

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

Подсказка 1

Есть два возможных ответа — да или нет. Если нет, то нужно доказывать, что абсолютно для любого числа в последовательность {A^i} найдется не подходящее число, что кажется очень непростой задачей. Тогда будем доказывать, что ответ «да». Если мы хотим, чтобы верхняя целая часть Aⁿ отличалось от ближайшего натурального квадрата на 2, то хотелось бы понять, чему равна эта верхняя целая часть. Вернее, что нам было бы удобнее взять за верхнюю целую часть, чтобы она отличалась от какого-то квадрата на 2? А если вспомнить как возводится число вида t+1/t в квадрат?

Подсказка 2

Хотелось бы сделать так, чтобы число вида Aⁿ + 1/Aⁿ было бы целым и A было некоторым квадратом, чтобы как раз получить t^2n + 1/(t^2n) = (tⁿ + 1/tⁿ)²-2. Осталось только понять, чему должно быть равно t, чтобы каждое выражение вида Aⁿ + 1/Aⁿ при A = t², было бы целым. Здесь вас на поиск подходящего t может натолкнуть либо мысль о процессе построения бесконечных цепных дробей, либо же тот факт, что число вида (a+b√c)^k, где a, b, k - целые, это выражение вида t+l√c. Заметьте, это верно и для отрицательных k.

Подсказка 3

Да, можно просто сказать, что t — корень некоторого уравнения с целыми коэффициентами и отрицательным коэффициентом при x, ведь тогда t+1/t = c, где с — целая положительная константа. Тогда, по модулю факта про возведение таких иррациональностей в степень можно сказать, что задача решена, поскольку мы нашли такое t, что любое выражение вида t^k + 1/t^k — целое, а значит, мы нашли подходящее А.

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

Пусть $t$ — больший корень многочлена $x2− 10x+ 1$ , тогда $t+ 1 =10 t$ .

Докажем по индукции, что число $n 1- t + tn$ целое при любом целом неотрицательном $n$ .

Действительно, это верно при $n = 0,1$ . Кроме того,

n+1 1 ( n 1 )( 1) ( n−1 1 ) t + tn+1 = t + tn- t+ t − t + tn−1- ,

что позволяет проделать шаг индукции.

Положим $A = t2$ , тогда

( )2 An + 1-= tn+ -1 − 2 An tn

-1- An <1

Значит, $n -1 A + An$ и есть верхняя целая часть $n A$ , а ближайший к ней квадрат целого числа равен $(n -1)2 t+ tn$ .

Ответ: да

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

Задача 10#89085

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

Источники: ММО - 2020, первый день, 11.6(см. mmo.mccme.ru)

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

Подсказка 1

Каким способом можно доказать, что состояние фиксированного объекта в процессе его изменения не приведёт к тому, что он примет начально состояние?

Подсказка 2

Найти полуинвариант! Давайте найдем величину, которая будет меняться монотонно в ходе процесса, и, как следствие, не вернется к изначальному состоянию.

Подсказка 3

Как найти полуинвариант в данной задаче? В условии задачи сказано, что при замене двух чисел x и y на их сумму x+y, второе число равно x-y или y-x. Было бы хорошо, если бы наш полуинвариант вел себя одинаково вне зависимости от этого выбора. Ясно, что данные числа равны по модулю. Как это помогает найти полуинвариант?

Подсказка 4

Пусть S является искомым полуинвариантом. Ясно, что S - это функция от набора чисел, написанных на доске в данный момент. Если мы положим в качестве S функцию от их квадратов, то значение S будет совпадать при выборе любой из разности чисел (x-y или y-x), что является хорошим знаком. Осталось доопределить S.

Подсказка 5

Самые естественные функции от набора переменных - их сумма или произведение. С суммой в данном случае работать проще (итак, в качестве предполагаемого полуинварианта мы пока положим S - сумму квадратов чисел написанных на доске), поскольку мы можем легко получить значения данного полуинварианта на каждом ходу. Поймите, как это можно сделать.

Подсказка 6

Если на доске были написаны числа x² и y², то сумма их квадратов измениться на (x-y)²+(x+y)²=2(x²+y²). Таким образом, значение S после каждого шага увеличивается вдвое. Осталось показать, что не существует двух различных последовательностей из 2n идущих подряд чисел таких, что отношение сумм их квадратов равно степени двойки. Каким способом это возможно сделать?

Подсказка 7

Мы можем показать, что степень вхождения двойки в сумму квадратов 2n последовательных чисел является инвариантом для данного n. Для этого можно явно показать, как степень вхождения двойки в рассматриваемую сумму зависит от n.

Подсказка 8

Пусть 2n=l*2^k, где l - нечетное натуральное число, k - натуральное число, не меньшее 1. Докажите, что степень вхождения двойки в сумму квадратов 2n последовательных чисел равна k-1.

Подсказка 9

Искомую сумму можно представить как l сумм 2^k последовательных квадратов натуральных чисел. Если мы докажем, что каждая из них имеет вид 2^{k-1}t, для некоторого нечетного числа t, то явно получим, что и вся сумма делится на 2^{k-1}, но не делится на 2^k. Сделайте это!

Подсказка 10

Рассмотрим сумму последовательных 2^k квадратов по модулю 2^k. Квадраты этих чисел имеют тот же набор остатков при делении на 2k, что и набор чисел 1², 2², 3²,..., (2^k)², а значит сравнимо по этому модулю c суммой 1²+2²+...+(2^k)². Каким образом ее можно преобразовать?

Подсказка 11

По известной формуле суммы квадратов первых n чисел, 1²+2²+...+(2^k)²=2^{k-1}(2^k+1)(2^{k+1}+1)/3 - кратно 2^{k-1}, но не кратно 2^k. Это как раз то, что мы хотели показать!

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

Рассмотрим набор из $2k$ подряд идущих чисел, квадраты этих чисел имеют тот же набор остатков при делении на $2k,$ что и набор чисел $2 2 2 ( k)2 1 ,2,3,..., 2 .$ Поскольку

2 2 2 ( k)2 1 +2 + 3 + ...+ 2 (= )( ) ( )( ) = 2k-2k+-1-2-⋅2k+-1-= 2k−12k+-1-2⋅2k-+1-- 6 3

сумма квадратов $k 2$ подряд идущих чисел делится на $k−1 2 ,$ но не делится на $k 2 .$

Представим число $2n$ в виде $k 2 ⋅l,$ где $l$ нечётно. Тогда сумма $2n$ последовательных квадратов разбивается на $l$ сумм вида $k−1 2 ti,$ где все $ti$ нечётны, поэтому вся сумма также делится на $k−1 2 ,$ но не делится на $k 2.$ Следовательно, наибольшая степень двойки, на которую делится сумма квадратов $2n$ последовательных чисел, зависит только от $n,$ но не от самих чисел.

В то же время сумма квадратов имеющихся чисел после замены удваивается. Действительно, заменив числа $a$ и $b$ на $a− b$ и $a+ b,$ получим:

( ) (a− b)2+ (a+ b)2 = 2a2+2b2 = 2 a2 +b2

Таким образом, снова получить набор из $2n$ подряд идущих чисел нельзя.

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

Задача 11#108459

На доске написаны $1000$ последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и каждую пару чисел заменить на их сумму и разность (не обязательно вычитать из большего меньшее, все замены происходят одновременно). Докажите, что на доске больше никогда не появятся $1000$ последовательных целых чисел.

Источники: ММО - 2020, 10.5(см. mmo.mccme.ru)

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

Подсказка 1

Каким способом можно доказать, что состояние фиксированного объекта в процессе его изменения не приведёт к тому, что он примет начальное состояние?

Подсказка 2

Подсказка 3

Подсказка 4

Пусть S является искомым полуинвариантом. Ясно, что S — это функция от набора чисел, написанных на доске в данный момент. Если мы положим в качестве S функцию от их квадратов, то значение S будет совпадать при выборе любой из разности чисел (x-y или y-x), что является хорошим знаком. Осталось доопределить S.

Подсказка 5

Самые естественные функции от набора переменных — их сумма или произведение. С суммой в данном случае работать проще (итак, в качестве предполагаемого полуинварианта мы пока положим S — сумму квадратов чисел написанных на доске), поскольку мы можем легко получить значения данного полуинварианта на каждом ходу. Поймите, как это можно сделать.

Подсказка 6

Если на доске были написаны числа x² и y², то сумма их квадратов измениться на (x-y)² + (x+y)² = 2(x²+y²). Таким образом, значение S после каждого шага увеличивается вдвое. Осталось показать, что не существует двух различных последовательностей из 1000 идущих подряд чисел таких, что отношение сумм их квадратов равно степени двойки. Каким способом это возможно сделать?

Подсказка 7

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

Подсказка 8

Да, достаточно доказать, что 8 подряд идущих чисел дают остаток 4 при делении на 8. Пусть эти числа имеют вид n-3, n-2, ..., n+3, n+4 при некотором целом n. Чему равна сумма их квадратов?

Подсказка 9

Сумма квадратов равна 8n² + 8n + 44, дает остаток 4 по модулю 8, а значит, и сумма 1000 последовательных чисел сравнима с 4 по модулю 8, то есть всегда делится на 4 и не делится на 8.

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

Поскольку $(x +y)2+ (x− y)2 =2(x2+ y2),$ то сумма квадратов всех чисел на доске увеличивается в два раза с каждым ходом. Из формулы

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

2 2 2 +(n+ 3)+ (n+ 4) = 8n + 8n +44

ясно, что сумма квадратов $8$ последовательных целых чисел даёт остаток $4$ при делении на $8.$ Значит, сумма квадратов $1000$ последовательных целых чисел тоже даёт остаток $4$ при делении на $8.$

Таким образом, после первого хода сумма квадратов чисел на доске всегда будет делиться на $8,$ и, следовательно, на доске никогда больше не появятся $1000$ последовательных целых чисел.

Интенсивы

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

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

Задача 12#124035

Приведите пример числа, делящегося на $2020,$ в котором каждая из десяти цифр встречается одинаковое количество раз.

Источники: ММО - 2020, первый день, 11.1 (см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Обратим внимание на 101. Нам нужен просто пример (необязательно наименьшее число), надо взглянуть на числа, которые делятся на 101. У многих из них повторяются цифры (2020, 2121, 3030, 4343 и др), а ведь нам как раз нужен пример, где всех цифр одинаковое количество!

Подсказка 3

Мы на финишной прямой! Осталось только собрать такой пример (мы уже поняли, что каждой цифры должно быть по две), осталось не забыть, что число должно не только оканчиваться на ноль, но и делиться на 4

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

Рассмотрим число

98987676545431312020

(существуют и другие примеры).

Поскольку $2020 =4 ⋅5 ⋅101,$ число делится на $2020,$ если оно делится на $4,$ $5$ и $101.$ Приведённое число оканчивается на $20,$ следовательно, делится на $4$ и $5.$ Числа вида $abab$ равны $101⋅ab.$ А поскольку приведённое число раскладывается в сумму чисел вида $abab⋅10k,$ оно делится на $101.$

Ответ:

$98987676545431312020$

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

Задача 13#106713

Пользуясь равенством $lg11= 1,0413...,$ найдите наименьшее число $n> 1,$ для которого среди $n$ -значных чисел нет ни одного, равного некоторой натуральной степени числа $11.$

Источники: ММО - 2019, второй день, 11.1(см. mmo.mccme.ru)

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

Подсказка 1

Ясно, что k-я степень числа 11 представляет собой n-значное число, если она находится между (n-1)-ой и n-ой степенями 10. Как теперь можно оценить n?

Подсказка 2

Верно! Из прошлой подсказки получается n - 1 < k × lg(11) < n. По условию нам даны первые знаки числа lg(11). Как можно, исходя из этого, оценить n через k × lg(11)?

Подсказка 3

Конечно! Число lg(11) не слишком удобное число, но можно сравнить k × lg(11) с числом k+1. При каких k больше второе, а при каких первое?

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

Число $11k$ является $n$ -значным, если $10n−1 < 11k < 10n,$ т. е. $n− 1< klg11< n.$ Значит, $n = [klg11]+ 1.$ Если $k≤ 24,$ то $klg11< k+ 1$ (и значит, $n= k+ 1),$ так как

k(lg11− 1)≤24⋅0,0415= 0,996< 1

Если $k≥ 25,$ то $klg11> k+ 1$ (и значит, $n ≥k +2),$ так как

k(lg 11 − 1)≥ 0,041⋅25= 1,025> 1

Ответ:

$26$

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

Задача 14#73723

Пусть $x$ и $y$ — пятизначные числа, в десятичной записи которых использованы все десять цифр ровно по одному разу. Найдите наибольшее возможное значение $x,$ если $∘ ∘ ∘ ∘ tgx − tgy = 1+ tgx tgy$ ( $∘ x$ обозначает угол в $x$ градусов).

Источники: ММО-2018, задача 11.3(см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Как насчёт формулы тангенса разности?

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

Данное равенство при условии, что $tgx∘$ и $tgy∘$ определены, эквивалентно равенству $tg(x − y)∘ = 1,$ откуда $x − y = 45+ 180n,$ где $n ∈ℤ.$ Следовательно, разность $x − y$ делится нацело на $45,$ а значит, на $5$ и на $9.$ Поскольку сумма всех цифр делится на $9,$ то каждое из чисел $x$ и $y$ делится на $9.$

Наибольшее пятизначное число, все цифры которого различны, равно $98765.$ Ближайшее к нему меньшее число, делящееся на $9,$ равно $98757$ и содержит повторяющиеся цифры. Последовательно уменьшая это число на $9,$ получаем числа $98748,98739,98730,98721.$ Первые два из них также содержат повторяющиеся цифры. Третье состоит из различных цифр, но поскольку $98730= 90 +180⋅548,$ то его тангенс не определён. Число $x =98721$ также состоит из различных цифр. Если взять, например, $y =54036,$ то получим $x − y = 44685 =45+ 180⋅248,$ поэтому число $98721$ искомое.

Ответ:

$98721$

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

Задача 15#79882

Можно ли представить число $112018$ в виде суммы кубов двух натуральных чисел?

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

Подсказка 1

Существует ряд модулей, по которым кубы натуральных чисел дают "приятные остатки". К их числу относиться, например, модуль 8 - куб натурального числа может давать только остатки 0,1,3, -3, -1 по данному модулю. А по какому модулю можно рассмотреть данное уравнение?

Подсказка 2

Ясно, что при этом нам придется рассматривать число 11^2018 по данному модулю, поэтому будет проще, если 11^2018 будет давать какой-то понятный остаток по рассматриваемому модулю (точнее остаток, который мы сможем найти, что не всегда бывает просто).

Подсказка 3

Давайте рассмотрим уравнение по модулю 9. Какие остатки могут давать кубы натуральных чисел по этому модулю?

Подсказка 4

Только остатки 0, 1 или -1. С чем в свою очередь сравнимо число 11^2018 по модулю 9?

Подсказка 5

Ясно, что 11^2018 сравнимо с 2^2018 по данному модулю. Осталось заметить, что 2^6=64 сравнимо с 1 по модулю 9. Вообще говоря, для каждого числа a существует число b такое, что a^b сравнимо с 1 по данному модулю. В некоторых задачах данное число b можно найти перебором, тем более в тех задачах, где в качестве основания рассматриваются 2, потому что ее первые степени считаются довольно быстро. Закончите решение, воспользовавшись этим сравнением.

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

С одной стороны, поскольку $26 = 64≡ 1 (mod 9)$ и $2018 ≡2 (mod 6= φ(9)),$ имеем

2018 2018 2 11 ≡ 2 ≡ 2 = 4 (mod 9)

То есть число $112018$ даёт остаток $4$ при делении на $9.$ С другой стороны, кубы натуральных чисел дают только остатки $0,1$ и $8$ при делении на $9.$ Значит, сумма кубов двух натуральных чисел может дать лишь остатки $0,1,2,7$ или $8$ при делении на $9,$ но не может дать $4.$

Ответ:

Нет

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

Задача 16#91095

Известно, что в десятичной записи числа $229$ все цифры различны. Есть ли среди них цифра $0?$

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

Подсказка 1

Разумно начать решать от обратного, предположить, что 0 там нет. Но как тогда искать противоречие? Вообще число очень большое и единственная информация, которую можно относительно просто узнать, это остатки при делении на некоторые числа.

Подсказка 2

Попробуйте определить количество цифр у числа, тогда сразу поймëте, какой остаток надо искать.

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

Заметим, что

29 30 3 9 2⋅2 = 2 = (1024) <2 ⋅10

Следовательно, $229 < 109.$ С другой стороны,

29 10 2 9 2 8 2 = (2 ) ⋅2 =1024 ⋅512> 5⋅10

Поэтому в записи числа $229$ ровно девять цифр. Если среди них нет нуля, то сумма цифр в десятичной записи этого числа равна $1+ 2+ ...+ 9= 45.$ Отсюда следует, что $229$ делится на $3,$ что не так. Противоречие.

Ответ:

да

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

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

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

Задача 17#31222

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

Источники: ММО-2017, 9.1, автор - М.А. Евдокимов, (см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Да, мы представили n=a*10^(k-1)+m, где a-первая цифра, k-кол-во цифр. Но ведь тогда a*10^(k-1)=4m. Попробуйте оценить k, зная, что в числе нет одинаковых цифр.

Подсказка 3

Ура! Мы получили, что k<=4(так как иначе на конце будет две одинаковые цифры-нули). Остается перебрать варианты и выбрать максимальное число.

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

По условию $aA-= 5A$ (где $A−$ число, составленное из всех цифр, кроме первой, $a$ — первая цифра). Пусть $n$ – количество цифр в числе $--- aA.$ Отсюда

n−1 n−3 4A =a ⋅10 ⇒ A = 25a ⋅10

Если $n> 4,$ то у числа $A,$ а значит, и у искомого числа, есть две совпадающие цифры (два нуля на конце). Если же $n =4,$ то

A = 250a

Ясно, что чем больше $a,$ тем больше исходное число. При $a≥ 4$ число $250a$ состоит из $4$ цифр, а не из трех. При $a= 3$ мы получаем $A = 750,$ а исходное число равно $3750.$ Значит, наибольшее искомое число равно $3750.$

Ответ:

$3750$

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

Задача 18#91098

Найдите все такие пары натуральных чисел $a$ и $k,$ что для всякого натурального $n,$ взаимно простого c $a,$ число $akn+1 − 1$ делится на $n.$

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

Подсказка 1

Понятно, что a=1 подходит. Пусть теперь a больше 1, попробуйте тогда подобрать какой-то пример для n, который сделает выполнение условия невозможным.

Подсказка 2

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

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

Если $a =1,$ то $akn+1− 1= 0,$ а значит, делится на $n.$

Пусть $a≥2.$ Возьмём $k n =a − 1,$ тогда $k a ≡n 1,$ и следовательно,

kn+1 kkn−1 0≡n a − 1≡n (a) ⋅a− 1≡n a− 1

Если $k> 1,$ то в силу неравенства $a >1$ получаем неравенство $k a− 1< a − 1 =n,$ что противоречит $a− 1≡n 0.$

Если $k= 1,$ то $n ak+1 − 1= a2− 1$ должно делиться на все $n,$ что невозможно.

Таким образом, пары, в которых $a≥ 2,$ нам не подходят.

Ответ:

$a =1,k$ - любое натуральное число.

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

Задача 19#34908

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

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

Пусть это число $n$ . Тогда $n2− 2016..10000 .$ . Отсюда $n2 − 2016..2000 .$ и $n2− 16= (n − 4)(n +4)..2000 .$ . Тогда так как разница множителей равна 8, то ровно одно из них делится на 5 и поэтому оно делится сразу на $3 5$ и оба множителя кратны 4 (так как если один не кратен, то и второй не кратен и тогда их произведение не может быть равно $4 3 2 ⋅5$ ). Отсюда один из множителей делится на 500 = $2 3 2 ⋅5$ . Значит, $n = 500a± 4$ . Давайте проверим эти числа

2 496 = 246016

5042 = 254016

9962 = 992016

Итак, минимальное число равно 996.

Ответ: 996

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

Задача 20#35425

Найдите наименьшее натуральное число, кратное 99, в десятичной записи которого участвуют только чётные цифры.

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

Подсказка 1

На какие ещё числа должно делиться наше число? Вспомните известные вам признаки делимости и попробуйте предположить, с чем именно здесь удобно будет работать?

Подсказка 2

Логичнее всего поработать с делимостью на 9 и 11. Но для признака делимости на 11 нам нужна знакопеременная сумма цифр. Как же тут быть, если мы не знаем сколько всего этих цифр в нашем числе?

Подсказка 3

Давайте введём переменные для суммы цифр стоящих на чётных местах и для суммы на нечётных. Сделайте выводы об сумме и о модуле разности.

Подсказка 4

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

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

Обозначим через $a$ и $b$ сумму цифр, стоящих на чётных и нечётных местах соответственно. Из признаков делимости на 9 и на 11 следует, что $a +b$ кратно 9, а $|a− b|$ кратно 11. Но все цифры чётные, поэтому $a+ b$ делится на 18, а $|a − b|$ — на 22. Также заметим, что $|a− b|≤ a+ b$ . Если $a +b= 18$ , то $|a − b|= 0$ . Но из этого следует, что $a= b= 9$ , чего не может быть в силу чётности $a$ и $b$ . Если $a+ b≥ 54$ , то в нашем числе будет не менее 7 цифр, поскольку 8·6 = 48 < 54. Пусть $a +b= 36$ . Тогда $|a − b|=22$ или $|a− b|= 0$ . В первом случае одно из чисел $a$ и $b$ равно 29, а другое – 7, чего не может быть. Во втором случае $a= b= 18$ . Заметим, что 18 нельзя представить в виде суммы менее чем трёх чётных цифр, поэтому наше число хотя бы шестизначное. Осталось заметить, что наименьшее шестизначное число, удовлетворяющее условиям задачи, — это 228888. Действительно, первая цифра не может быть меньше 2, вторая — тоже, поскольку если она равна 0, то общая сумма цифр не больше $2+ 8⋅4< 36$ .

Ответ: 228888