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

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

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

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

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

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

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

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

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

Задача 1#76757

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

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

Подсказка 1

Найдите способ перечислить все хорошие числа. Как можно оценить их количество?

Подсказа 2

Если число делится на два последовательных натуральных числа, то оно делится и на их произведение. Как можно оценить количество чисел кратных 3*5? k(k+2) при произвольном нечетном k?

Подсказка 3

Их количество не превосходит n/15 и n/k(k+2) соответственно. При каком k таких чисел уже не найдется?

Подсказка 4

При k больше, чем √n. Как теперь можно оценить общее количество хороших чисел?

Подсказка 5

Оно не больше, чем сумма n/{3*5}+n/{5*7}+...+n{l(l+2)}. Как можно преобразовать данную сумму?

Подсказка 6

Воспользуйтесь тем, что 1/{k(k+2)}=1/{2k}-1/{2k+4}, чтобы преобразовать данную сумму. Наконец, воспользуйтесь ограничениями на n, чтобы доказать, что это число менее n/5.

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

Заметим, что число, делящееся на два последовательных нечётных натуральных числа, делится также на их произведение. Поэтому количество чисел от $1$ до $n,$ делящихся на $2$ фиксированных нечётных числа $k$ и $k+ 2$ не превосходит $--n-- k(k+2) + 1.$ Также заметим, что число, не превосходящее $n$ может делиться на $k(k+ 2)$ только в случае, когда $k(k+ 2)≤ n.$ Обозначим наибольшее нечетное число, не превосходящее $√- n,$ через $l,$ то есть для него верно, что $-n- l≤ l+2,$ а также $√ - l≤ n.$ Тогда суммарное количество хороших чисел не превосходит

n n n 3⋅5 + 5⋅7 + ...+ l(l+-2)

Заметим, что

( ) -n- +-n- +...+--n---= n -1-+ -1-+ ...+ --1--- = 3⋅5 5 ⋅7 l(l+ 2) 3⋅5 5⋅7 l(l+2)

1 (1 1 1 -1-) 1 ( 1 -1-) = 2n 3 −5 +...+ l − l+2 = 2n 3 − l+2

Тогда вся сумма равна

n n n l n √- 6 − 2l+-4 + l≤ 6 + 2 ≤ 6 + n∕2

Легко видеть, что при $n> 1000,√n∕2< n∕30,$ откуда вся сумма меньше, чем $n∕6+ n∕30 =n∕5,$ что и требовалось доказать.

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

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

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

Задача 2#76760

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

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

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

Задача 3#78894

На доске написано натуральное число, в записи которого нет цифр $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.$

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

Задача 4#78904

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

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

Задача 5#79758

Найдите все такие натуральные $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$

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

Задача 6#79761

Обозначим через $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$ — противоречие.

Курсы

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

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

Задача 7#83387

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

Пусть $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. Пусть существует $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> 1$ . Во втором же $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> 1$ . Во втором же $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′+b′d< c′d′+b′c′ < c′d′+b′a′ = 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$ . Отметим, что это множество вместе с каждым вектором $(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$ и обе координаты вектора $v0$ по модулю не больше, чем $c$ — это опять противоречит выбору $u$ . Значит, $y0 < 0$ и $c− y0 > c$ . Теперь выберем наибольшее целое неотрицательное $m$ , при котором $x0− a− ma≥ 0$ . Ясно, что это неотрицательное значение строго меньше, чем $a$ . Тогда вектор $v0− mu =(x0− a− ma, y0− c− mc)$ и есть искомый вектор. Действительно, все нужные неравенства уже установлены, осталось только исключить случай $x0 − a− ma =0$ , но в таком случае из уравнения прямой $ℓ$ получаем $xc− ya= p$ , $− (y0− c− mc)a =p$ , что невозможно в силу того, что $a> c> 0$ , $− y0+c +mc ≥1 +c+ mc≥ 2$ .

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

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

Задача 8#83856

Выписаны 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$

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

Задача 9#86099

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

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

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

Задача 10#89260

Вася написал на доске числа от $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.$

Ответ:

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

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

Задача 11#90238

Найдите все натуральные $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$ нет

Интенсивы

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

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

Задача 12#91097

Назовем несократимую дробь $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$

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

Задача 13#91976

Найдите сумму всех натуральных чисел $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

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

Задача 14#96476

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

Ответ: да

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

Задача 15#100472

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

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

Задача 16#73203

Число называется шикарным, если у него есть два делителя, отличающихся на $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.$ Следовательно, шикарных чисел больше.

Ответ:

Шикарных

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

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

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

Задача 17#75199

Имеется натуральное число $n > 2015.$ Возьмём остатки от деления числа $2n$ на $2,3,4,...,n.$ Докажите, что сумма этих остатков больше $2n.$

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

Обозначим сумму остатков от деления $2n$ на числа $1,2,...,n$ через $S . n$ Мы докажем, что $S > 3,5n n$ при $n >1000.$

Числа $n 2$ не делится нацело ни на какое нечётное число, отличное от $1,$ значит, остаток от деления $n 2$ на такое число не меньше $1.$ Отсюда легко вывести, что для любого нечётного $k> 1$ остаток от деления $n 2$ на $l 2 k$ не меньше $l 2 .$

Отсюда следует, что

Sn ≥n0 +2n1+ 22n3 +...+ 2mnm

где $n i$ –– количество не превосходящих $n$ чисел вида $2i(2k +1),k > 1,$ а $m$ определяется условиями $32m ≤n ≤ 3⋅2m+1$ (нет смысла брать большее $m,$ так как тогда выражение в скобке будет равно нулю).

Рассмотрим $(i+1)$ -e слагаемое $2in. i$ Число $n i$ равно числу не превосходящих $n$ членов арифметической прогрессии $3⋅2i,5 ⋅2i,7 ⋅2i,...$ Число таких членов не меньше $n−3⋅2i, 2i+1$ и, значит, это слагаемое не меньше $n− 3⋅2i−1. 2$

Заменив сумму в правой части первыми восемью слагаемыми, получим

n −1 2 6 7 n Sn > 82 − 3(2 + 1+ 2+ 2 +...+ 2 )>4n − 3⋅2 = 3,5n +(2 − 384)

При $n >1000$ выражение в скобке положительно, то есть $Sn > 3,5n.$

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

Задача 18#75880

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

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

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

Пусть число после первого укорачивания равно $n2,$ а после третьего — $m4.$ Тогда $100m4$ отличается от $n2$ только двумя последними цифрами, то есть $2 22 2 2 100 ≥n − (10m ) = (n− 10m )(n+ 10m )≥0.$ Так как по условию изначальное число больше миллиона, то $4 2 m ≥ 1000,10m > 100,$ что возможно только если $2 n =10m$ (иначе $2 2 (n− 10m )(n+ 10m )> 1⋅100$ ). Значит, вторая и третья цифры исходного числа — нули, и куб $3 k,$ получающийся после второго укорачивания, оканчивается на $0.$ Следовательно, четвертая и пятая цифры исходного числа — тоже нули (куб числа, делящегося на $10,$ делится и на $3 10$ ), и после пятого укорачивания мы получим число $k--3 -n-2 (100) = (100).$ Поскольку в разложение числа, являющегося одновременно точным квадратом и точным кубом, все простые множители входят в степенях, кратных $6,$ это число является точной шестой степенью.

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

Задача 19#83231

На доску выписаны числа $1,2,3,...,2 00...0 2 1◟00◝н◜ул ◞ей$ . Можно ли покрасить половину этих чисел в красный цвет, а оставшиеся в синий так, чтобы сумма красных чисел делилась на сумму синих?

Источники: КМО - 2023, третья задача первого дня для 8-9 классов, автор Белов Д.А. (cmo.adygmath.ru)

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

Обозначим самое большое выписанное число через $2n$ . Минимальная сумма синих чисел равна

n(n+-1)- 1+ 2+...+n = 2 .

Максимальная сумма красных чисел равна

(n+ 1)+(n+ 2)+...+ (n+ n)=n ⋅n+ 1+2 +...+ n=

2n2+ n(n+ 1) 3n2+ n = -----2-----= ---2--

Так как $3n(n +1)> 3n2+ n$ , отношение суммы красных чисел к сумме синих меньше трех, значит, если все-таки сумма красных чисел делится на сумму синих, частное равно 1 или 2.

В первом случае мы получаем, что суммы красных чисел и синих чисел должны быть равны, поэтому сумма всех выписанных на доску чисел должна быть четна. При этом половина, а именно $1 0◟0 ◝..◜.0◞ 1 100нулей$ , чисел нечетна. Поэтому сумма всех чисел на самом деле нечетна, и частное не может быть равно 1.

Во втором случае обозначим сумму синих чисел через $S$ . Сумма красных чисел равна $2S$ , а сумма всех выписанных чисел равна $3S$ , то есть делится на 3. На самом же деле сумма выписанных чисел равна

2n(2n+-1) 1 +2+ 3+ ...+ 2n = 2

Признак делимости на 3 гласит: натуральное число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Сумма цифр числа $2n= 210◟000.◝◜ну..л0◞ей 2$ равна 4 , а сумма цифр числа $2n+ 1$ равна 5 . Поэтому оба этих числа не делятся на 3 , тогда и сумма всех выписанных чисел на 3 не делится, и второй случай также невозможен.

Ответ: нет

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

Задача 20#89870

Дано натуральное число $a> 1.$ Определим функцию

√ - f(n)= n +[a{n 2}].

Докажите, что существует такое натуральное $n,$ что $f(f(n))= f(n)$ , но $f(n)⁄= n.$

Напомним, что $[x]$ — целая часть $x,$ то есть наибольшее целое число, не превосходящее $x,$ а ${x} =x − [x]$ — дробная часть $x.$

Источники: СПБГОР - 2023, 11.5 (см.pdmi.ras.ru)

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Дирихле. Для любого иррационального числа $𝜃$ и натурального числа $m$ найдется такое число $k$ , $1≤ k≤ m− 1$ , что $1- {k𝜃}< m$ или $1- {k𝜃}> 1− m$ .

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Кронекера. Для любого иррационального числа $𝜃$ и любых чисел $α$ , $β$ , $0 ≤α <β < 1$ , найдется такое натуральное число $n$ , что ${n𝜃}∈ (α,β)$ .

_________________________________________________________________________________________________________________________________________________________________________________

Применим теорему Дирихле для $√ - 1 𝜃 = 2+ a$ и $m =a$ и найдем такое $1≤ k≤ a− 1$ , что

{ √- 1 } 1 { √- 1 } 1 k( 2+ a) < a или k( 2+ a) > 1− a.

______________________________________________________________________________________________________________________________________________________

В первом случае имеем неравенство $a−ak< {k√2}< a+1a−k$ . Применим теорему Кронекера для

𝜃 =√2, α= k и β = a+-1− {k√2}> k, a a a

получим, что найдется такое $n$ , что $k< {n√2}< a+1− {k√2} a a$ . Для этого $n$ имеем

k< a{n√2}< a(a+-1− {k√2})< a( a+1-− a−-k)= k+ 1. a a a

Следовательно, $√- [a{n 2}]=k$ и $f(n)= n+ k$ . Поскольку

k a− k √- √ - a+1- 1= a + a < {n 2}+{k 2} < a ,

дробная часть числа $√- (n+ k) 2$ меньше, чем $1 a$ , поэтому

√- [a{(n +k) 2}]=0.

В итоге $f(n)= n+ k,$ поэтому

f(f(n))= f(n+ k)= n +k= f(n)⁄= n

______________________________________________________________________________________________________________________________________________________

В случае ${k(√2 + 1)}> 1− 1 a a$ выполняется неравенство