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

Оценочная теория чисел

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

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

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

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

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

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

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

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

Пусть $p$ — простое число, а числа $a ,...,a 1 p$ — целые. Докажите, что существует целое число $k,$ такое, что числа $a + k,a + 2k,...,a + pk 1 2 p$ дают не менее $p∕2$ различных остатков по модулю $p.$

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

Подсказка 1

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

Подсказка 2

Зайдëм с конца. Если при каком-то k различных остатков не меньше (p + 1)/2, то задача решена. Это возможно, когда сумма количеств по всем k хотя бы p(p + 1)/2. Попробуйте это доказать.

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

Для каждого остатка оценим сверху количество таких $k,$ в для которых этот остаток есть среди чисел $a +k,a + 2k,...,a + pk. 1 2 p$ Сначала заметим, что $ai+ ik$ сравнимо с $aj + jk$ ровно при одном $k$ от $1$ до $p.$ И пусть при этом единственном $k$ число $ai+ik$ сравнимо с $ri,j$ по модулю $p.$ То есть каждой паре $i,j$ соответствует единственный остаток $ri,j.$

Рассмотрим фиксированный остаток $r.$ Предположим, что $ap− r$ не делится на $p.$ Пусть он встречается ровно $i$ раз. Обозначим через $a1,...,ai$ количества чисел (среди $a1+k,a2+ 2k,...,ap+ pk$ ), которые равны $r$ по модулю $p$ на шагах, где встречается хотя бы один раз остаток $r.$ Тогда $a1+...+ap−1 = p− 1,$ так как любой такой остаток будет встречаться $p− 1$ раз в сумме для всех $k$ (по одному разу за каждый $ai,$ кроме $ap$ ). А количество пар, которым соответствует остаток $r,$ равно

a (a − 1) a(a − 1) -1-12----+ ...+ -i-i2---

Обозначим его через $mr.$ С другой стороны

i=a1+ ...+ ai− (a1− 1)− ...− (ai− 1)≥(p− 1)− mr

Если же $ap− r$ делится на $p,$ то $a1+ ...+ ai = p+ (p− 1).$ То есть в этом случае $mr ≥ 2p− 1− mr.$

Теперь просуммируем по всем остаткам по модулю $p.$ Получим, что сумма количеств различных остатков среди $a1+ k,a2+ 2k,...,ap+ pk$ по всем $k$ от $1$ до $p$ не меньше, чем

(p− 1)⋅(p − 1)+ 2p − 1− m0 − ...− mp−1 =p2− p(p− 1)= p(p+-1) 2 2

Тогда при каком-то $k$ количество различных остатков не меньше, чем

p(p+-1) p+-1 p 2p = 2 > 2

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

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

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

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

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

На доске написано натуральное число, в записи которого нет цифр $1,2$ и $9.$ Докажите, что если это число умножить на $3,$ то хотя бы одна из этих цифр в нём появится.

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

Пусть наше число $N.$ Тогда получается, что если $N$ начинается на $3,4,5,6,7$ или $8$ и имеет $k$ цифр, то $3⋅10k−1 ≤ N < 9⋅10k−1,$ поэтому $k−1 k−1 9⋅10 ≤ 3N < 27⋅10 ,$ откуда $k−1 k 9⋅10 ≤ 3N < 3⋅10,$ т.е. число $3N$ либо имеет $k$ цифр и начинается с цифры $9,$ либо имеет $k+ 1$ цифру и начинается с цифры $1$ или $2.$

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

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

Дано натуральное число $a.$ Докажите, что любое натуральное число $n$ можно домножить на какое-то натуральное число, меньшее $10a,$ так, чтобы десятичная запись произведения начиналась на $a.$

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

Пусть $k$ — наименьшее целое число такое, что $n ≤10k,$ а $d$ — наименьшее натуральное число такое, что $dn ≥10ka$ (иначе говоря, $k =⌈lg n⌉$ и $⌈ k ⌉ d = 10 a∕n$ ). Тогда $k (d− 1)n< 10 a,$ то есть $k k dn< 10 a+ n≤ 10 (a+ 1);$ это значит, что число $dn$ начинается на $a.$ Значит, если $d< 10a,$ то $d$ — требуемый множитель.

Предположим, что $d> 10a.$ Из выбора $d$ получаем, что $k 10 a> 10an,$ то есть $k−1 10 >n,$ что противоречит выбору $k.$ Наконец, если $d =10a,$ то целое число $dn∕10$ также начинается на $a,$ то есть подходит число $d∕10= a< 10a.$

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

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

Найдите все такие натуральные $n,$ для которых существует хотя бы $n−1 2$ таких $k,$ что $n+ k2$ — точный квадрат.

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

Выясним, при каких $k$ число $n +k2$ является квадратом. Пусть $n+ k2 =m2,$ тогда $n =(m − k)(m+ k).$ Пусть $d$ и $n d$ — пара делителей $n$ ( $n d > d$ ). Решая систему из уравнений $n m − k= d,m + k= d,$ получаем, что $nd−d- k = 2 .$ То есть количество таких $k$ равно количеству таких пар делителей $n (d, d),$ у которых одинаковая чётность. С одной стороны, их должно быть хотя бы $n−1 2 .$ С другой стороны, их не более $√ - n$ (потому что в каждой паре один делитель не больше $√ - n$ ). Значит, $n−1 √- -2-≤ n.$ Решая это неравенство, получаем, что $√- n <3 +2 2.$ Значит, могут подойти лишь $n =1,2,3,4,5.$

Очевидно, что $n= 1$ подходит. Двойка не подойдёт, потому что разница между минимальными квадратами $3,$ и она растёт. $3$ подходит, например, $3+ 12 = 22.4$ не подойдёт, потому что разница между минимальными квадратами $3,$ а следующая минимальная разница уже $5.5$ не подойдёт, потому что есть пример $5+ 22 = 32,$ однако третья минимальная разница между квадратами уже $7.$

Ответ:

$n =1,3$

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

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

Обозначим через $S (m )$ сумму цифр натурального числа $m.$ Докажите, что существует бесконечно много натуральных $n$ таких, что

n (n+1) S(3 )≥ S 3

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

Пусть таких чисел конечное число, тогда для всех $n,$ начиная с некоторого $N,S(3n)<S(3n+1).$ Но $3n,3n+1$ делятся на $9,$ поэтому $n S(3 )$ и $n+1 S(3 )$ делятся на $9,$ значит, $n n+1 S(3 )≤S(3 )− 9.$ Тогда $N+k N S(3 )≥S(3 )+ 9k> 9k,$ значит, число имеет более $k$ знаков: $N+k k 3 >10 .$ Отсюда, при $k= N$ получаем $2N N 3 >10$ — противоречие.

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

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

Цель этого сюжета — доказательство следующего утверждения:

Пусть $p$ — нечётное простое число. Докажите, что существует ровно $(p− 3)∕2$ упорядоченных четвёрок $(a,b,c,d)$ натуральных чисел, для которых $ab+ cd =p$ и $max(c,d)<min(a,b).$

Если $r$ — остаток по модулю $p,$ то назовём четвёрку ( $a,b,c,d$ ), удовлетворяющую условиям выше, $r$ -четверкой, если $c ≡ra$ (mod $p).$

1. Докажите, что если $r$ -четвёрка существует, то $r∈{2,3,...,p− 2}.$

2. Докажите, что для данного $r$ существует не более одной $r$ -четвёрки.

3. Докажите, что если $r$ -четверка существует, то $(p − r)$ -четвёрки не существует.

4. Докажите, что для всякого $r∈{2,3,...,p− 2}$ существует либо $r$ -четвёрка, либо $(p − r)$ -четвёрка.

Источники: ЮМШ - 2024, сюжет 1 (см. yumsh.ru)

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

Пункт 1. Подсказка 1

Перепишем требуемое так: доказать, что для r=0, r=1 и r=p-1 r-четвёрки точно нет. Каким путём хочется доказать это утверждение?

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

Конечно! Давайте пойдём от противного. Если 0-четвёрка существует, то что следует из c ≡ ra (mod p)? Но разве это не противоречит равенству из условия?) Окей... Пусть теперь 1-четвёрка существует. Попробуем аналогично случаю r=0 прийти к противоречию! Какое тогда сравнение по (mod p) можно написать?

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

Верно! Тогда p = ab + cd ≡ ab + rad = a(b+d) (mod p). Какая делимость отсюда следует? Как можно оценить a и b+d?

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

Да! Либо a, либо (b+d) делится на p. Значит либо a≥p, либо (b+d)≥p. Хмм... но по условию ab + cd = p... Осталось написать цепочки неравенств и прийти к противоречию! Абсолютно аналогично докажем и для r=p-1.

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

Опять пойдём от противного. Пусть для одного r существуют две четвёрки: (a,b,c,d) и (a`, b`, c`, d`). Воспользуемся равенством из условия и попробуем связать четвёрки между собой.

Пункт 2. Подсказка 2

Ага. Можно заметить, что ac' ≡ ara' ≡ ca' (mod p). Попробуем аналогично связать b,d и b`,d`.

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

Тогда ac`- a`c, bd`- b`d кратны р. Предположим, что эти разности одновременно не равны нулю. Попробуем тогда оценить bd`- b`d, пользуясь тем, что ac`- a`c > 0. Какое противоречие получаем?

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

Да! ac` > p > ab. Отсюда с` > b, c` > d. Не забываем, что bd`- b`d кратно р, но разве оно больше p?) С этим случаем покончено. А что, если всё-таки какая-то разность равна нулю (пусть bd`- b`d=0)? Что можно сказать про делители переменных, исходя из условия ab+cd = p = a`b`+ c`d`? Как связать это с bd`= b`d.

Пункт 2. Подсказка 5

Заметим, что из ab + cd = p = a`b` + c`d` следует, что b и d, b` и d` взаимнопросты. Тогда из bd`= b`d следует, что b=b`, d=d`. Как теперь можно преобразовать равенство ab+cd = a`b` + c`d`? Что из него следует?

Пункт 2. Подсказка 6

Конечо! (a-a`)b=(c-c`)d. Но b и d взаимнопросты. Значит (a-a`) делится на d, (c-c`) делится на b! Обозначим это так: (a-a`)=dx, c-c`)=bx. Осталось рассмотреть случай x>0 и x<0, пользуясь неравенствами между переменными и заключить, что четвёрки совпадают!

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

Пусть (a,b,c,d), (a`,b`,c`,d`) — две четвёрки, удовлетворяющие условиям с r и c r` = p − r соответственно. Давайте действовать, как в прошлом пункте. Какие тогда цепочки сравнений по mod p тогда можно написать? Какое противоречие с делимость на p получается?

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

Верно! Можно получить, что ac`+a`c, bd`+b`d кратны p. Аналогично прошлому пункту, пусть с`≥b, тогда с`>c,d. Оценим bd`+b`d>0. Какое противоречие с делимостью на p можно получить?

Пункт 3. Подсказка 3

Да, bd`+b`d = 0, но bd`+b`d >0 !? Окей, пусть c`< b. Попробуем оценить a`c+ac и b`d+bd`. Чему могут быть равны эти выражения (помним, что они краты p).

Пункт 3. Подсказка 4

a`c+ac` < ab+ a`b` < 2p, аналогично b`d+bd`<2p. Тогда, т.к. они делятся на p и больше нуля, то они равны p! А что еще равно p по условию?)

Пункт 3. Подсказка 5

Да! Запишем разность ab + cd и a`c+ac`. Получаем делимость на a. Такс... чего-то не хватает. Вспомним, что четвёрки упорядоченные. Что, если а — наибольшее из всех чисел? Выполняется ли полученная делимость?)

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

Окей...Давайте искать четверки так: на плоскости рассмотрим все векторы с целыми координатами (x,y), где y≡rx (mod p). Рассмотрим вектор u=(a,c), где сумма a+c минимальная. Что тогда нужно сделать, чтобы доказать существование r-четвёрки (или (p-r)-четвёрки)?

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

Давайте на прямой с уравнением xc − ya =p (пусть a>c) искать точку (d,−b) такую, что d> 0, d< a,d <b,c<b — тогда четвёрка (a,b,c,d) и будет искомой. С какими прямыми нам теперь нужно работать, чтобы найти иском точку?

Пункт 4. Подсказка 3

Да! Рассмотрим прямую y=-x. Пусть точка (x₀,y₀)∈ℓ с целыми x₀,y₀ лежит выше прямой y+x= 0, а точка v₀=(x₀− a,y₀− c) — (нестрого) ниже. Какие условия теперь надо проверить?

Пункт 4. Подсказка 4

Конечно! Проверим нужные нам неравенства, которы мы писали выше! Проверьте эти условия, пользуясь выбором вектора (сумма координат минимальна).

Пункт 4. Подсказка 5

Теперь выберем наибольшее целое неотрицательное m, при котором x₀−a−ma≥0. Тогда вектор v₀−mu = (x₀−a−ma, y₀−c−mc) — искомый. Какой случай осталось проверить, прежде чем разобраться со случаем с>a?

Пункт 4. Подсказка 6

Осталось только исключить случай x−a−ma =0! Разберём теперь c>a аналогично, просто по сути переобозначив переменные, закончив решение задачи!

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

1. Требуется исключить варианты $r=0,1,p− 1.$ Если существует $r$ -четверка $(a,b,c,d)$ при $r= 0,$ то $c$ натуральное кратное $p,$ и тогда $ab+cd> p$ — противоречие.

Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= 1.$ Тогда

p= ab+cd≡ ab+ rad= a(b+d) (mod p)

Получаем, что $.. a(b+ d).p.$ Тогда либо $a,$ либо $b+ d$ делится на $p.$ Тогда либо $a≥ p,$ либо $b+ d≥ p.$ В первом случаем получаем, что $ab+ cd≥p +cd> p.$ Во втором же $ab+cd≥ 2b+d ≥p+ 1.$ Получаем, что $1$ -четверки не существует.

Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= p− 1.$ Тогда

p= ab+cd≡ ab+ rad= a(b− d) (mod p)

Получаем, что $.. a(b− d).p.$ Тогда либо $a,$ либо $b− d$ делится на $p.$ Тогда либо $a≥ p,$ либо $b+ d≥ p$ $(b− d⁄= 0,$ поскольку $b>d).$ В первом случаем получаем, что $ab+ cd ≥p+ cd> p.$ Во втором же $ab+ cd≥ b+d> b− d≥ p.$ Получаем, что $(p− 1)$ -четверки тоже не существует.

2. Пусть $(a,b,c,d),$ $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с одним и тем же $r.$ Тогда $ac′ ≡ara′ ≡ca′ (mod p),$ аналогично $bd′ ≡− rdd′ ≡ b′d (mod p).$ Т.е. $ac′− a′c,$ $bd′− b′d$ кратны $p.$

Предположим, что эти разности одновременно не равны нулю. Пусть не умаляя общности $ac′− a′c> 0,$ тогда $ac′ >p >ab,$ т.е. $c′ > b$ и тем более $c′ > d.$ Отсюда получаем, что

|bd′− b′d|< max(bd′,b′d)< max(c′d′,b′c′)= b′c′ <a′b′ < p

откуда (т.к. $|b′d − b′d|$ кратно $p)$ получаем $bd′− b′d= 0$ — противоречие.

Пусть теперь одна из исходных разностей равна нулю (не умаляя общности $bd′− b′d).$ Отметим, что из равенств $ab+ cd =p =a′b′+ c′d′$ следует взаимная простота $b$ и $d,$ $b′$ и $d′.$ Поэтому из равенства $bd′ = b′d$ следует, что $b= b′$ и $d =d′,$ а из него — $(a− a′)b= (c′− c)d.$ В силу взаимной простоты $b$ и $d$ имеем $a− a′ =dx,$ $c′− c =bx.$ При $x> 0$ это противоречит условию $c′ < b′ = b,$ при $x< 0$ — условию $c< b$ . Значит, $x= 0,$ $a= a′,$ $c= c′$ — четверки полностью совпадают.

3. Пусть $(a,b,c,d)$ , $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с $r$ и c $r′ = p− r$ соответственно. Тогда $ac′ ≡− ara′ ≡ −ca′ (mod p),$ аналогично $bd′ ≡ −rdd′ ≡− b′d (mod p).$ Т.е. $ac′+a′c,$ $bd′+ b′d$ кратны $p.$

Пусть $′ c≥ b,$ а значит, $′ c> c,d,$ тогда, аналогично прошлому пункту,

′ ′ ′′ ′′ ′′ ′ ′ bd + bd< cd + bc< cd + ba =p

— противоречие с делимостью на $p.$ Значит, $c′ < b$ и, аналогично $c< b′,$ $d′ < a,$ $d< a′.$ Тогда $a′c+ ac′ <ab+ a′b′ < 2p,$ поэтому из делимости $ac′+ a′c= p$ и аналогично $b′d+ bd′ = p.$

Предположим теперь, не умаляя общности, что $a$ — наибольшее из чисел. Вычитая из $ab+cd$ равное ему $ac′+ ca′,$ получаем $a(b− c′)=c(a′− d),$ откуда из взаимной простоты $a$ и $c$ получаем, что $a′− d$ делится на $a$ — противоречие с тем, что $a< a′,$ $a′− d> 0.$

4. Рассмотрим на плоскости множество всех векторов $(x,y)$ с целыми координатами $x,y$ такими, что $y ≡ rx (mod p)$ или $y ≡(p− r)x (mod p).$ Отметим, что это множество вместе с каждым вектором $(x,y)$ содержит также и $(±x,±y).$ Рассмотрим в нашем множестве вектор с минимальной суммой координат. В силу замечания выше можно считать, что вектор $u := (a,c),$ где $a,c> 0,$ $a⁄= c$ (на осях координат и на биссектрисах углов между ними такой вектор лежать не может, поскольку $2 ≤r ≤p− 1),$ если $c≡ (p− r)a (mod p),$ то переобозначим $r$ и $p− r.$ Предположим пока, что $a> c.$ Рассмотрим прямую $ℓ$ с уравнением $xc− ya =p.$ Будем искать точку $(d,− b)$ на этой прямой такую, что $d> 0,d< a,d <b,c<b$ — тогда четверка $(a,b,c,d)$ и будет искомой. Заметим, что если $(x,y)∈ℓ,$ то $(x− a,y − c)∈ℓ.$

Прямая $ℓ$ где-то пересекает прямую $y+ x= 0.$ Пусть точка $(x0,y0)∈ ℓ$ с целыми $x0,y0$ лежит выше прямой $y+ x= 0,$ а точка $v0 :=(x0− a,y0− c)$ — (нестрого) ниже.

Во-первых, проверим, что $x0− a> 0.$ В самом деле, в противном случае $x0 ≤ a.$ Из выбора вектора $u$ имеем

a +c≤ |x0 − a|+|y0− c|= a− x0+|y0+c|

Если $c≥y0$ , то

a − x0+ |y0− c|= a+ c− x0− y0 < a+ c

— противоречие. Если же $y0 > c,$ то $p= x0c− y0a< ac− ac= 0$ — снова противоречие.

Итак, $x0− a> 0.$ Поскольку $(x0− a)+ (y0− c)≤ 0,$ имеем $y0 − c< 0.$ Если $y0 ≥ 0,$ то $0< x0− a ≤c− y0 ≤ c$ и обе координаты вектора $v 0$ по модулю не больше, чем $c$ — это опять противоречит выбору $u.$ Значит, $y < 0 0$ и $c− y > c. 0$ Теперь выберем наибольшее целое неотрицательное $m,$ при котором $x0− a− ma≥ 0.$ Ясно, что это неотрицательное значение строго меньше, чем $a.$ Тогда вектор

v0− mu = (x0 − a− ma,y0− c− mc)

и есть искомый вектор. Действительно, все нужные неравенства уже установлены, осталось только исключить случай $x − a− ma =0, 0$ но в таком случае из уравнения прямой $ℓ$ получаем $xc− ya= p,$ $− (y − c− mc )a =p, 0$ что невозможно в силу того, что $a> c> 0,$ $− y + c+mc ≥ 1+c +mc ≥2. 0$

Наконец обратимся к случаю $c> a.$ В этом случае обозначим $′ a =c,$ $′ c = a$ и построим точно так же четверку $′ ′ ′ ′ (a,b,c,d)$ со всеми нужными свойствами, но такую, что, наоборот $′ ′ a ≡rc (mod p).$ В этом случае, очевидно, $′ ′ ′ ′ (b,a ,d,c)$ будет $p− r$ -четверкой, что нам подходит.

Курсы

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

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

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

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

Источники: КФУ - 2024, 11.3 (см. malun.kpfu.ru)

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

Подсказка 1

Пусть х₁ - наибольшее из чисел. Тогда очевидно х₁>P/S. С таким выражением работать куда проще, чем с абстрактным условием на неизвестное число. Перезапишем его в виде Sx₁>P. Как бы нам доказать это неравенство?...

Подсказка 2

Давайте домножим выражение для суммы всех чисел на х₁. Попарного сравним каждое слагаемое со слагаемыми из суммы квадратов. Что получается?

Подсказка 3

Верно, Sx₁ оказывается не меньше суммы квадратов! А теперь можно заменить всё на введённые в условии обозначения и доказать неравенство.

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

Расположим наши числа по убыванию, $x ≥ x ≥ x ≥...≥x . 1 2 3 100$ Имеем

S = x1+ x2+x3 +...+ x100

x2+x2 +x2+ ...+ x2 > P 1 2 3 100

Умножим первое равенство на $x1,$ получим, что

Sx1 = x2+x1x2+ x1x3+ ...+ x1x100 ≥ x2+ x2 +x2+ ...+ x2 > P 1 1 2 3 100

Следовательно, $x1 > P. S$

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

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

Сколько двузначных натуральных чисел нельзя представить в виде суммы двух палиндромов?

Палиндром - число, читающееся одинаково слева направо и справа налево. Однозначные числа $0,1,...,9$ также считаются палиндромами. Многозначные палиндромы не могут начинаться с 0.

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

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

Подсказка 1

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

Подсказка 2

n + однозначное. А еще n + 11. А что делать с n + 10? Сколько таких чисел и чему они равны?

Подсказка 3

Предположим, что число n + 10 = a + b. Какими тогда могут быть a и b?

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

Если число $n$ является палиндромом, то числа $n,n +1,n+ 2,...,n +9$ допускают нужное представление. Поэтому числа от $10$ до $20$ могут быть представлены нужным образом:

10= 9+ 1,11= 11+0,12= 11+1,...,20= 11 +9

Если число $n$ двузначное и является палиндромом, то число $n +11$ также палиндром, и может быть представлено как $(n +11)+ 0$ . Например, если $n = 55,n+ 11= 66 =66+ 0$ . Поскольку разность между соседними двузначными палиндромами равна $11$ , это означает, что все такие числа допускают нужное представление. Осталось рассмотреть числа вида $n+ 10$ , где $n$ — палиндром, то есть числа $21,32,43,54,65,76,87,98$ . Пусть число $n+ 10= a+ b$ . Если и $a$ и $b$ двузначные палиндромы, тогда правая часть делится на $11$ , а левая нет. Значит, одно из слагаемых должно быть однозначным, то есть числом из набора $0,1,...,9$ . Но разность $10$ и любого числа из набора не кратна $11$ . Числа $21,32,43,54,65,76,87,98$ нельзя представить как сумму двух палиндромов.

Ответ: 8

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

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

Вася написал на доске числа от $1$ до $1012.$ Сперва он сосчитал количество выписанных чисел, представимых в виде суммы точного куба и точной шестой степени. Затем он подсчитал количество выписанных точных квадратов. Какой из результатов оказался больше?

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

Подсказка 1

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

Подсказка 2

Найдем количество точных квадратов среди чисел на доске. Несложно показать, что их число равно 10⁶. Как теперь можно оценить количество тех чисел, то представимы в виде точного куба и точной шестой степени?

Подсказка 3

Пусть число n представимо в виде суммы n=a³+b⁶ для некоторых натуральных a и b. Тогда количество чисел n явно не больше, чем количество различных пар (a, b) для которых число a³+b⁶ не превосходит 10¹². Как можно оценить количество таких пар?

Подсказка 4

Если a³+b⁶ не превосходит 10¹², то каждое из чисел a³ и b⁶ строго меньше 10¹². Тогда a имеет меньше 10⁴ возможных значений, b меньше 10², следовательно, количество таких пар меньше 10⁶.

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

Натуральное число $n$ такое, что $1≤ n2 ≤1012,$ тогда и только тогда, когда $1≤ n≤ 106.$ Таким образом, количество полных квадратов, не превосходящих $12 10 ,$ равно $6 10 .$

Докажем, что количество чисел на доске, представимых в виде суммы точного куба и точной шестой степени, меньше, чем $6 10 .$ Действительно, количество чисел $k$ на доске не превосходит количества пар натуральных чисел $(a,b)$ таких, что $3 6 k =a + b,$ для которых верно неравенство

1≤ a3+b6 ≤ 1012

Таким образом, для каждого из чисел верно, что

3 12 6 12 1 <a < 10 ,1< b < 10

то есть

1< a< 104,1< b< 102

Тем самым мы показали, что количество пар $(a,b)$ меньше, чем $104⋅102 = 106.$

Ответ:

Квадратов больше

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

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

Найдите все натуральные $n$ , для которых число $-n2+-1- [√ n]2+ 2$ — целое.

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

Пусть $k2 ≤ n< (k+ 1)2.$ Обозначим $n= k2+m$ , где $0≤ m≤ 2k.$ Тогда $k≤ √n <(k+ 1)$ $⇒ [√n]= k.$ Тогда получаем дробь, которая является целым числом по условию:

(k2 +m )2+ 1 k4 +2k2m+ m2 +1 ---k2+2--- =------k2-+2-----

Значит, $k4+2k2m +m2 +1 ≡0(mod(k2+2)).$ Получаем, что, $k2 ≡−2(mod(k2+2)).$ Заменим $k$ :

(−2)2+ 2⋅(−2)m + m2+ 1≡ 0(mod (k2+ 2))

m2 − 4m + 5≡ 0(mod(k2+ 2))

Так как $2 2 0≤ m ≤ 2k,0< m − 4m +5 ≤4(k +2).$ Таким образом, $m2-−-4m-+-5 k2+2$ равно 1, 2 или 3.

1) $m2− 4m+ 5= 1⋅(k2 +2)$

$(m − 2)2+ 1= k2+2$

$(m − 2− k)(m− 2+ k)=1$

Такое может быть только если числа равны 1 или -1. Тогда $m − 2 − k =m − 2+ k,k= 0.$ Но тогда $0≤ n <1$ — число будет ненатуральным. Противоречие.

2) $m2− 4m+ 5= 2⋅(k2 +2)$

$m2− 4m+ 1− 2k2 =0$

Рассмотрим левую часть данного уравнения как квадратный трёхчлен относительно $m :$

$D4-=4− (1− 2k2)$

$D4-=2k2+ 3$

Так как $m$ — целое число, $2k2 +3$ — квадрат. Посмотрим на остатки при делении на 3 и на 9:

Если $m ≡0(mod3),$ получаем, что $2k2+ 3≡ 0(mod3)$ и $2k2+3 ≡3(mod9),$ чего не может быть, так как если квадрат делится на 3, то он делится и на 9.

Если $m ≡1(mod3)$ или $m ≡ 2(mod3),$ получаем, что $2k2+ 3≡ 2(mod3).$ Квадрат не может давать остаток 2 при делении на 3.

Значит, такое равенство невозможно. Противоречие.

3) $m2− 4m+ 5= 3⋅(k2 +2)$

$2 2 m − 4m− 3k − 1 =0$

Заметим, что тогда правая часть должна делиться на 3: $2 3k$ делится на 3, $− 3m$ тоже. Тогда $2 m − m − 1$ тоже должно делиться на 3.

Если $m ≡0(mod3),$ получаем, что $− 1≡0(mod3),$ что неверно.

Если $m ≡1(mod3),$ получаем, что $− 1≡0(mod3),$ что неверно.

Если $m ≡2(mod3),$ получаем, что $1≡0(mod3),$ что неверно.

Значит, такое равенство невозможно. Противоречие.

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

Ответ:

таких $n$ нет

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

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

Назовем несократимую дробь $a b$ особенной, если дробь $a+2k- b+2k$ — несократимая для всех натуральных $k.$ Сколько существует особенных дробей, у которых числитель и знаменатель — натуральные числа, не превосходящие $127?$

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

Подсказка 1

Попробуйте собрать какую-то очевидную информацию про рассматриваемые дроби. Какие точно не могут быть особенными?

Подсказка 2

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

Подсказка 3

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

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

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

Посчитаем, сколько таких дробей. Дробей первого вида $126 +126= 252.$ Дроби второго вида, у которых числитель и знаменатель отличаются на $k 2,$ это $k k k 1∕(2 +1),3∕(2 +3),...,(127− 2 )∕127,$ т.е. $k k−1 (127− 2 +1)∕2= 64 − 2 .$ Нужно сложить эти выражения по всем $1 ≤k≤ 6.$ Получится $64⋅6− (1+2 +4+ 8+ 16+32)= 384 − 63= 321.$ Также нужно учесть неправильные дроби, поэтому всего их $642.$ Значит, в сумме выходит $252+ 642= 894.$

Докажем, что все остальные дроби не подходят. Если $a$ и $b$ четные, то дробь сократима. Остаются дроби, у которых числитель и знаменатель отличаются на $d,$ у которого есть нечетный делитель $p> 1.$ Но такая дробь не может быть особенной, поскольку можно выбрать нечетное число $M,$ кратное $p$ и большее, чем $a$ и $b,$ и взять $k= (M − a)∕2$ или $k =(M − b)∕2$ (хотя бы одно из этих чисел натуральное, поскольку $M$ нечетно, и хотя бы одно из $a$ и $b$ нечетно). Тогда дробь $(a+ 2k)∕(b +2k)$ будет сократима на $p,$ поскольку ее числитель или знаменатель, по построению, будет равен $M,$ а значит будет делиться на $p,$ но разность числителя и знаменателя также кратна $p,$ т.е. и числитель и знаменатель кратны $p,$ т.е. дробь сократима.

Остаётся рассмотреть дроби вида $n∕n,$ но в случае $n >1$ они сократимы, а в случае $n= 1$ такая дробь сократима для всех $k.$

Ответ:

$894$

Интенсивы

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

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

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

Найдите сумму всех натуральных чисел $n,$ для которых число $n2+ 7n +1$ является квадратом некоторого натурального числа.

Источники: ДВИ - 2024, вариант 242, задача 2 (pk.math.msu.ru)

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

Подсказка 1

Одно из значений n ищется подбором, попробуйте его сразу угадать!

Подсказка 2

Для остальных n > 1 попробуем сравнить наше выражение с точными квадратами. n² + 7n при выделении полного квадрата даёт (n + 3.5)² - 3.5². Попробуйте с учётом этого сделать вывод о том, будет ли наше выражение больше/меньше или может быть равно (n + 4)², (n + 3)² или (n + 2)². Осталось перебрать не так уж много вариантов, чтобы получить исчерпывающий ответ!

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

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

Пусть данное число является квадратом натурального числа $m.$ Тогда:

2 2 n +7n +1= m |⋅4

2 2 4n +28n+ 4= 4m |+ 45

4n2 +28n+ 49= 4m2 + 45

(2n +7)2− 4m2 = 45

(2n+ 7− 2m)(2n+ 7+ 2m)= 45

Так как первый сомножитель меньше второго, то получаем три случая:

1.

{ 2n+ 7− 2m = 5 2n+ 7+ 2m = 9

Вычтем из второго уравнение первое, получим, что $m = 1.$ А значит, $n = 0$ — не натуральное число.

2.

{ 2n+7 − 2m = 1 2n+7 +2m = 45

Аналогично первому случаю, получаем, что $m =11, n =8.$

3.

{ 2n+7 − 2m = 3 2n+7 +2m = 15

Получаем, что $m =3, n= 1.$

Итак, сумма подходящих $n$ равна $1 +8= 9.$

______________________________________________________________________________________________________________________________________________________

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

Ясно, что $n =1$ подходит, потому что $1 +7+ 1= 32.$ При $n >1$ заметим, что

n2+ 7n+ 1> n2+4n+ 4= (n+ 2)2

так как

3n> 3

Но при этом

n2+7n +1< n2+ 8n+ 16 =(n+ 4)2

Значит, возможна только ситуация, когда

2 2 2 n + 7n+ 1= (n +3) = n +6n+ 9

n= 8

В итоге сумма подходящих значений равна $1 +8 =9.$

Ответ: 9

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

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

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

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

Заметим, что

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

Следовательно, в десятичной записи числа $229$ не больше, чем 10 цифр.

С другой стороны,

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

поэтому в десятичной записи числа $229$ не меньше, чем 9 цифр.

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

Если цифр 10 и они различные, то среди них есть ноль.

Ответ: да

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

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

Пусть $n$ — натуральное число. Игорь выбрал $k$ различных натуральных чисел, не превосходящих $n.$ Затем Саша выписал всех их попарные суммы. Оказалось, что среди выписанных чисел нет двух различных, одно из которых делится на другое. При каком наибольшем $k$ такое могло произойти?

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

Подсказка 1

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

Подсказка 2

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

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

Пусть Игорь выбрал числа $1≤ a < a <⋅⋅⋅< a ≤n. 1 2 k$ Рассмотрим следующие числа, выписанные Сашей:

a1+ a2 < a1 +a3 < ⋅⋅⋅< a1+ ak < a2 +ak < a3+ ak < ⋅⋅⋅< ak−1 +ak < 2n

Чисел всего $(k − 1)+ (k − 2)= 2k− 3$ и все они меньше, чем $2n.$ Покажем, что среди чисел от 1 до $2n$ нельзя выбрать более $n$ чисел так, чтобы ни одно из выбранных чисел не делилось ни на одно другое выбранное число. Пусть удалось выбрать хотя бы $n+ 1$ чисел, обладающих таким свойством, тогда у каких-то двух из них совпадет наибольший нечетный делитель, действительно, нечетных чисел до $2n$ ровно $n.$ Тогда одно из этих чисел будет делиться на другое, противоречие. Значит, $n 2k− 3≤ n⇔ k < 2 + 2.$

Осталось привести пример. Пусть $n = 2l−$ четно, тогда в качестве $ai$ достаточно взять числа от $l$ до $2l.$ Такой пример очевидно подходит, так как минимальная сумма $2l+ 1$ больше половины от наибольшей суммы, которая равна $4l− 1.$ Аналогично, если $n =2l+ 1−$ нечетно, достаточно взять числа от $l$ до $2l+ 1.$

Ответ:

При $n= 2l$ — $k= l+1,$ а при $n= 2l+1$ — $k =l+ 2$

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

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

Существует ли такое натуральное $k,$ что среди любых $k$ подряд идущих натуральных чисел встретится хотя бы один куб натурального числа?

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

Подсказка 1

Чему равна разность между кубами соседних чисел n и n+1?

Подсказка 2

Разность равна 3n^2+3n+1. Существует ли число k, которое было бы больше, чем 3n^2+3n+1 при любом n?

Подсказка 3

Нет, например при n = k данное число, уже больше, чем k.

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

Рассмотрим разность между соседними кубами $n3$ и $(n+ 1)3.$ Эта разность равна $3n2+ 3n +1.$ Пусть мы нашли $k,$ которое удовлетворяет условию. Тогда возьмем $n =k$ и получим, что разность между двумя соседними кубами явно больше $k.$ Получаем противоречие.

Ответ:

Не существует

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

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

Может ли произведение $2024$ последовательных натуральных чисел быть точной $2024$ -ой степенью натурального числа?

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

Подсказка 1

Предположим, что такое возможно. Тогда a²⁰²⁴=x(x+1)...(x+2023). Что можно сказать про a по сравнению с x?

Подсказка 2

Среди чисел х, х+1, ..., х+2023 должно найтись само а. Тогда полезно будет рассмотреть, например, а+1(поймите, почему оно точно должно быть).

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

Предположим, что такое возможно. Тогда пусть $a2024 = x(x+ 1)...(x+ 2023).$ Заметим, что из натуральности $x$ следует, что $x <a <x +2023.$ При $a≤ x$ слева в равенстве $2024$ сомножителя, не больших $x,$ а справа $2024$ сомножителя, не меньших $x, x +1> x.$ Аналогично, противоречие, если $a≥ x+ 2023.$ Тогда в сомножителях справа есть число $a+ 1.$ Оно взаимно просто с $a,$ так что делится на какое-то простое $p,$ на которое не делится $a.$ Значит, правая часть делится на $p,$ а левая — нет. Противоречие. Значит, условие, требуемое в задаче, никогда не выполняется.

Ответ:

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

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

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

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

Докажите, что существует натуральное число $N$ такое, что уравнение

3 3 3 3 x +y + z +t = N

имеет не менее $1000$ решений в натуральных числах.

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

Рассмотрим числа $x,y,z,t$ в промежутке от $1$ до $10k.$ Тогда количество наборов $x,y,z,t$ равно $(10k)4.$ Максимальное значения числа $N$ равно $k 3 3⋅(10 ) .$ Тогда по принципу Дирихле есть число $N$ для которого количество решений хотя бы $k 10 ∕4.$ Взяв достаточно большое $k$ мы получим не менее $1000$ решений.

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

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

Пусть $a , 1$ $a ,...,a 2 10$ — натуральные числа, $a < a < ...< a . 1 2 10$ Пусть $b k$ — наибольший делитель $a , k$ меньший $a . k$ Оказалось, что $b1 > b2 > ...> b10.$ Докажите, что $a10 > 500.$

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

Неравенства из условия влекут

a1 a2 a10 b1 < b2 < ...< b10,

причем для каждого $k ∈{1,2,...,10}$ отношение $ak bk$ — суть наименьший простой делитель $ak$ . Тогда $a10 b10$ не меньше, чем 29 — десятое простое число, а значит

a10 ≥29⋅b10 (∗)

Число $b10$ же является делителем $a10,$ большим 1, а значит не меньше, чем наименьший простой делитель — $a10 b10,$ то есть так не меньше, чем 29. Подставляя полученную оценку в неравенство $(∗)$ имеем

a10 ≥29⋅b10 ≥292 > 500.

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

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

Докажите, что существует такое $c> 0,$ что для любого нечётного простого $p =2k+ 1$ числа $10,21,32,$ …, $kk− 1$ дают хотя бы $c√p-$ различных остатков при делении на $p.$

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

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

Все сравнения в этом решении производятся по модулю $p.$ Если $a$ и $b$ — целые числа, причём $b$ не делится на $p,$ то через $a b$ мы обозначаем тот единственный остаток $c$ по модулю $p,$ для которого $a ≡bc.$

Пусть числа

0 1 2 k−1 1,2 ,3 ,...,k

дают ровно $d$ различных остатков при делении на $p.$ Обозначим $t= [p∕4].$ Тогда выражения вида

(2a)2a−1 2a−1 f(a)= (aa−1)2 = 2 a

при $1≤ a≤ t$ дают максимум $d2$ различных остатков.

Назовём пару натуральных чисел $(a,b)$ таких, что $1≤ a< b≤ t,$ исключительной, если $f(a)≡ f(b).$ Покажем, что для каждого $δ = 1,2,...,t− 1$ существует не более одной исключительной пары $(a,b),$ в которой $b− a= δ.$ Действительно, если $(a,b)$ — такая пара, то из

22a−1a≡ 22b−1b

вытекает, что

a 2δ b ≡ 2 ,

откуда

b= a+ δ ≡ 22δb+ δ,

или $b(1− 22δ)≡ δ.$ Такой остаток $b$ не более чем единственен (поскольку $δ ⁄= 0$ ), а по нему восстанавливается $a.$

Итого, существует не более чем $t− 1$ исключительная пара; обозначим их количество через $S.$ Пусть числа $f(1),f(2),...,f(t)$ дают ровно $l$ различных остатков по модулю $p,$ встречающихся $a1,a2,...,al$ раз соответственно. Тогда

∑l ai = t, S = ∑lC2 . i=1 i=1 ai

Верна следующая цепочка неравенств:

( l l ) ( ) t− 1≥ S = 1 ∑ a2i − ∑ ai ≥ 1 t2− t , 2 i=1 i=1 2 l

откуда

t2 t l≥ 3t−-2-> 3.

Вспоминая, что $l≤d2,$ получаем оценку

--- ---- d> ∘t∕3≥ ⌊∘ p∕12⌋.

Таким образом, в качестве искомой константы $c$ можно взять, например, число $1∕24:$ для простых $p <12$ неравенство $√p d > 24$ тривиально, а для $p >12$ следует из неравенства $[x]≥ x∕2$ при $x> 1.$

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

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

Число называется шикарным, если у него есть два делителя, отличающихся на $2,$ и фееричным, если у него есть два делителя, отличающихся на $3.$ Каких чисел больше от $1$ до $6000$ — шикарных или фееричных?

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

Подсказка 1

Перебрав первые чисел так 20, видно что одних больше половины, а других меньше. Почему так?

Подсказка 2

Если d шикарное, то и kd шикарное (почему?).

Подсказка 3

3 и 4 шикарные, а вот перебирая маленькие числа, нечетных фееричных не нашлось, может это не совпадение?

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

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

Если число кратно $3$ или $4,$ оно точно является шикарным. Заметим, что таких чисел хотя бы $6000 6000 6000 3 + 4 − 12 = 3000.$ Так же заметим, что шикарным является число $35,$ которое не кратно ни $3,$ ни $4.$ Следовательно, шикарных чисел больше.

Ответ:

Шикарных