Оценочная теория чисел —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Оценочная теория чисел

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

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

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

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

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

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

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

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

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

Задача 1#86099

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

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

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

Если число $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

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

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

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

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

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

Задача 3#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$ -четверкой, что нам подходит.

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

Задача 4#79762

Саша написал на доске ненулевую цифру и приписывает к ней справа по одной ненулевой цифре, пока не выпишет миллион цифр. Докажите, что на доске не более $100$ раз был написан точный квадрат.

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

Рассмотрим отдельно числа из нечетного и из четного числа знаков.

Пусть $2 2 x1,x2,...$ — встретившиеся на доске квадраты из четного количества знаков, и в их записи содержится соответственно $2n1,2n2,...(n1 < n2 < ...)$ цифр. Аналогично, пусть $2 2 y1,y2,...$ — встретившиеся на доске квадраты из нечетного количества знаков, и в их записи содержится соответственно $2m1 − 1,2m2 − 1,...(m1 < m2 <...)$ цифр.

Число $2 xk$ содержит $2nk$ цифр и не оканчивается на $0,$ поэтому $2 2nk−1 xk > 10 ,$ откуда $nk−1 xk >10 ,$ Число $2 xk+1$ получается из $xk$ приписыванием некоторого четного количества — обозначим его $2a$ — ненулевых цифр. Поэтому $2a2 2 2a 2 2a 10 xk <xk+1 < 10 xk+ 10 .$ Из левого неравенства получаем $a 10 xk+ 1≤ xk+1,$ следовательно, $2a 2 a 2 2a 2 2a 10 xk+ 2⋅10 xk+ 1≤ xk+1 < 10 xk+10 ,$ откуда $a 2a 2⋅10 xk+1 <10 ,$ т. е. $a xk < 10 .$ Из этого неравенства следует, что $xk$ содержит не более $a$ цифр, т. е. $nk ≤a,$ тогда из неравенства $a 10 xk+ 1≤xk+1$ следует $a+ nk ≤nk+1,$ откуда $2nk ≤ nk+1.$ Аналогичное рассуждение применимо к последовательности $2 yk :yk+1$ получается приписыванием к $y2k$ $2a$ цифр, $yk <10a,$ и $a ≥mk,$ т. е. $mk+1 ≥2mk.$ Теперь заметим, что в каждой из последовательностей $mk$ и $nk$ меньше $50$ членов (так как $m1,n1 ≥ 1$ и $m50$ и $n50$ должны быть не меньше, чем $250 > 1000000$ ).

Итак, всего квадратов на доске окажется не более $100.$

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

Задача 5#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$ — противоречие.

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

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

Курсы

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

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

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

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

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

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

Задача 9#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

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

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

Задача 10#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---= 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,$ что и требовалось доказать.

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

Задача 11#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 не делится, и второй случай также невозможен.

Ответ: нет

Интенсивы

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

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

Задача 12#75880

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

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

Пусть число после первого укорачивания равно $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,$ это число является точной шестой степенью.

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

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

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

Задача 14#73203

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

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

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

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

Ответ:

Шикарных

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

Задача 15#88341

$d ,...,d 1 9$ — различные целые числа. Докажите, что при достаточно больших натуральных $n$ число $(n− d)...(n− d ) 1 9$ имеет простой делитель, больший $20.$

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

Предположим противное, пусть найдётся сколь угодно большое $n,$ при котором выражение имеет только простые делители, меньшие $20.$ При огромных $n$ выражение будет принимать огромные значения, а значит какое-то простое число, меньшее $20,$ будет входить в разложение на простые в огромной степени. Заметим, что всего есть $8$ простых чисел, меньших $20,$ а скобочек $9.$ Поэтому всегда какие-то две скобочки имеют НОД, больший единицы. Понятно, что любые две скобки $n− di$ и $n − dj$ имеют ограниченный НОД, не превосходящий $di− dj$ по абсолютной величине. Из этого следует, что в разложение двух и более скобок не может входить одно и то же простое число в огромных степенях, ведь тогда НОД будет слишком большим. Однако, при огромных $n$ каждая скобка принимает огромное значение, а значит включает в себя один из простых множителей в огромной степени. Как известно, скобочек $9,$ а простых чисел, меньших $20$ — $8,$ значит какие-то две скобки включают одно и то же простое число в огромной степени, противоречие.

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

Задача 16#76734

Найдите все пары $(x;y)$ натуральных чисел, для которых оба числа $x2+8y;y2− 8x$ являются точными квадратами.

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

Подсказка 1

Давайте внимательно посмотрим на наши выражения. Нельзя ли сразу угадать какую-то пару чисел, удовлетворяющую условиям задачи. Пусть x равен какому-то натуральному n. Тогда какой должен быть y, чтобы первое выражение было квадратом?

Подсказка 2

Верно, тогда y=n+2. Можно проверить, что условие задачи выполняется. Что же делать теперь? Ведь y может быть больше или меньше x+2. Какую идею тогда здесь можно применить для дальнейшей оценки наших выражений, чтобы перебирать другие варианты было проще?

Подсказка 3

Да, можно попробовать зажать наши числа между квадратами. Если y < x+2, то первое выражение будет находиться между x² и (x+4)², и остаётся только вариант для (x+2)² = x² + 8y из-за чётности. Аналогично рассматривается, если y > x+2. Тут уже второе число зажимается между y² и (y-4)². Осталось только технически это всё реализовать и найти оставшиеся решения. Победа!

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

Легко проверить, что пары вида $(n;n +2)$ , где n – натуральное число, удовлетворяют условию задачи. Пусть $(x;y)$ – любая другая пара, удовлетворяющая условию задачи. Рассмотрим два случая.

1) Пусть сначала $y < x+ 2$ . Тогда $2 2 2 2 x <x + 8y < x + 8(x+ 2)= (x+ 4)$ , откуда $2 2 x + 8y =(x+ k)$ , где $k ∈{1;2;3}$ . Очевидно, возможен лишь случай $k= 2$ (по чётности), и тогда $x= 2y − 1$ .

Осталось выяснить, при каких натуральных $y$ число $2 2 y − 8x= y − 16y+ 8$ будет точным квадратом. Пусть $2 2 y − 16y+ 8= a$ , тогда $√-----2 y =8± 56+ a$ . Число под корнем должно быть точным квадратом: $2 2 56+ a = c$ , т. е. $2 2 c− a = 56$ .

Разложим $56$ на множители и рассмотрим системы. Учитывая, что $c− a$ и $c+ a$ имеют одинаковую чётность, отбросим лишние, останутся системы:

{ c− a = 4 c+ a = 14

{ c− a = 2 c+ a = 28

откуда $c= 9,a= 5$ или $c= 15$ , $a= 13$ .

При $a= 5$ значение $y = 8± √56+25$ и подходит $y = 8+9 =17$ . При $a= 13$ значение $y = 8± √56+-169$ и подойдет $y =8+ 15= 23$ . Поскольку $x= 2y− 1$ , получаем пары $(45;23)$ и $(33;17)$ .

2) Пусть теперь $y > x+ 2$ , т. е. $x <y − 2$ . Здесь $y > 4$ , и мы имеем $(y− 4)2 = y2− 8(y− 2)<y2− 8x< y2$ . Значит, $y2− 8x= (y − k)2$ , где $k ∈{1;2;3}$ . Опять возможен только случай $k= 2$ (по чётности), так что $y = 2x +1$ .

Пусть $x2 +16x+ 8= b2$ , тогда $x= −8± √56+-b2$ . Выше показано, что число под корнем является точным квадратом только при $b= 5$ или $b= 13$ . Тогда $x =1$ или $x =7$ . Получаем пары $(1;3)$ и $(7;15)$ , первая из которых входит в множество $(n;n+ 2)$ .

Ответ:

$(7;15),(33;17),(45;23),(n;n+ 2),n∈ ℕ$

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

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

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

Задача 17#76536

Число $a >0$ таково, что неравенства $2≤ an ≤ 4$ выполняются ровно при $5$ натуральных значениях $n.$ При скольких натуральных значениях $n$ могут выполнятся неравенства $n 4≤a ≤8?$

Источники: Миссия выполнима-2022, 11.7 (см. mission.fa.ru)

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

Подсказка 1

Пользоваться изначальным неравенством, где n стоит в показателе степени, неудобно. Предположим logₐ 2 = 𝜶 и зададим обычные ограничения на n. Если при заданном а значений n ровно 5, то как можно записать это в виде неравенства?

Подсказка 2

Верно, числа от n до n+4 принадлежат промежутку от 𝜶 до 2𝜶, при этом n-1 уже меньше 𝜶, а n+4 больше 2𝜶. Теперь попробуем преобразовать наше неравенство так, чтобы "зажать" и найти количество значений n, лежащих в промежутке от 2𝜶 до 3𝜶.

Подсказка 3

И не забудьте для каждого количества решений привести примеры!

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

Ясно, что $a> 1.$ Полагая $log 2= α, a$ неравенство $2≤an ≤4$ перепишем в виде $α≤ n≤ 2α,$ а неравенства $4≤ an ≤8$ - в виде $2α ≤n ≤3α.$ Согласно условию, для некоторого натурального числа $m$ выполнены неравенства $m − 1 <α ≤ m< m + 4≤2α <m + 5.$ Из них следует, что

2m − 2< 2α ≤2m < 2m +3< 3α< 2m +5.

Таким образом, неравенствам $2α ≤n ≤3α$ обязательно удовлетворяет четвёрка чисел ${2m;2m +1;2m+ 2;2m + 3}$ и, возможно , одно или оба числа пары ${2m − 1;2m +4}.$

Приведём три соответствующих примера. При $α= 4,6$ имеем $m =5$ и

2m − 1 <2α <3α <2m + 4;

при $α= 5,2$ имеем $m =6$ и выполняются неравенства

2α< 2m − 1 <3α <2m + 4;

наконец, если $α =5,4,$ то $m =6$ и

2α< 2m − 1 <2m + 4< 3α.

Ответ: четыре, пять или шесть

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

Задача 18#76459

Пусть $p ,p,...,p ,... 1 2 n$ — множество всех простых чисел, расположенных в некотором порядке. Может ли случиться так, что для всех натуральных $i$ число $pipi+1−p2i+2- pi+pi+1$ является натуральным?

Источники: Изумруд-2022, 11.5 (см. izumrud.urfu.ru)

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

Подсказка 1

В задачах на делимость (а это по сути она и есть) часто выгодно рассмотреть какое-то красивое число. А поскольку у нас в задаче часто фигурируют простые, рассмотрим p_m = 2. Что тогда хорошего можно сказать про дробь?

Подсказка 2

Тогда, можно сказать, что число меньше 2, а значит равно 1, а значит, p_(m + 1) = p^2_(m + 2) + 2. А мы как-то использовали m? Может ли m быть сильно большим? Как можно ограничить m зная симметричность p_(i + 1) и p_i в нашем числе?

Подсказка 3

Если m > 1, то можно взять рассмотреть (2p_(m - 1) - p^2_(m + 1))/(2 + p_(m - 1)). Тогда, p_(m - 1) = p^2_(m + 1) + 2 = (p^2_(m + 2) + 2)^2 + 2. По какому модулю теперь удобно посмотреть, при наличии тут множественных квадратов?

Подсказка 4

Конечно, mod 3. Ведь тогда, если p_(m + 2) != 3, то p_(m + 1) кратен 3, а значит равен 3. Но тогда p_(m + 2) = 1. А если же p_(m + 2) = 3, то p_(m - 1) = 123. Значит, пришли к общему противоречию с тем, что m > 1, значит, m = 1. При этом, поняли, что mod 3 в этой задаче, как будто, играет важную роль. Давайте тогда , если уж все таки хотим делимость, рассмотрим такие p_k и p_k + 1, что их сумма кратна 3, и при этом они оба отличны от 3. Что это значит тогда для этих двух чисел? А для дроби?

Подсказка 5

Это значит, что остатки mod 3 у этих

Подсказка 6

Это числа, которые сравнимы с 2 mod 3, а после идет сама тройка. Но тогда, если после тройки стоит число = 2 mod 3, то после него идут только числа = 2 mod 3, а значит пришли к противоречию, так как числа = 1 mod 3 существуют. А значит, после 3 идут только числа = 1 mod 3, но тогда перед 3 стоит конечное число простых = 2 mod 3. А то, что таких бесконечно - остаётся вам в качестве упражнения! :)))

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

Предположим, что такое могло случиться. Тогда существует натуральное $m$ такое, что $p = 2. m$ Значит число

2pm+1 − p2m+2 p2m+2 + 4 --2+pm+1---= 2− 2+pm+1-< 2

является натуральным, откуда

p2m+2-+4 =1 и pm+1 =p2 +2 2+ pm+1 m+2

Случай $m> 1$ невозможен, так как тогда число

2pm− 1− p2 p2 + 4 --2+pm−m1+1-= 2− m2++1pm-−1 < 2

также является натуральным, откуда

p2m+1-+4 =1 и p =p2 +2= (p2 + 2)2 +2 2+ pm−1 m−1 m+1 m+2

Теперь если $pm+2 = 3,$ то $pm−1 =123,$ что невозможно. Если же $pm+2 ⁄= 3,$ то

p2 ≡ 1 и p =p2 +2 ... 3 m+2 3 m+1 m+2

Значит,

pm+1 = 3, pm+2 = 1

Это невозможно. Следовательно, $m =1.$

Предположим теперь, что нашлись числа $pk$ и $pk+1$ с различными ненулевыми остатками при делении на 3, то есть

.. pk+pk+1. 3

Поскольку число

pkpk+1 − p2 --p-+-p-k+2 k k+1

является натуральным, то

. pkpk+1 − p2k+2.. 3

Но тогда

p2k+2 ≡3 pkpk+1 ≡3 2

Это невозможно, так как квадраты имеют остатки 0 или 1 при делении на 3. В итоге мы доказали, что числа с остатками 1 и 2 при делении на 3 не могут быть соседними.

Поскольку $p1 = 2,$ это означает, что после $p1$ стоят несколько чисел с остатком 2 при делении на 3, затем где-то стоит число 3. Если после тройки стоит число с остатком 2 при делении на 3, то все числа далее будут с таким же остатком и в последовательности простых чисел не будет ни одного числа с остатком 1 при делении на 3 (такие есть, например, число 7).

Следовательно, после тройки стоит число с остатком 1 при делении на 3 и все числа за ним имеют такой же остаток. Но тогда до тройки стоит лишь конечное число простых чисел с остатком 2 при делении на 3.

Предположим, что простых чисел вида $3k+ 2$ конечное число. Обозначим все такие числа через $q1,q2,...,ql.$ Число $3q1q2...ql− 1$ не делится на простые числа $q1,q2,...,ql$ и даёт остаток 2 при делении на 3. Значит среди его простых делителей должно быть число вида $3k+ 2$ — противоречие.

Ответ: нет

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

Задача 19#74657

Найдите целую часть числа

---1--- ---1--- -----1---- √1 +√2-+ √3+ √4 +⋅⋅⋅+√623-+√624

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

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

Подсказка 1

Гораздо удобнее работать с целочисленными знаменателями-> что нужно сделать, чтобы они стали именно такими? Попробуем оценить число А другим число так, чтобы нам было удобно оценивать их разность двумя способами. Тогда мы сможем прийти к оценке числа А!

Подсказка 3

А+В=24(почему?). Теперь мы можем оценить их разность, группируя соответствующие слагаемые.

Подсказка 4

Их разность меньше 1, а сумма равна 24. Осталось ли ль сделать соответствующие выводы)

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

Обозначим

--1---- ---1--- ----1----- A = √1+ √2 +√3-+ √4 + ⋅⋅⋅+ √623+ √624

Возьмём число

B = √--1√--+ √-1-√-+ ⋅⋅⋅+ √---1-√--- 2+ 3 4+ 5 624+ 625

Число слагаемых одинаково, каждое слагаемое в $A$ больше соответствующего слагаемого в $B,$ поэтому $A > B.$ Избавимся от иррациональности в знаменателях:

A= √2-− √1-+√4 − √3+ ⋅⋅⋅+ √624− √623

B =√3-− √2-+ √5− √4+ ⋅⋅⋅+ √625− √624

Очевидно, $√ --- √- A+ B = 625 − 1 =24.$ Оценим $A − B.$

( ) ( A− B =√--1-√-− √--1-√-− √--1√-- − ⋅⋅⋅− √---1-√---− 1+ 2 2+ 3 3 + 4 622+ 623

− √---1-√---)− √---1-√---< √--1√--< 1 623+ 624 624+ 625 1+ 2

Подставим $B = 24 − A :$

A− 24+ A< 1,

отсюда $A < 12,5.$ Но $A > B,$ значит, $A >12.$ Следовательно, целая часть числа $A$ равна 12.

Ответ: 12

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

Задача 20#74652

Найдите все натуральные числа $a,$ для которых число

a+1 +√a5-+2a2+-1 -----a2+-1------

также является натуральным.

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

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

Подсказка 1

Мы хотим сделать так, чтобы числитель делился на знаменатель. Попробуем сделать замену а+1=b, так же заменим и корень. Что получится?

Подсказка 3

Может ли -а-1 быть сравнимо с нулем по модулю a^2+1?

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

Обозначим $a+ 1= b,√a5-+2a2+-1= c$ . В числителе записано

c2-− b2 c+ b= c− b

На $a2+ 1$ должно делиться

c2− b2 = a5+ 2a2+ 1− (a +1)2 = a5+a2− 2a≡a2+1 −a − 1

При $a> 1$ модуль остатка меньше $2 a +1,$ поэтому остаток не может делиться на $2 a + 1$ ни при каком $a> 1.$ Уравнению удовлетворяет единственное значение $a= 1.$

Ответ: 1

Предыдущий раздел

Следующий раздел