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

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

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

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

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

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

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

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

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

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

Дано натуральное число $n.$ Для каждого простого числа $p$ из промежутка $[n,n2]$ посчитали число $1, p$ и все полученные числа сложили. Докажите, их сумма меньше $2.$

Источники: СпбОШ - 2021, задача 11.5(см. www.pdmi.ras.ru)

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

Подсказка 1

Давайте попробуем посчитать количество чисел от n до n², которые делятся на простое p(тоже из этого отрезка). Как можно оценить это число?

Подсказка 2

Мы знаем, что таких чисел ровно [n²/p]. Но с целой частью работать не очень удобно, поэтому снизу можно поджать выражением n²/p - 1. А что можно сказать про разные p? Существуют ли числа из [n, n²], которые делятся на p₁ и p₂, если p₁ и p₂ из отрезка [n, n²]?

Подсказка 3

Все такие числа уникальны(то есть, для каждого p свой набор чисел, который делятся на p и пересечений по этим наборам нет). В таком случае, как можно оценить количество чисел из [n, n²], которые делятся на какое-то простое из [n, n²]?

Подсказка 4

Количество всех чисел — это Σ(n²/p - 1) по всем простым из нашего отрезка. А как её можно оценить сверху(помните, что мы смотрим на Количество чисел) и снизу?

Подсказка 5

Очевидно, что n² больше чем наша сумма, так как на рассматриваемом отрезке чисел: n² - n + 1. Оценку снизу получить сложнее, давайте посмотрим на Σ(n²/p), что из неё надо вычесть, чтобы получить сумму меньше, чем наша?

Подсказка 6

Если из Σ(n²/p) вычесть n², то мы получим сумму меньше чем наша, ведь количество слагаемых в сумме не больше n². Какие оценки мы получили и как из них получить оценку на Σ(1/p)?

Подсказка 7

Финальные оценки — это n² > Σ(n²/p - 1) > Σ(n²/p) - n². Остаётся сократить всё неравенство на n² и тогда получим, что сумма, которая нам нужна не превосходит 2.

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

Выпишем числа от $1$ до $n2$ и для каждого простого числа $p$ из отрезка $[n,n2]$ подчеркнём те числа, которые делятся на $p.$ Для каждого $p$ будет подчёркнуто в точности $[n2] n2 p > p − 1$ чисел, причём каждое число будет подчёркнуто не больше одного раза. Действительно, если число $k$ подчеркнули как делящееся на простые числа $p$ и $q,$ то $k$ делится и на $2 pq > n ,$ что невозможно. Таким образом, всего подчёркнуто не менее чем $∑ (n2 ) p − 1$ чисел(суммирование ведётся по всем простым числам от $n$ до $2 n$ ). Количество слагаемых в сумме не превосходит $2 n ,$ поэтому вычитается не более $2 n$ единиц. Поскольку количество чисел не меньше $2 n$ и каждое подчёркнуто не более одного раза, всего подчёркиваний меньше, чем $2 n.$ Следовательно,

∑ (n2 ) ∑ n2 n2 > -p − 1 > -p − n2

откуда после сокращения на $n2$ получаем требуемое неравенство $∑ 1p <2.$

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

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

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

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

В стране Лимонии в обращении используются монеты достоинством $3n,3n−1⋅5,3n−2$ . $52,3n−3⋅53,...,3⋅5n−1,5n$ пиастров, где $n$ — натуральное число. Житель страны зашел в банк, не имея при себе наличных денег. Какую наибольшую сумму ему не смогут выдать в банке?

Источники: СПБГУ-21, 11.5 (см. olympiada.spbu.ru)

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

Подсказка 1

Попробуйте воспользоваться индукционными рассуждениями. Пусть для n = k можно выдать все суммы, большие A_k. Что тогда можно сказать A_{k + 1}? Попробуйте выразить его через A_k.

Подсказка 2

Попробуйте доказать, что A_{k+1} = 3A_k + 2 • 5^{n + 1}. Доказываться должно в лоб. Возьмите любое число, большее A_{k + 1} и подумайте, что с ним нужно сделать, чтобы можно было применить предположение. Ну, вероятно избавиться от самой большой степени пятёрки и уменьшить степень тройки.

Подсказка 3

Осталось показать, что нельзя собрать A_{k + 1} монет. Тут идея схожая с предыдущей подсказкой. Предположите, что можно и попробуйте прийти к тому, что тогда на предыдущем шаге индукции можно было собрать A_k.

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

Обозначим нужное число за $A n$ и попробуем его найти по индукции. Заметим, что если из монет $3n,3n−1⋅5,...,3⋅5n−1,5n$ мы можем собрать любое число большее $An$ , то из монет $n+1 n n n+1 3 ,3 ⋅5,...,3⋅5,5$ мы сможем собрать любое число большее $n+1 3An+ 2⋅5$ так: если мы хотим получить число $n+1 A >3An +2⋅5$ , то возьмем такое $k$ от 0 до 2, что $n+1 A − k5$ делилось на 3. Тогда $A−k5n+1- 3 > An$ и значит, его можно представить как $A−k5n+1- n n−1 n 3 = k03 + k13 ⋅5+ ...+ kn5$ , где $ki$ целые и неотрицательные. Тогда $n+1 n+1 n n A = k⋅5 +k03 +k13 ⋅5+ ...+ kn5 ⋅3$ .

Теперь пусть из монет $n+1 n n n+1 3 ,3 ⋅5,...,3⋅5 ,5$ мы сможем собрать число $n+1 B =3An +2 ⋅5$ , то есть $B = k03n+1+ k13n ⋅5 +...+ kn5n⋅3+ kn+1 ⋅5n+1$ , где $ki$ целые и неотрицательные. Заметим, что 3 монеты вида $5n+1$ можно обменять на 5 монет $3⋅5n$ . Значит, можно считать, что $kn+1 ≤2$ . С другой стороны, $B− kn+15n+1 = 3An +(2− kn+1)5n+1$ делится на 3, и значит, $kn+1 ≡ 2 (mod 3)$ и $kn+1 = 2$ . Тогда $n+1 B−2⋅53---= An =k03n+ k13n−1⋅5+ ...+ kn5n$ , где $ki$ целые и неотрицательные. Это значит, что из монет $3n,3n− 1⋅5,...,3⋅5n−1,5n$ мы смогли собрать $An$ ?!

Значит, мы доказали, что из монет $3n+1,3n ⋅5,...,3⋅5n,5n+1$ можно собрать любое число большее $B = 3An+ 2⋅5n+1$ и нельзя собрать $B = 3An+ 2⋅5n+1$ . Значит $An+1 = 3An +2⋅5n+1$ . Тогда $An+1− 3An +2 ⋅5n+1− 5(An − 3An− 1+2 ⋅5n)= An+1− 8An+ 15An −1 = 0$ . Из этого рекурсивного отношения получаем, что $An =a3n+ b5n$ . Тогда $An+1 − 3An +2⋅5n+1 = a3n+1+b5n+1− a3n+1− 3⋅b5n+2 ⋅5n+1 = 5n(2b− 10)=0$ и значит $b= 5$

Заметим, что для $n =1$ мы можем получить все числа хотя бы 10, так как для любого $A ≥10$ существует $k$ от 0 до 2 такое, что $. A − 5k..3$ и $A − 5k ≥0$ . Значит, $A = 5k +3 ⋅ A−35k$ . Так же $9=3 ⋅3$ , $8 =3+ 5$ , а вот 7 получить уже не получится. Значит $A1 =7 =3a+ 5b= 3a+25$ . Отсюда $a =− 6$ и $A = 5⋅5n− 6⋅3n$ .

Ответ:

$5⋅5n− 6⋅3n,n ∈ℕ$

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

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

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

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

Пусть $p$ — наименьшее простое в разложении $n.$ Тогда $n− p,n− 2p,...,n− (⌈-n⌉− 1)p 2p$ не взаимно просты с $n$ и не являются его делителям. Действительно, если $n$ делится на $n− kp,$ то $kp$ делится на $n− kp,$ то есть $kp ≥n − kp,k≥ n∕2p.$ Поэтому, если $n- (⌈2p⌉ − 1)> k,$ то $n$ точно не является решением уравнения $f(n)= k.$ Остался случай, когда $n p ≤K = 2(k +1).$ То есть, если $n= pt$ при $t >1,$ то $p≤ t≤ K.$ Следовательно $2 n= pt≤K .$ А значит, $n$ ограничено. Если $n = p,$ то $f(n)= 0< k.$ Таким образом, для каждого $k$ существует только конечное число таких $n$ (не более $2 4(k+ 1)$ ).

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

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

Можно ли в выражении $A⋅5n+ B ⋅3n−1+ C$ подобрать натуральные коэффициенты $A,B$ и $C$ так, чтобы ни один из них не делился на 8, но результат при любом натуральном $n$ делился на $8?$

Источники: ФЕ - 2021, 10.1 (см. www.formulo.org)

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

Подсказка 1

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

Подсказка 2

Нам поможет сравнение по модулю и его свойства! Попробуйте выделить выражения, дающие такой же остаток от деления на 8, что и искомое. Внимание: они зависят от чётности n.

Подсказка 3

Остался теперь уже гораздо более простой перебор и задача решена!

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

Если $n ..2 .$ , то $A⋅5n+ B⋅3n−1+ C ≡A +3B + C (mod 8).$

Если $n$ не делится на 2, то $n n−1 A ⋅5 +B ⋅3 +C ≡ 5A + B+ C (mod 8).$

Тогда если $A = 2$ , $B = 4$ и $C =2$ , то оба выражения делятся на 8.

Ответ: да

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

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

Натуральное число $n$ назовём удачным, если его можно единственным образом разбить в сумму 10 различных натуральных чисел (порядок слагаемых не важен). Найдите все удачные числа.

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

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

Подсказка 1

Если у нас число представляется единственным образом, то это значит, например, что мы не можем как-то уменьшить одно число на 1, увеличить другое на 1 и получить новое разбиение. Положим, что у нас есть числа a₁ < a₂ < … < a₁₀, что тогда можно сказать, в соответствии с нашими рассуждениями выше, об a₁? Перекладывается ли это на a₂?

Подсказка 2

Мы можем сказать, что a₁ = 1, так как если a₁ > 1, то выходит, что мы можем уменьшить на 1 a₁, увеличить на 1 a₁₀, и это будет новым разбиением. Но ведь аналогично можно рассуждать и относительно a₂, a₃, … Когда этот процесс должен закончиться?

Подсказка 3

Мы можем проводить такие рассуждения вплоть до a₉, но вот с a₁₀ так же не получится. Подумайте, может ли a₁₀ быть равен, скажем, 100? А 20? А какие тогда он может принимать значения и почему (рассуждайте похожим образом, как с остальными a_i)?

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

Пусть число $n$ — удачное, $n =a + a + ...+a 1 2 10$ , где $a < a <...<a 1 2 10$ — натуральные слагаемые. Если предположить, что $a >1 1$ , то $n$ можно разбить в сумму различных натуральных слагаемых еще одним способом:

n =(a1− 1)+ a2+ ...+(a10+1)

Таким образом, $a1 = 1$ .

Далее, если предположить, что $a >2 2$ , то для $n$ опять можно привести другое разбиение:

n =a1+ (a2− 1)+ a3+...+(a10 +1)

Значит, $a2 =2$ . Продолжая так далее, получаем $a3 = 3$ , $a4 = 4,...,a9 = 9$ . Если $a10 >11$ , то $a9+ 1< a10− 1$ , и снова можно сконструировать другое разбиение.

Наконец, нетрудно видеть, что при $a10 = 10$ или $a10 = 11$ получающиеся числа 55 и 56 являются удачными.

Ответ: 55 и 56

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

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

Вычислите с точностью до одной десятой значение выражения

∘ -----∘------√------- 86+41 86 +41 86+ ...

Источники: Межвед - 2021, 10.7 (см. v-olymp.ru)

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

Подсказка 1

Это выражение, как мы можем заметить, бесконечное по записи, а потому, например, кусок выражения после числа 41 равен всему выражению целиком.

Подсказка 2

Если так, то мы можем просто обозначить наше выражение за x и составить уравнение на эту величину!

Подсказка 3

Если наше выражение равно x, то x = sqrt(86 + 41x). Осталось лишь решить это несложное уравнение и показать, какой из корней нам подходит!

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

Пусть

∘ -----∘------√------ F = 86 +41 86+ 41 86+ ...

Тогда $F$ является положительным корнем уравнения

F2 =86+ 41F

Отсюда находим $F = 43$ .

_________________________________________________________________________________________________________________________________________________________________________________

В официальных решениях на сайте олимпиады доказывается, почему выражение для $F$ определено и на самом деле является действительным числом через критерий существования предела у монотонной последовательности. Но тогда корректнее было бы переформулировать условие задачи (и в идеале ещё не давать задачу 9-классникам), а при данной формулировке получается, что достаточно показать невозможность другого значения, кроме как 43.

Ответ:

$43$

Курсы

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

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

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

Петя написал на доске натуральное число $A.$ Если его умножить на $8,$ то получится квадрат натурального числа. А сколько существует таких трёхзначных чисел $B,$ для которых $A ⋅B$ тоже является квадратом натурального числа?

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

Если $8A$ — квадрат натурального числа, то любое простое число, большее 2, входит в $A$ в четной степени, а двойка — в нечетной. Значит, и в $B$ любое простое число, большее 2, должно входить в четной степени, а двойка — в нечетной, то есть $AB$ должно иметь вид $2 2x$ . Следовательно, нам надо найти количество таких $x$ , что $2 2x$ — трехзначное. Другими словами,

2 1000> 2x ≥100

2 500> x ≥ 50

Подойдут $x$ от 8 до 22, их 22 - 7 = 15.

Ответ: 15

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

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

Пусть $p$ и $q$ — взаимно простые натуральные числа. Лягушка прыгает по числовой прямой, начиная в точке $0.$ Каждый раз она прыгает либо на $p$ вправо, либо на $q$ влево. Однажды лягушка вернулась в $0.$ Докажите, что для любого натурального $d <p+ q$ найдутся два числа, посещённые лягушкой и отличающиеся ровно на $d.$

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

Подсказка 1

Какой есть частный случай пары (p;q)?

Подсказка 2

p = q = 1. С ним все понятно, теперь считаем, что p и q различны, пусть p < q. Что можно сказать о длине пути, который пропрыгала лягушка?

Подсказка 3

Заметим, что его длина делится на p и q, тогда и на pq, так как p и q взаимно просты.

Подсказка 4

Тогда длина пути равна kpq, сколько прыжков сделала лягушка?

Подсказка 5

Лягушка сделает kq "коротких" прыжков вправо и kp "длинных" прыжков влево. Подумайте, как при взаимно простых p и q можно представить d.

Подсказка 6

d = ap - bq. Подумайте, какими можно выбрать a и b.

Подсказка 7

Давайте назовем каждую серию из a+b последовательных прыжков лягушки окном. Сколько всего будет окон?

Подсказка 8

Окон будет ровно k(p+q). Нам нужно окно, где лягушка сделала a коротких и b длинных прыжков и сдвинулась на d = ap - bq.

Подсказка 9

Такое окно найдётся, если есть окно, где коротких прыжков не менее a, и окно, где их не более a. Докажите, что существует такое окно.

Подсказка 10

А что, если сдвигать первое окно по кругу, пока мы не дойдем до второго? Сколько всего будет коротких прыжков в окнах?

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

Первое решение. Случай $p= q = 1$ очевиден. Иначе $p$ и $q$ различны, пусть $p< q.$ Всего лягушка пропрыгала путь, длина которого делится на $p$ и на $q,$ а значит, и на $pq,$ так как $p$ и $q$ взаимно просты. Тогда длина пути равна $kpq$ для некоторого натурального $k,$ и лягушка сделала $kq$ «коротких» прыжков вправо и $kp$ «длинных» прыжков влево.

Известно, что при взаимно простых $p$ и $q$ можно представить $d$ в виде $d= ap− bq$ с целыми $a$ и $b.$ Это равенство, очевидно, сохранится, если одновременно увеличить (или уменьшить) $a$ на $q$ и $b$ на $p.$ Поэтому можно выбрать $a$ натуральным и не превосходящим $q.$ При этом будет неотрицательным (иначе $d> p+q),$ и так как $a≤ q,$ то $b<p$ (ведь $d >0).$ Поэтому $a+ b< p+ q ≤ k(p+ q).$

Назовём каждую серию из $a+ b$ последовательных прыжков лягушки окном. Условно считаем, что за последним прыжком лягушки идёт её первый прыжок (как при движении по кругу), поэтому окно может состоять и из нескольких последних и первых прыжков. Тогда всего окон ровно $k(p+ q)$ штук.

Надо найти окно, где лягушка сделала ровно $a$ коротких прыжков (и $b$ длинных) — тогда она сдвинется на $d$ за эти $a+ b$ прыжков. Такое окно найдётся, если есть окно, где коротких прыжков не менее $a,$ и окно, где их не более $a:$ можно сдвигать первое окно по кругу, пока не дойдём до второго, число коротких прыжков в окне каждый раз меняется максимум на $1,$ поэтому будет момент, когда оно равно $a.$

Сложим число коротких прыжков во всех окнах — получим $kq(a +b),$ ведь каждый прыжок учил $a+b$ раз. Окон $k(p+ q),$ и в среднем на окно придётся $kqk(a(p++bq))$ коротких прыжков. Это число равно

kq(a+-b)-= qa-+qb= pa+-qa−-d= a− -d-- k(p +q) p +q p+q p+ q

что больше $a− 1$ и меньше $a.$ Значит, найдётся окно, где коротких прыжков не менее $a,$ и окно, где их не более $a.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Лягушку из условия назовём старой. Будем считать, что она пропрыгивает свою последовательность ходов бесконечное число раз по циклу. Посадим на прямую новую лягушку в точку $d$ и заставим её прыгать ту же последовательность прыжков, что прыгает старая (тоже в бесконечном цикле).

Множество чисел, посещённых новой лягушкой, получается из множества чисел, посещённых старой, сдвигом на $d.$ Если хотя бы одно число из нового множества совпадет с числом из старого, то обратный сдвиг даст нам искомую пару чисел. Предположим, что этого не произойдёт.

Как и в предыдущем решении, представим число $d$ в виде $ap− bq$ для некоторых неотрицательных $a$ и $b.$ Заставим старую лягушку пропрыгать $a +b$ ходов по её циклу; она окажется в точке $e =xp− yq,$ где $x+ y = a+b.$ Так как $a− x = y− b,$ разность координат новой и старой лягушек кратна $p +q :$

d− e= (a − x)p− (b− y)q = (a− x)(p+ q)

Далее пустим лягушек прыгать одновременно: старую по продолжению исходной траектории, а новую — по сдвинутой. На каждом шаге разность их координат будет либо не меняться (если они прыгают в одну сторону), либо меняться на $p +q$ (если одна прыгает на $+ p,$ а другая на $− q).$ Таким образом, разность всегда будет оставаться кратной $p+q;$ при этом она, по предположению, не может становиться нулевой, поэтому она всегда будет сохранять знак.

Пусть лягушки пропрыгали полный цикл и вернулись (новая в $d,$ а старая в $e).$ Количество ходов в цикле обозначим через $T.$ Сумму всех чисел, посещённых новой лягушкой (без учёта начальной позиции), обозначим через $S, 1$ а сумму чисел, посещённых старой, — через $S.$ С одной стороны, числа на соответствующих ходах отличались не менее чем на $p +q,$ причём разность всегда имела один и тот же знак, поэтому $|S1 − S|≥ T(p+q).$ С другой стороны, набор чисел, посещённых новой лягушкой за цикл, отличается от аналогичного набора старой лягушки сдвигом на $d,$ поэтому $|S1− S|= Td$ (отметим, что эти наборы могут содержать некоторые числа по несколько раз, если в течение цикла лягушка посещала их неоднократно). Подставляя и сокращая на $T,$ получаем $d≥ p+ q,$ что противоречит условию задачи.

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Как и в решении $2,$ будем считать, что лягушка прыгает в бесконечном цикле. Также воспользуемся представлением $d =ap− bq$ для неотрицательных $a$ и $b,$ сумму $a +b$ обозначив через $r.$

Через $δi$ обозначим разность между положениями лягушки в момент $i+r$ (то есть через $i+ r$ шагов после начала) и в момент $i.$ Так как их разделяет $r$ шагов, то

δi = xp− (r− x)q = ap +(x− a)p− bq− (r− x− b)q =

= d+ (x − a)p+(x− (r− b))q = d+ (x− a)(p+q)

Если $δi$ равно $d,$ то мы нашли искомые позиции. Предположим противное, пусть $δi ⁄= d$ для всех $i.$ Тогда все числа $δi$ имеют вид $d+ (p+q)ki$ для целых $ki ⁄= 0.$

Заметим, что разность между $δi$ и $δi+1$ определяется тем, какими были $(i+ 1)$ -й и $(i+r+ 1)$ -й шаги; разобрав случаи, нетрудно убедиться, что она равна $± (p+q)$ или $0.$ Это означает, что числа $δi$ либо все меньше $0,$ либо все больше $0.$

Рассмотрим позицию лягушки через $rT$ шагов, где $T$ — количество шагов в её цикле. С одной стороны, она равна сумме $δ0+ δr +δ2r+...+δr(r − 1),$ которая по доказанному выше должна быть либо отрицательной, либо положительной. С другой стороны, через $rT$ шагов лягушка вернётся на позицию $0.$ Противоречие.

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

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

Рассмотрим такие натуральные числа $a,b$ и $c,$ что дробь

ab+-c2 k = a+ b

является натуральным числом, меньшим $a$ и $b.$ Какое наименьшее количество натуральных делителей может быть у числа $a+ b$ ?

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

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

Первое решение. Поскольку число $a+b$ больше единицы, оно имеет хотя бы два различных делителя. Докажем, что их не может быть ровно два, т. е. что число $a +b$ не может быть простым. Домножив равенство из условия на знаменатель, получим

2 ab+ c =ka +kb

или, что то же самое,

2 2 2 ab− ka− kb +k = k − c.

Разложив обе части на множители, придем к соотношению

(a− k)(b− k)=(k− c)(k+ c).

Поскольку $k< a$ и $k < b,$ обе скобки в левой части положительны и, значит, $c< k.$ Тогда существуют такие натуральные числа $x,y,z$ и $t,$ что

a− k= xy, b− k= zt, k− c =xz и k+ c= yt. (∗)

Например, можно положить

x= НОД (a− k,k− c), t= НОД(b− k,k+ c), y =(a− k)∕x

и $z = (b− k)∕t.$ Тогда первые два равенства будут выполнены по определению; с другой стороны, $k − c$ делит $xz, ak+c$ делит $yt,$ поэтому из равенства произведений вытекают написанные равенства.

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

a+b =(a− k)+(b− k)+ (k− c)+ (k +c)= xy+ zt+ xz+ yt=(x+ t)(y+z).

Таким образом, число $a+b$ представляется в виде произведения двух натуральных чисел, больших 1, и, значит, не является простым.

Наконец, несложно увидеть, что $a +b$ может иметь ровно три различных делителя. Например, если $a= 10, b= 15, c= 5,$ то

2 k= 10⋅15+5- =7, иa+ b= 25= 52 10+ 15

имеет три делителя.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Приведём другое доказательство того, что число $p= a+ b$ не может быть простым. Предположим противное.

Будем считать, что $a≤ b.$ Тогда число

kp= ab+c2 = a(p − a)+ c2 =ap+ c2− a2

делится на $p$ и меньше, чем $ap.$ Следовательно, число

a2− c2 =(a− c)(a+ c)

положительно и кратно $p.$ Тогда первая скобка положительна и

a− c< a+ b= p,

поэтому она не делится на $p.$ Вторая скобка также положительна и

a+ c< 2a≤ a+ b=p,

поэтому она также не делится на $p.$ Мы пришли к противоречию, поэтому предположение неверно. Таким образом, $a+ b$ — составное число и, значит, оно имеет хотя бы три делителя.

Ответ:

три делителя

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

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

Пусть $p$ — простое число, большее $3.$ Докажите, что найдется натуральное число $y,$ меньшее $p∕2$ и такое, что число $py+ 1$ невозможно представить в виде произведения двух целых чисел, каждое из которых больше $y.$

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

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

Положим $p= 2k+ 1.$ Предположим противное: для каждого из чисел $y = 1,2,...,k$ существует разложение $py +1= a b, y y$ где $ay > y,by >y.$ Заметим, что каждое из чисел $ay$ и $by$ строго больше $1,$ а также что $ay < p,by < p,$ иначе $ayby ≥ p(y +1)> py+ 1.$ Значит, каждое из $p− 1$ чисел набора $a1,b1,a2,b2,...ak,bk$ лежит в множестве из $p− 2$ чисел ${2,3,...,p− 1}.$ Таким образом, в этом наборе найдутся два равных числа. Пусть каждое из этих двух чисел равно $d.$

Пусть эти равные числа имеют равные индексы в наборе, то есть $ay = by =d$ при некотором $y.$ Тогда $2 py+ 1= d,$ поэтому число $2 d − 1= (d − 1)(d +1)= py$ делится на простое $p.$ Так как $1≤d − 1< d+ 1≤ p,$ это может быть лишь при $d+ 1= p.$ Тогда соответствующее значение $y$ равно $d− 1= p− 2 =2k− 1,$ что при $p >3$ больше, чем $k.$ Противоречие (так как $y ≤k$ ).

В противном случае существуют индексы $y1 < y2$ такие, что $1≤ y1 < y2 < d,$ для которых числа $py1+ 1$ и $py2+ 1$ делятся на $d.$ Тогда и $p(y2− y1) =(py2 +1)− (py1+ 1)$ также делится на $d.$ Из взаимной простоты чисел $d$ и $p$ получаем, что $y2− y1$ делится на $d,$ а это невозможно, так как $0< y2− y1 < y2 < d.$

Таким образом, в каждом случае получено противоречие и, следовательно, указанное в условии задачи число $y$ всегда найдётся.

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

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

Можно ли отметить в ряду натуральных чисел бесконечно много чисел так, чтобы разность любых отмеченных чисел (где из большего вычитается меньшее) была квадратом натурального числа?

Источники: Олимпиада Эйлера, 2020, РЭ, 8 задача(см. old.mccme.ru)

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

Пусть так отметить числа можно. Пронумеруем отмеченные числа в порядке возрастания: $a ,a,...,a ,.... 1 2 n$ Положим $bn = an+1− an.$ По условию в последовательности $b1,b2,...,bn,...$ любое число является квадратом натурального числа. Кроме того, квадратом является любая сумма $bk +bk+1+⋅⋅⋅+bn = an+1− ak.$ Пусть $2 b2+ ⋅⋅⋅+ bn = (cn) .$ Очевидно, $c2 < c3 < ⋅⋅⋅< cn <....$ Поэтому найдется такое $n,$ что $2cn +1> b1.$ Сумма $b1+ b2 +...+ bn$ тоже должна быть квадратом некоторого натурального числа $d.$ При этом $2 2 d > (cn) ,$ откуда $2 2 2 2 2 d ≥ (cn +1) = (cn) +2cn+ 1> (cn) + b1 =d .$ Противоречие.

Ответ:

Нельзя

Интенсивы

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

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

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

В ряд выписывают дроби $-1-,-2-,-3-,...,4060,4061. 4061 4060 4059 2 1$ Сколько всего целых чисел встретится в таком ряду?

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

Подсказка 1

Наши числа имеют вид (4062-x)/x. Нам надо найти количество целых чисел, когда x пробегает от 1 до 4061. Как вы думаете, при каком условии на x это число будет целым?

Подсказка 2

(4062-x)/x = 4062/x - 1. Тогда нужно всего лишь обеспечить целость числа 4062/x. Стало быть x- делитель 4062. Посчитайте количество делителей числа 4062 (только не забудьте, что x<4062) и радуйтесь жизни!

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

Сумма числителя и знаменателя каждой дроби равна $4062$ , то есть каждая дробь имеет вид $4062−x x$ , где $x$ – натуральное число, не превосходящее $4061$ . Число $4062−x 4062 x = x − 1$ будет целым, когда число $x$ - делитель $4062$ .

Поскольку $4062 =2 ⋅3 ⋅677$ , где числа $2$ , $3$ и $677$ – простые, у числа $4062$ будет $8$ делителей. И так как $x< 4062$ , $x$ может принимать одно из $7$ значений (все делители $4062$ , кроме самого числа), чтобы дробь $4062−x x$ была целой.

Ответ: 7

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

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

Девочка Катя не любит число $239.$ Она выписала несколько различных чисел, ни одно из которых не содержит последовательность цифр $239$ (подряд и именно в таком порядке). Докажите, что сумма обратных к этим числам не больше $30000.$

Источники: ИТМО 2019

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

Подсказка 1

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

Подсказка 2

Скорее всего, потом нам придется оценивать сумму ряда. Лучше выразить количества разрядов через некоторое n.

Подсказка 3

Будем рассматривать (3n+1), (3n+2) и (3n+3)-значные числа. Сколько их может быть?

Подсказка 4

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

Подсказка 5

Например, для (3n+1) разряда есть 9 вариантов для первой цифры и не более 999ⁿ вариантов для каждой следующей тройки.

Подсказка 6

Оцените величины выписанных чисел.

Подсказка 7

Например, (3n+1)-значные числа должны быть не меньше 10³ⁿ. Как тогда можно оценить величины обратных?

Подсказка 8

Например, для (3n+1)-значных чисел обратные не будут превосходить 1/10³ⁿ. Осталось только записать ряд и оценить его величину!

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

Количество подходящих $3n+ 1$ -значных чисел не больше, чем $9 ⋅999n :9$ вариантов для первой цифры и не более 999 вариантов для каждой следующей тройки цифр. Каждое из них не меньше $3n 10 .$

Количество подходящих $3n +2$ -значных чисел не больше, чем $n 90⋅999 .$ Каждое из них не меньше $3n+1 10 .$

Количество подходящих $3n +3$ -значных чисел не больше, чем $n 899 ⋅999 .$ Каждое из них не меньше $3n+2 10 .$

Пусть количество знаков в самом большом выписанном числе не превосходит $3N + 3.$ Тогда общая сумма чисел не больше

∑N ( n n n ) 9⋅999n--+-90⋅999n-+ 899⋅999-n = n=0 1000 10⋅1000 100 ⋅1000

∑N ( n) = (9+9 +8,99) 999n- ≤30⋅---1--- = 30000 n=0 1000 1 − 0,999

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

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

Дано натуральное число $n >10$ и все его натуральные делители

1= a1 <a2 <...<ak =n

Докажите, что $a1a2+a2a3+ ...+ aka1 ≤ n2.$

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

Подсказка 1

Тут стоит подумать про какие-то максимально банальные оценки, связанные с делителями.

Подсказка 2

Подумайте, как оценить сверху некоторый делитель a_k.

Подсказка 3

Попробуйте посмотреть на количество делителей, больших a_k. Сколько их и как это можно применить для оценки a_k?

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

Отбросим сначала $a a k 1$ и оценим сумму остальных слагаемых. Заметим, что $a ≤ n-, k−i i+1$ так как есть по крайней мере $i$ делителей числа $n,$ больших $ak−i.$ Тогда указанную сумму можно оценить как

2( 1 1 1 ) a1a2+ a2a3 +...+ ak−1ak ≤n 1⋅2 + 2⋅3 + 3⋅4 +...

где количество слагаемых меньше $n.$ Представляя каждую дробь $k⋅(k1+1) = 1k − k1+1$ и сокращая, получаем оценку $n2⋅(1− 1n)= n2− n.$ Осталось заметить, что отброшенное слагаемое $aka1 = n,$ откуда и следует оценка на $n2.$

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

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

Натуральное число $n$ назовём кубоватым, если $n3+ 13n− 273$ является кубом натурального числа. Найдите сумму всех кубоватых чисел.

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

Подсказка 1

Какой мы знаем распространённый метод для поиска кубов и квадратов целых чисел? Намёк: нам могут помочь ФСУ!

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Осталось лишь сделать небольшой числовой перебор и задача решена!

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

При $n= 21$ это число равно $213,$ то есть кубу.

Если $n> 21$ , то

3 3 2 3 3 (n +1) = n +3n + 3n+ 1> n +13n− 273> n

то есть это не может быть кубом.

Если $n< 21,$ то $n3+13n− 273< n3.$ Также для $n >8,$ выполняется неравенство

3 3 3 2 n +13n− 273>(n− 1) =n − 3n + 3n− 1

то есть выражение не может быть кубом. Осталось перебрать $n ≤8.$

Если $n= 8,$ то $n3+ 13n − 273= 73.$

Если $n= 7,$ то $n3+ 13n − 273= 161$ ?!

Если $n= 6,$ то $n3+ 13n − 273= 21$ ?!

Если $n≤ 5,$ то $n3+ 13n − 273≤ 53 +13⋅5− 273 <0$ ?!

Ответ: 29

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

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

Пользуясь равенством $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$

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

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

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

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

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

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

Рассмотрим числа, полученные при вычеркивании $0,1,...,499$ последних цифр. Предположим, что все они имеют вид $bki i$ , где $b ≤ 500 i$ . Покажем, что все $bi$ различные. Предположим противное, пусть нашлись два числа $ki bi$ и $kj bj$ такие, что $bi = bj$ . Ясно, что $ki ⁄= kj$ . Пусть $ki >kj$ . Вычтем из первого числа число $kj a bj ⋅10$ , где $a$ подобрано так, чтобы количество цифр в уменьшаемом и вычитаемом было одинаковым. Полученная разность делится на $k bjj$ . Но при этом эта разность равна числу, которое было вычеркнуто, то есть в нём не более $499$ цифр. А в числе $bkjj$ хотя бы $500$ цифр. Таким образом, делимость невозможна. Значит, все $bi$ различны. Но тогда среди них найдётся $bi$ , большее $500$ , потому что их $501$ . Получили требуемое.

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

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

Определим последовательность $a ,a,a ,... 1 2 3$ формулой $a = [n 20201817]. n$ Докажите, что существует такое натуральное число $N,$ что среди любых $N$ подряд идущих членов последовательности есть такой, десятичная запись которого содержит цифру $5.$ (Как обычно, через $[x]$ обозначается наибольшее целое число, не превосходящее $x.$ )

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

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

Обозначим $β =-1-. 2017$ Напомним, что частный случай неравенства Бернулли $(1+ x)2017 ≥ 1+2017x$ (при $x≥ −β$ ) можно переписать в виде $β 1+ βy ≥ (1 +y)$ (при $y = 2017x ≥− 1$ ).

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Для любого натурального п верны неравенства $n+1+β ( 1)β n+β n+1 ≤ 1+ n ≤ n$

Доказательство. Правое неравенство сразу следует из упомянутого неравенства Бернулли. Для доказательства левого, применяя то же неравенство, получаем

( )β ( )β nn+-1 = 1− n+11 ≤1 −n-β+1 = n+n-1+−1-β

откуда $( ) (1+ 1n)β = nn+1 −β ≥ n+n+11−β-≥ n+n1++β1 .$

______________________________________________________________________________________________________________________________________________________

Лемма 2. Для любого натурального п верны неравенства $nβ − 1≤ an+1− an ≤ 2nβ + 1.$

Доказательство. Поскольку $n1+β − 1< an ≤ n1+β,$ достаточно доказать, что $nβ ≤(n+ 1)1+β − n1+β ≤ 2nβ,$ или

( 1)β 1≤ (n +1) 1+ n − n ≤2

Применяя лемму $1,$ получаем

( )β (n+ 1) 1+ 1 − n ≥(n+ 1)n+-1+β-− n= 1+ β > 1 n n+ 1

что доказывает левое неравенство. Аналогично, для правого имеем $(n+ 1)(1 +n1)β − n ≤ (n+1)(nn+β)− n = n(1+βn)+β-< 2.$

______________________________________________________________________________________________________________________________________________________

Перейдём к решению задачи. Покажем, что число $N =22017+ 1000$ подходит. Для этого достаточно доказать, что при любом натуральном $n ≥22017$ число с пятёркой в десятичной записи найдётся даже среди чисел $an,an+1,...,an+1000.$ Поскольку $n≥ 22017,$ найдётся натуральное $k$ такое, что $10k−1 ≤$ $≤ nβ∕2 <10k.$ Покажем, что даже среди $(k+ 2)$ -х с конца цифр чисел $an,an+1,...,an+1000$ встретится пятёрка, откуда и будет следовать требуемое.

По лемме $2,$ при каждом $d= n,n +1,...,n+ 999$ имеем $a − a ≤ 2dβ +1 ≤2 ⋅(2n)β +1 <4⋅nβ +1< 9⋅10k d+1 d$ это означает, что $(k+ 2)$ -я цифра при переходе от $a d$ к $a d+1$ либо не изменяется, либо увеличивается на $1$ (при этом $9$ переходит в $0$ ). С другой стороны, по той же лемме

( ) ad+100− ad ≥ 100 nβ − 1 ≥ 2⋅10k+1− 100 ≥10k+1;

это означает, что за $100$ таких переходов $(k+ 2)$ -я цифра обязана хотя бы раз изменить своё значение (на следующее по циклу). Значит, за $1000$ переходов она примет все $10$ возможных значений, в частности, побывает и пятёркой.

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

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

Обозначим через $s(n)$ сумму цифр числа $n.$ Докажите, что для любого $C > 0$ найдется такое натуральное $n,$ что $( 2) s(n)>s n + C.$

Источники: Ломоносов-2016, 11.8 (см. olymp.msu.ru)

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

Возьмем $n =103k− 102k− 1.$ Тогда $s(n)= 27k− 1,$ поскольку в записи этого числа $3k$ цифр, причем все кроме одной — девятки, и одна восьмерка. Раскроем скобки:

2 6k 5k 4k 3k 2k n = 10 − 2⋅10 +10 − 2⋅10 + 2⋅10 + 1

Поэтому в числе $n2$ все цифры равны $0,$ кроме одной единицы, одной двойки, двух восьмерок, и двух блоков из $k− 1$ девяток. Поэтому

(2) sn = 2⋅9⋅(k− 1)+ 8+ 8+2 +1= 18k+ 1

Выбирая $k> C,$ получаем, что

s(n)− s(n2)= 27k − 1 − 18k− 1= 9k − 2 >C

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

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

Известно, что в десятичной записи числа $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,$ что не так. Противоречие.

Ответ:

да