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

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

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

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

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

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

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

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

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

Задача 1#76757

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

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

Для каждого остатка оценим сверху количество таких $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)

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

Расположим наши числа по убыванию, $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)

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

Если число $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.$ Сперва он сосчитал количество выписанных чисел, представимых в виде суммы точного куба и точной шестой степени. Затем он подсчитал количество выписанных точных квадратов. Какой из результатов оказался больше?

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

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

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

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

Пусть данное число является квадратом натурального числа $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≤ 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#102317

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

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

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

Ответ:

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

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

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

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

Задача 17#102331

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

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

Предположим, что такое возможно. Тогда пусть $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,$ а левая — нет. Противоречие. Значит, условие, требуемое в задаче, никогда не выполняется.

Ответ:

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

Задача 18#104579

Докажите, что существует натуральное число $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$ решений.

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

Задача 19#73203

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

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

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

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

Ответ:

Шикарных

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

Задача 20#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.$