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

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

Тема ПитерГор (Санкт-Петербургская олимпиада)

Теория чисел на Питергоре

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

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

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

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

Подтемы раздела питергор (санкт-петербургская олимпиада)

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

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

Задача 1#82679

Дано 101-значное число $a$ и произвольное натуральное число $b$ . Докажите, что найдется такое не более чем 102-значное число натуральное число $c$ , что любое число вида $caaa...ab$ - составное.

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

Из признака делимости на $10101+1$ (необходимо рассмотреть знакочередующуюся сумму блоков по 101 цифре с конца) следует, что числа в которых количество $a$ в записи отличается на четное число имеют одинаковые остатки при делении на $101 10 +1$
Заметим, что $101 10 +1 ≡11 0$ , а еще по лемме об уточнении показателя $101 10 +1$ не делится на $2 11$ , поэтому у $101 10 + 1$ есть простой делитель $p$ отличный от 11
Достаточно сделать так, чтобы $cb$ и $cab$ делились на 11 и на $p$ соответственно. Такое $c$ существует и не превосходит $101 11× p≤ 10 + 1$ по китайской теореме об остатках.

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

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

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

Задача 2#70485

Найдите все пары ненулевых (не обязательно положительных) рациональных чисел $x,y,$ обладающие следующим свойством: любое положительное рациональное число можно представить в виде ${rx}∕{ry}$ с положительным рациональным $r.$

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

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

Подсказка 1

Давайте для начала причешем задачу. Если r - рациональное и положительное, то x,y - просто целые, так как можно построить явную биекцию между решениями при просто рациональных x,y и целых. Также, можно заметить, что если мы уберем целую часть числа r , то отношение из условия останется таким же, а значит, можно сказать, что 0 < r < 1 . А тогда можно сказать, что {(1 - r)x} = {-rx}, аналогично с y. Значит, можно считать, что y - натуральное, а х - целое. Значит, у нас, существенно, два случая - когда наша дробь - положительное число, и когда отрицательное. Попробуйте теперь найти такую дробь, которая не может быть представлена в таком виде как мы описали, и с теми условиями, которые мы доказали.

Подсказка 2

Сейчас будет приведено совсем не строгое, но тем не менее, наталкивающее на мысли, объяснение, почему нужно брать конкретную дробь, при разборе случая , когда дробь - положительное число. Давайте распишем {rx} как rx - [rx], {ry} как ry - [ry]. Тогда, для некоторого n/k = {rx}/{ry}, выполнено, что n*{ry} = k*{rx}. Значит, nry - n*[ry] = krx + k*[rx]. Что мы из этого можем получить? Если мы хотим прийти к противоречию, то можно попытаться взять какие - то k и n, такие, чтобы что-то в этом равенстве стало плохо. Сейчас целое число слева равно целому справа, а что можно подставить, чтобы слева, после преобразований, стало нецелое, а справа целое?

Подсказка 3

Возьмем n = x + 1, k = y. Тогда, во первых, сократятся rxy и rxy слева и справа, а в итого, останется уравнение {ry} = x * [ry] - y * [rx]. А значит, слева будет что - то между 0 и 1, а справа что-то целое. Пришли к противоречию. То есть, случай, когда дробь больше нуля разобран. Осталось подумать над случаем, когда наша дробь отрицательна. Можно попытаться найти контрпример, однако сразу непонятно как его строить, рассуждения из прошлого пункта непримиримы. Тогда скажем, что наша дробь равна некоторому a/b, где а - отрицательное и попытаемся доказать, что для любых а и b такое r найдется. И кажется, что в такой непонятной конструкции, как дробная часть, могут спасти только оценки значений. Попробуйте их применить(само собой, после избавления от знаменателей).

Подсказка 4

После избавления от знаменателей, у нас получается выражение brx - b*[rx] = ary - a[ry]. А значит, r - одно из решений уравнения r(bx - ay) = n, для некоторого целого n. При этом, мы можем сказать, что (без ограничения общности) х < 0, а значит, по нашим рассуждениям из первой подсказки, {rx} = 1 - {r|x|}. Подставьте это значение в наше уравнение и попробуйте подумать над максимальным и минимальным значением нецелое части.

Подсказка 5

Получим, что b = a{ry} + b{r|x|}. При r бесконечно близком к нулю, получается, что правая часть будет стремиться к нулю, что меньше b. При r бесконечно близким к 1, но меньшим ее, правая часть будет стремиться к a+b, что больше b. Значит, найдется промежуточное значение, при котором в нашем выражении будет достигаться равенство. А значит, для любой пары а и b из второго случая, мы привели пример. Значит, только для xy<0 выполнено требуемое.

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

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

Так как в качестве $r$ можно взять любое положительное рациональное число, можно считать, что числа $x$ и $y$ целые. В этом случае замена числа $r$ на его дробную часть не изменит отношения ${rx} {ry},$ значит, можно дополнительно считать, что $0< r< 1.$ Наконец, замена r на $1− r$ соответствует смене знаков чисел $x$ и $y,$ поскольку

{(1 − r)x} {−rx} {(1-− r)y}-= {−ry}.

Таким образом, достаточно рассмотреть лишь случай, когда $y$ — натуральное число.
Пусть $x$ также является натуральным числом. Покажем, что уравнение

{rx}-= x+1- {ry} y

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

y⋅rx− y⋅[rx]= x⋅ry− x ⋅[ry]+ {ry},

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

{ry} =x ⋅[ry]− y⋅[rx].

Но это уравнение не может иметь решений, поскольку левая часть положительна и меньше $1,$ а правая часть целая. Следовательно, если числа $x$ и $y$ одного знака, то требуемое $r$ не найдётся.
Пусть $x$ является отрицательным целым числом. Достаточно показать, что уравнение

{rx} a {ry} = b (∗)

для любых натуральных чисел $a$ и $b$ имеет вещественное решение $r.$ Тогда

b⋅rx− b⋅[rx]=a ⋅ry− a⋅[ry]

и, значит, $r$ является решением линейного уравнения

(bx− ay)r= n

для некоторого целого $n$ и, в частности, должно быть рациональным числом. Домножив уравнение $(∗)$ на знаменатели и воспользовавшись тем, что ${rx} =1 − {r|x|},$ получим уравнение

b= a{ry} +b{r|x|}.

При $r= 0$ правая часть равна нулю и поэтому меньше левой. А при $r,$ близких к $1,$ обе дробные части также будут близки к $1,$ поэтому правая часть будет близка к $a+ b$ и, в частности, будет больше левой. Следовательно, при некотором промежуточном $r$ правая часть будет равна левой. Поэтому если числа $x$ и $y$ разных знаков, то требуемое $r$ обязательно найдётся.

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

Разобьем плоскость на единичные квадраты линиями целочисленной решетки. Проведем прямую $l$ через начало координат $O$ и точку $(x,y).$ Поскольку $x,y ∈ Q.$ она имеет рациональный угловой коэффициент и проходит через какой-то узел решетки. Точка вида $(rx,ry)$ — это любая рациональная точка этой прямой. Проведем прямую через такую точку и левый нижний угол той клетки, в которую попала эта точка. Угловой коэффициент этой прямой равен как раз ${rx}∕{ry}.$

$PIC$

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

Предположим, что $x$ и $y$ одного знака. Тогда полученные отрезки имеют положительный угловой коэффициент. Один из них выходит из левого нижнего узла квадрата. Ясно, что из этого узла можно провести луч с положительным рациональным коэффициентом $λ,$ который пересечет верхнюю или нижнюю сторону квадрата, не встретив по дороге точек ни одного из наших отрезков. Это число $λ$ нельзя представить в нужном виде.

Пусть, наоборот, числа $x$ и $y$ разного знака. Тогда наши отрезки имеют отрицательный угловой коэффициент. Один из них выходит из левого верхнего узла квадрата. Несложно понять, что один из этих отрезков соединяет точку на левой стороне квадрата с точкой на его нижней стороне. На рациональных точках этого отрезка реализуются все возможные положительные рациональные угловые коэффициенты!

Ответ:

подходят все пары, в которых $xy <0$

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

Задача 3#70483

Будем говорить, что набор чисел $a ,...,a 1 m$ сильнее набора чисел $b,...,b , 1 n$ если среди всех неравенств вида $a > b i j$ количество верных неравенств не менее чем в $2$ раза превосходит количество неверных. Докажите, что не существует трех наборов $A,B,C,$ таких, что $A$ сильнее $B,$ $B$ сильнее $C,$ $C$ сильнее $A.$

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

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

Подсказка 1

Нам дали факт о том, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных» и просят доказать, что какой-то факт не выполнен, скорее всего мы получим противоречие с тем, что какая-то величина будет одновременно больше и меньше какого-то числа или мы сможем показать, что она не меньше и не больше некоторой числа, а значит равна ему и такой случай уже намного проще разобрать.

Подсказка 2

Давайте теперь зафиксируем произвольную тройку (A_i, B_j, C_t) и распишем для неё условие, что A сильнее B, B сильнее C, C сильнее A. А сколько вообще может быть верных неравенств при таком условии? Может попробовать оценить сверху и снизу количество верных неравенств?

Подсказка 3

Действительно, количество верных неравенств не больше чем 2, мы показали это для произвольной тройки, а сколько всего троек? Теперь попробуем понять, как ограничить эту величину снизу. Мы не пользовались тем, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных». Как раз «не менее» намекает нам о том, что мы сможем оценить снизу.

Подсказка 4

Можно посмотреть на наборы A, B и поотвечать на вопросы. А сколько можно записать неравенств вида a_i > b_j? А сколько из них должны быть верными? А мы пользовались какими-либо особенностями множеств A и B или это можно сказать для любой пары множеств?

Подсказка 5

Ура, мы получили, что количество верных неравенств не меньше чего-то, но и не больше, а значит в точности равно этому числу. Это уже хорошее условие, но на самом деле мы знаем больше! Что должно выполняться, чтобы это равенство достигалось?

Подсказка 6

Верно, количество верных неравенств должно быть ровно в 2 раза больше количества неверных! Так как мы доказываем, что такого не бывает, то в какой-то из пар наборов количество верных больше, чем в 2 раза неверных, а для числа с каким свойством неравенство было бы выполнено для всех остальных чисел?

Подсказка 7

Верно, для наибольшего из всех чисел или для наименьшего, здесь мы пользовались принципом крайнего, который часто может встречаться в задачках, где что-то сравнивается. Вернёмся к условию, что A сильнее B, B сильнее C, C сильнее A, оно ведь тоже участвовало в оценке, тогда что должно быть верно, чтобы она достигалась? Как нам объединить это с прошлым фактом?

Подсказка 8

Давайте рассмотрим тройку с минимальный (для максимального тоже верно) числом из всех наборов, тогда одно из неравенств очевидно выполнено, а другое - нет. Что можно сказать про оставшееся, а сколько таких неравенств, где в тройке участвует минимальное (максимальное) число? А сколько должно должно быть верных неравенств в паре наборов?

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

Предположим противное. Пусть наборы

A = (a1,...,al),B = (b1,...,bm ),C =(c1,...,cn)

таковы, что $A$ сильнее $B,B$ сильнее $C,C$ сильнее $A.$ Можно считать, что число $a1$ наибольшее среди всех чисел этих трёх наборов. Для каждой тройки индексов $i,j,k(1 ≤i≤ l,1≤ m,1≤ k≤ n)$ посчитаем, сколько верных увтерждений имеется среди неравенств $a > b,b >c ,c >a , i j j k k i$ просуммируем эти числа по всем $i,j,k$ и обозначим полученную сумму через $S.$ Тогда

S ≤ 2lmn, (∗)

поскольку всего имеется $lmn$ троек и в каждой тройке не больше двух верных неравенств. Далее заметим, что каждое неравенство $ai > bj$ присутствует в $n$ таких тройках, поэтому в сумме $S$ оно учтено $n$ раз. По предположению среди неравенств $ai > bj$ не меньше $2lm 3$ верных, поэтому вклад всех неравенств вида $ai >bj$ в сумму $S$ не меньше чем $2lmn. 3$ Аналогично вклад всех неравенств вида $b > c j k$ в сумму $S$ и вклад всех неравенств вида $c > a k i$ в сумму $S$ также не меньше чем $2lmn. 3$ Следовательно, суммарное количество верных неравенств не меньше чем $3⋅ 2lmn ≥S. 3$

Сопоставляя это с неравенством $(∗),$ заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности $2 3mn$ верных неравенств вида $bj > ck,$ а в каждой тройке $ai > bj,bj >ck,ck >ai$ ровно два верных неравенства.

Рассмотрим теперь тройку чисел $a1,bj,ck.$ Среди неравенств $a1 >bj,bj > ck,ck >a1$ должно быть ровно два верных. Поскольку $a1$ — наибольшее число неравенство $ck > a1$ неверно, т.е. выолняется неравенство $bj > ck.$ Значит, все неравенства вида $bj > ck$ верные и всего их $mn$ штук. Но это противоречит тому, что их $2 3mn.$ Стало быть, наше предположение неверно.

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

Задача 4#71958

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

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

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

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

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

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

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

Задача 5#71954

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

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

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

Очевидно, $p =2$ не подходит, поэтому $p$ нечётно. Поскольку сумма всех чисел равна $p⋅ p+1, 2$ она делится на $p.$ Значит, либо количество блоков делится на $p,$ либо сумма чисел в каждом блоке делится на $p.$ Первый случай невозможен, поскольку тогда блоков ровно $p$ и они все состоят из одиночных чисел, а значит, во всех блоках разные суммы. Следовательно, сумма чисел в каждом блоке делится на $p.$ Рассмотрим первый блок, пусть последнее число в нём равно $k <p,$ тогда сумма чисел в этом блоке равна $k(k+1)- 2$ и она делится на $p.$ Это возможно, только если $k+ 1= p.$ Тогда второй блок состоит лишь из числа $p$ и должно выполняться равенство $(p−1)p- 2 =p,$ поэтому $p =3.$ Это возможно: $1+2 =3.$

Ответ:

$p =3$

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

Задача 6#69819

В ряд выписано $2021$ простое натуральное число. Каждое, кроме крайних, отличается от одного из своих соседей на $12,$ а от другого — на $6.$ Докажите, что среди этих чисел есть равные.

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

Подсказка 1

Если мы хотим сказать, что все числа различные, то такая последовательность достаточно быстро, линейно растет. И при этом, почти все идут подряд, если смотреть на целую часть при делении на 6. То есть, число может «прыгать» через 1(после того как нацело поделили всю нашу последовательность на 6), но не больше чем на 1. Вот так «на пальцах», не строго, мы поняли, что было бы очень удачно, если бы мы смогли найти два каких-то соседних числа, которые отличаются на хотя бы 18. А это можно сделать, если мы(допустим) сможем разделить нашу последовательность на что-то большее ,чем некоторое число , и на что-то меньшее , чем некоторое число. И наименьшее и наибольшее из соответствующих групп отличались хотя бы на 18. То есть, иными словами, мы хотим сказать, что какие - то два подряд идущих числа, отличающиеся на 6, не могут быть в последовательности. Попробуйте придумать, как к такой конструкции прийти.

Подсказка 2

Одна из таких конструкций - остатки. По китайской теореме об остатках найдется такое k, что p + 6k делится на 5,а p + 6(k+1) на 7, при этом p - наименьшее простое число, большее 7(чтобы существовало число перед ним, которое входит в последовательность), входящее в последовательность. При этом 0 < k <= 5*7(по КТО найдется такое k). Теперь подумайте, откуда здесь возникает противоречие.

Подсказка 3

А возникает оно из - за того, что оба этих числа не простые, при этом они идут через одно. То есть, как раз мы получили конструкцию, в которой все разделилось на две кучи, в одной из которых числа которые хотя бы p+6(k+2), а в другой p+6(k-1). То есть разность хотя бы 18. Что теперь это значит? Какие теперь числа точно не могут быть в последовательности? А сколько теперь может быть чисел максимум в последовательности?

Подсказка 4

Верно, числа больше или равные p + 6(k+2), поскольку множество «меньших» непустое. Значит, чисел в наборе останется не больше чем 36(самое p и всевозможные 0 < k <= 5*7) и 2,3,5,7 - то есть не более 40 чисел. Но у нас 2021 число. Противоречие.

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

Способ 1

Предположим, что все числа в ряду различны. Выберем в нашем ряду число $p,$ у которого с каждой стороны не меньше пяти соседей, причём среди них нет числа $5.$ Такое $p$ найдётся, так как число $2021$ достаточно большое, а число $5$ в нашем ряду встречается не более одного раза. Если $p≡ ±1 (mod 5),$ рассмотрим соседа числа $p,$ отличающегося от него на $6.$ А если $p≡ ±2 (mod 5),$ рассмотрим его соседа, отличающегося на $12.$ Не умаляя общности, будем считать, что этот сосед находится справа от $p.$ На приведённой ниже схеме выберем среди первых четырёх чисел то, которое равно остатку числа $p$ при делении на $5.$ Число над стрелкой показывает, на сколько должен отличаться его правый сосед, а число после стрелки — какой остаток при делении на $5$ этот сосед будет иметь. Все числа над стрелками однозначно определяются условиями, что разности $± 6$ и $±12$ чередуются и в ряду нет остатка $0 :$

+6 +12 − 6 −12 +6 +12 −6 1−−→ 2 −−−→ 4−−→ 3 −−−→ 1−−→ 2 −−−→ 4−−→ 3

Осталось заметить, что, с какого бы из первых четырёх чисел мы ни начали, через четыре шага мы придём к этому же числу(так как по одному разу прибавим $6$ и $12$ и по одному разу вычтем). Следовательно, в нашем ряду обязательно найдутся два одинаковых числа.

Способ 2

Пусть $p$ — наименьшее простое число в этом ряду большее $7.$ По китайской теореме об остатках существует такое число $k$ ( $0< k≤ 35$ ), что

p+ 6k≡ 0 (mod 5)

p+ 6(k+ 1)≡ 0 (mod 7).

Тогда числа $p+ 6k$ и $p+ 6(k+ 1)$ не простые, поэтому в нашем ряду они не встречаются. Но тогда в нашем ряду не может быть и чисел, больших $p+ 6(k+1),$ так как иначе нашлось бы два соседних числа, одно из которых не превосходит $p+ 6(k− 1),$ а второе не меньше числа $p+ 6(k +2),$ что невозможно. Следовательно, в ряду может встретиться не более $40$ различных простых чисел: $2,3,5,7$ и $p,p+ 6,...,p+ 6⋅35.$ Но в ряду $2021$ число, значит, среди чисел есть равные.

Способ 3

Пусть $p$ — наименьшее просто число в этом ряду. Тогда все числа в ряду не превосходят $p +18⋅1010,$ так как если идти по ряду от $p$ до какого-то числа, то за каждые два шага число будет увеличиваться не более чем на $18.$ Докажем, что среди чисел

p,p+6,p+ 12,...,p+ 18⋅1010(∗)

количество простых меньше $2021.$ Из этого будет следовать, что в ряду обязательно найдутся равные числа. Пусть $dn$ — количество чисел в этом ряду, кратных $n.$ Подсчитаем количество чисел в ряду (*), кратных $5,7$ и $11.$ По формуле включений-исключений это количество равно

N =d5+ d7+ d11− d35 − d55− d77+ d385.

Если $(6,n)= 1,$ то на $n$ делится каждое $n$ -ое число в ряду (*) и $[3031] dn = n$ или $[3031] dn = n + 1.$ Следовательно,

[ ] [ ] [ ] [ ] [ ] [ ] [ ] N ≥ 3031- + 3031 + 3031-− 3031- − 1− 3031 − 1 − 3031 − 1+ 3031-= 606+433+ 275 − 87− 56− 40+ 7= 1129. 5 7 11 35 55 77 385

Итого, в ряду (*) не менее $1129$ чисел, кратных $5,7$ и $11.$ Из этих $1129$ чисел не более трёх являются простыми — это сами числа $5,7$ и $11,$ если они там есть. Поэтому в ряду (*) не более $3031− 1129+ 3= 1905$ простых.

Курсы

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

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

Задача 7#71933

Последовательность $(a ) n$ задана условиями

a1 = 1, a2 = 2 и an+2 = an(an+1 +1) при n ≥1.

Докажите, что $aa n$ делится на $(an)n$ при $n ≥100.$

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

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

Пусть простое число $p$ входит в $a n$ в $k$ -й степени. Докажем, что $a an$ делится на $pkn.$ Тогда утверждение задачи будет выполнено.

Пусть $ai$ — первое число в нашей последовательности, кратное $p.$ Если $p⁄= 2,$ то $i> 2$ и $ai = ai−2(ai−1+ 1).$ Следовательно,

ai−1 ≡ −1 (modp)

Заметим, что для $p= 2$ будет $i= 2,$ и выведенное сравнение тоже выполнено.

Итак, $ai−1 ≡ −1,ai ≡ 0,$ а тогда дальше в последовательности чередуются остатки $− 1$ и $0$ от деления на $p:$

a = a (a + 1)≡ −1 ⋅(0+ 1)=− 1 (modp) i+1 i−1 i ai+2 = ai(ai+1+ 1)≡ 0⋅(−1+ 1)=0 (modp) и т.д.

Более того, как видно из последнего вычисления, степени числа $p,$ на которые делятся члены последователыности, растут: если $ai$ делилось на $p,$ то $ai+2$ делится на $2 p$ и т. д. Отсюда следует, что если $an$ делится на $k p,$ то $an+2t$ делится на $k+t p .$ Кроме того, учтем, что числа $an$ и $n$ одинаковой четности, поскольку $a1 =1,$ $a2 = 2$ и остатки по модулю $2$ чередуются. Следовательно, $aan$ делится на $k+(a −n)∕2 p n .$ Остается заметить, что $n an > 2$ при $n≥ 5$ (это значит, что $an$ существенно крупнее $n$ ) и $k an ≥2 ,$ так как делится на $k p$ (это значит, что $an$ существенно крупнее $k$ ), поэтому $an− n >2kn$ , откуда следует требуемое.

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

Задача 8#71931

Сумму

2 2 ⋅5 2 ⋅5 ⋅...⋅2015 3⋅6 +3-⋅6-⋅9 +...+3-⋅6-⋅...⋅2019

записали в виде десятичной дроби. Найдите первую цифру после запятой.

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

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

Для начала упростим данную сумму. Каждое слагаемое запишем в виде разности

2⋅5⋅...⋅(3k− 1) 3⋅6⋅9⋅...⋅(3k+-3) =

= 2⋅5⋅...⋅(3k−-1)⋅(3k+-3)− 2⋅5⋅...⋅(3k−-1)⋅(3k+-2)= 3⋅6⋅9⋅...⋅(3k +3) 3⋅6⋅9⋅...⋅(3k+3)

= 2⋅5⋅...⋅(3k-− 1)− 2⋅5⋅...⋅(3k− 1)⋅(3k-+2) 3⋅6⋅9⋅...⋅3k 3⋅6⋅9⋅...⋅(3k+ 3)

Тогда вся сумма телескопически сократится до разности крайних слагаемых

2 2⋅5⋅...⋅2018 3 − 3⋅6⋅...⋅2019

Решение 1.

Оценим вычитаемое. Заведем переменные

A = 1⋅3⋅6⋅...⋅2016, B = 1⋅4⋅7⋅...⋅2017 21⋅⋅54⋅⋅87⋅⋅......⋅⋅22001178 23⋅5⋅6⋅⋅89⋅⋅.....⋅.2⋅2001189 C = 3-⋅6-⋅9-⋅...⋅2019, D = 4⋅7⋅10⋅...⋅2020 4⋅7⋅10-⋅...⋅2020- E = 5⋅8⋅11 ⋅...⋅2022

Мы хотим оценить величину числа $C.$

Поскольку $a−1 -a- a <a+1$ при натуральных $a,$ выполняются неравенства $A < B < C <D < E,$ откуда

ABC <C3 < CDE

Подставив в эти неравенства формулы для наших чисел и сократив дроби, получим

-1-- 3 -2-- 2019 <C < 2022

Тогда

1 ∘--1- ∘--2- 1 15-< 3 2019-<C < 3 2022-< 6

и значит,

1 < 2− 2⋅5⋅...⋅2018-< 3 2 3 3⋅6⋅...⋅2019 5

Таким образом, первая цифра после запятой исходного числа равна $5.$

Решение 2.

Оценим с двух сторон выражение

( )( ) ( ) C = 2⋅5⋅8⋅...⋅2018-= 1− 1 1 − 1 ... 1− --1- (∗) 3⋅6⋅9⋅...⋅2019 3 6 2019

Для этого заметим, что

k − 1 1 ( 1 )3 1 k --k- =1 −k < 1− 3k < 1− k+-1 = k-+1 (∗∗)

Действительно,

( ) 1− -1 3 =1− 1 + 1--−--1- 3k k 3k2 27k3

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

-12-− -13-= 9k-− 13-<--1---= 1 −--1- 3k 27k 27k k(k+ 1) k k +1

последнее сразу видно после умножения на $27k3$ и раскрытия скобок.

Неравенства $(∗∗)$ позволяют оценить произведение $(∗)$ сверху и снизу. Действительно,

(( 1 )( 1) ( 1) ( -1-))3 1 2 3 673 -1- 1 −3 1− 6 1− 9 ... 1− 2019 < 2 ⋅3 ⋅4 ⋅...⋅674 = 674

поэтому

C <-3√1--< √31--= 1< 1 674 512 8 6

Аналогично

(( 1) ( 1)( -1) ( -1--))3 1 2 3 672- 1-- 1− 6 1− 9 1 −12 ... 1− 2019 > 2 ⋅3 ⋅4 ⋅...⋅673 = 673

Поэтому

C > 2 ⋅3√1-> 2 ⋅3√1--= 2 ⋅ 1=-2 >-1 3 673 3 729 3 9 27 15

Итак, $1-<C < 1 15 6$ и, значит, $1= 2− 1< 2 − C < 2− 1-= 3. 2 3 6 3 3 15 5$

Ответ:

первая цифра после запятой равна $5$

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

Задача 9#71908

На доске написано $100$ различных натуральных чисел. К каждому из этих чисел прибавили НОД всех остальных. Могло ли среди $100$ чисел, полученных в результате этих действий, оказаться три одинаковых?

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

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

Предположим, что числа $a< b<c,$ написанные изначально на доске, превратились в три одинаковых числа. Заметим, что НОД, прибавленный к числу $a$ , является делителем чисел $b$ и $c,$ а значит, и их разности $c− b.$ Следовательно, он не превосходит $c− b,$ а значит, заведомо меньше разности $c− a.$ После прибавления этого НОДа к $a$ получилось число, меньшее $c,$ и оно не могло совпасть с числом, полученным из $c.$

Ответ: нет

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

Задача 10#81384

Имеется натуральное $1001$ -значное число $A.$ $1001$ -значное число $Z$ — то же число $A,$ записанное от конца к началу (например, для четырёхзначных чисел это могли быть $7432$ и $2347$ ). Известно, что $A> Z.$ При каком $A$ частное $A∕Z$ будет наименьшим (но строго больше $1$ )?

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

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

Первое решение. Пусть $A = a--a---...a. 1000 999 0$ Поскольку $A >Z,$ среди цифр $a,a ,...,a 0 1 499$ есть хотя бы одна недевятка. Значит, $Z ≤ Z0 = 99◟. ◝4.◜99.9◞89◟95..◝◜0.19◞.$ Покажем, что $501 499 A − Z ≥10 − 10 .$ Отсюда будет следовать, что

A 10501− 10499 Z-− 1≥ ----Z0----

Эта оценка достигается при $Z =Z0,$ что и даёт ответ. Имеем

( 1000 ) ( 999 ) ( 501 499) A− Z =(a1000− a0) 10 − 1 + (a999− a1) 10 − 10 + ⋅⋅⋅+ (a501− a499)10 − 10 = =φ499Δ499+ φ498Δ498+ ⋅⋅⋅+ φ0Δ0

где $φi =a501+i− a499−i$ и $Δi = 10501+i− 10499−i$ при $i= 0,1,...,499.$ Заметим, что $Δi+1 > 10Δi.$ Пусть $j−$ наибольший индекс, при котором $φj ⁄= 0.$ Тогда

|φjΔj + φj−1Δj−1+ ⋅⋅⋅+ φ0Δ0|≥|φjΔj|− |φj−1Δj−1|− ⋅⋅⋅− |φ0Δ0|≥ ≥Δ (1− 9-− -9-− ⋅⋅⋅− -9) = Δj-≥ Δ j 10 100 10j 10j 0

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

Второе решение. Ясно, что можно минимизировать (положительное) число $A- A−Z- Z − 1= Z .$ Пронумеруем цифры в $A$ слева направо $a1,a2,...,a1001.$ Пусть $k$ — наименьший номер, для которого $ak ⁄= a1002−k$ (тогда $k≤ 500$ и $ak >a1002−k,$ ибо $A > Z$ ).

Рассмотрим произвольный оптимальный пример. Заменим первые и последние $k− 1$ цифр на девятки. $A− Z$ не изменится, $Z$ не уменьшится, то есть наша дробь не увеличится. По этой же причине $a501$ можно заменить на $9.$ Заменим $ak$ на $9,$ а $a1002−k$ на $8.$ При этом $A− Z$ не увеличится, а $Z$ не уменьшится. Заменим все цифры $ak+1,...,a500$ на нули, а $a502,...,a1001−k$ на девятки. Тогда $A − Z$ не увеличится, а $Z$ если и уменьшится, то на меньшую величину (это произойдёт только тогда, когда вторая половина и так была девятками!). Поскольку в оптимальном примере $A− Z <Z$ (в первом просто меньше цифр), то, ясно, $A−ZZ-$ не возрастёт. Итак, можно считать, что $A$ имеет вид

9◟9.◝.◜.9 ◞0◟0.◝.◜.0◞999◟ ◝..◜.9◞89◟9..◝◜.9◞ k 500−k 500−k k−1

В этом случае

A − Z = 10501+10500 − 10k− 10k−1

Это выражение достигает минимума при $k= 500,$ и при этом же $k$ достигается максимум значения рассматриваемых $Z.$ Значит, это и есть ответ.

Ответ:

При $A,$ запись которого (слева направо) такая: $501$ девятка, восьмёрка, $499$ девяток

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

Задача 11#80968

Даны два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $bk− a2$ и $k 2 a − b$ делится на $2018 2 .$

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

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

Будем решать обобщенную задачу. Дано натуральное число $n$ и два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $2k 2 b − a$ и $2k 2 a − b$ делится на $n 2 .$

Воспользуемся следующим известным утверждением: пусть число $c− 1$ дает остаток $k 2$ при делении на $k+1 2 ,$ где $k ≥2.$ Тогда $2 c − 1$ дает остаток $k+1 2$ при делении на $k+2 2 .$

Пусть $2 a − 1$ делится на $α 2$ и не делится на $α+1 2 ,$ а $2 b − 1$ делится на $β 2$ и не делится на $β+1 2 .$ Очевидно, что при этом $α,β ≥ 2.$ Тогда $2 a − 1$ дает остаток $α 2$ при делении на $α+1 2 ,$ а $2 b− 1$ дает остаток $β 2$ при делении на $β+1 2 .$ Пусть $α ≤β,$ положим для краткости $β−α 2 = m.$ По лемме число $2m 22 2 a − 1= (((a) )...)− 1$ даёт остаток $β 2$ при делении на $β+1 2 .$

Будем решать задачу индукцией по $n.$ Если $n≤ β+ 1,$ то нам подойдет $k= m,$ поскольку $2m a$ и $2 b$ дают равные остатки при делении на $2β.$ Сделаем переход от $n$ к $n+ 1.$ По индукционному предположению при некотором $k$ число $a2k− b2$ делится на $2n.$ Если оно делится и на $2n+1,$ то переход сделан. Иначе оно дает остаток $2n$ при делении на $2n+1.$ Пусть $r= 2n−β + 1.$ Тогда по лемме $b2(r−1)− 1$ дает остаток $2n$ при делении на $2n+1.$ Следовательно, $b2r− b2$ дает остаток $2n$ при делении на $2n+1.$ Воспользуемся формулой разности степеней:

a2kr− b2r = (a2k− b2)(a2k(r−1)+ a2k(r−2)b2+ ...+ b2(r−1))

Первая скобка дает остаток $2n$ при делении на $2n+1,$ вторая состоит из $r$ нечетных слагаемых и, значит, нечётна. Стало быть, разность $a2kr− b2r$ дает остаток $2n$ при делении на $2n+1.$ Но тогда $a2kr − b2 = (a2kr− b2r)− (b2r − b2)$ делится на $2n+1,$ поскольку выражения в скобках дают одинаковые остатки при делении на $2n+1.$

Интенсивы

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

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

Задача 12#71294

Натуральное число $n$ назовём почти квадратом, если $n$ можно представить в виде $n =ab,$ где $a$ и $b$ — натуральные числа, причем $a ≤b≤ 1,01a.$ Докажите, что для бесконечно многих натуральных $m$ среди чисел $m,m + 1,m + 2,...,m + 198$ нет почти квадратов.

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

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

Предположим противное. Разобьем натуральный ряд на отрезки по $199$ чисел. Тогда во всех отрезках, кроме, быть может, конечного количества $c,$ имеется почти квадрат. Отсюда следует, что среди чисел от $1$ до $2 n$ количество почти квадратов не меньше чем $n2- 199 − c,$ где $c$ — некоторая константа. С другой стороны, каждый такой почти квадрат имеет вид $ab,$ где $a≤n,$ $[ a-] b∈ a,a + 100 ,$ поэтому их количество не больше чем

n∑ ( ) 2 a100-+1 = n + n(n2+001)< n199 − c a=1

при достаточно большом $n.$ Противоречие.

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

Задача 13#80976

Саша перемножил все делители натурального числа $n.$ Федя увеличил каждый делитель на $1,$ а потом перемножил результаты. Федино произведение нацело делится на Сашино. Чему может быть равно $n?$

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

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

Пусть Сашино число имеет делители $1 =d < d < ...<< d = n. 0 1 k$ Заметим, что число $n +1$ взаимно просто со всеми этими делителями, поэтому число $(d0+ 1)(d2+1)...(dk−1+1)$ должно делиться на $d0⋅d1⋅...⋅dk.$ При этом $d1 ≤ d0+1,d2 ≤ d1+1$ и так далее $dk ≤ dk−1+ 1.$ Перемножив эти неравенства, получим, что делимое не превосходит своего делителя, а это возможно только в том случае, когда все неравенства обращаются в равенства. Но тогда $n = dk =dk−1+ 1,$ т. е. $n$ делится на $dk−1 = n− 1.$ Значит, либо $n= 2,$ либо числа $dk−1$ не существует и $n= 1.$

Ответ:

$n =1$ или $n= 2$

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

Задача 14#70499

В последовательности целых чисел $(a ) n$ сумма $a + a m n$ делится на $m +n$ при любых различных $m$ и $n.$ Докажите, что $a n$ кратно $n$ при любом $n.$

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

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

Распишем $a n$ в хорошем для нас виде

(a3n +an)+ (a5n+ an)− (a5n +a3n)= 2an.

Тогда видим, что каждая скобка в левой части делится на $2n,$ поэтому и правая часть делится, то есть $an$ кратно $n.$

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

Задача 15#70349

Натуральные числа $a$ и $b$ больше $1.$ Известно, что числа $a2+ b$ и $a +b2$ простые. Докажите, что числа $ab+ 1$ и $a+ b$ взаимно простые.

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

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

Пусть они не простые. Тогда $ab+ 1$ и $a+ b$ имеют общий простой делитель $p.$ Рассмотрим произведение чисел $a2+ b$ и $a+ b2$ и преобразуем

2 2 22 3 3 2 2 (a + b)(a+ b)= a b +ab+ a +b = ab(ab+ 1)+ (a+ b)(a − ab+ b).

Тогда произведение тоже делится на $p.$ Но поскольку $p ≤a+ b< min(a2+ b,b2+ a),$ число $p$ является собственным делителем какого-то из чисел $a2+b$ или $a+ b2,$ что противоречит их простоте.

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

Задача 16#71157

Дано бесконечное множество натуральных чисел $M.$ Известно, что для любых двух различных чисел $a,b ∈M$ в множестве $M$ также содержится хотя бы одно из чисел $b a − 2$ и $b a +2.$ Докажите, что в $M$ содержится хотя бы одно составное число.

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

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

Решение 1.
Предположим, что множество $M$ состоит только из простых чисел. Тогда все числа из множества $M$ нечётные(так как любое число вида $b 2 ± 2$ составное при $b≥ 3$ ). Возьмём в множестве $M$ два произвольных числа $a,b≥3.$ Если $a$ даёт остаток $1$ при делении на $3,$ то $b a$ также даёт остаток $1.$ Тогда $b a + 2$ делится на 3 и по нашему предположению $b a+ 2$ не может принадлежать множеству $M.$ Значит, в этом случае множеству $M$ принадлежит число $b a− 2.$ Аналогично если $a$ даёт остаток $2$ при делении на $3,$ то $b a$ также даёт остаток $b 2,a − 2$ составное и тогда в этом случае множество $M$ должно содержать число $b a+ 2.$
Если множество $M$ содержит хотя бы одно простое число $a,$ дающее остаток $1$ при делении на $3,$ то в множестве $M,$ как мы установили, содержится число вида $b a − 2,$ дающее остаток $2.$ Тогда число $b a (a − 2) +2$ тоже принадлежит $M.$ Заметим, что это число даёт при делении на $a$ тот же остаток, что и число $(− 2)a+ 2= −2a+ 2.$ Но это число делится на $a$ по малой теореме Ферма, значит, оно составное.
Аналогично, если простое число $a∈ M$ даёт остаток $2$ при делении на $3,$ то в множестве $M$ содержится число $(ab+2)a− 2,$ которое по тем же причинам делится на $a.$
Решение 2.
Предположим противное. Как и в первом решении установим, что если $a≡ ±1$ (mod $3$ ) принадлежит $M,$ то $ab∓ 2≡ ∓1 (mod 3)$ также принадлежит $M.$ В частности, в $M$ есть числа, сравнимые как с $1,$ так и с $− 1$ по модулю $3.$
Рассмотрим простые числа $q ≡ 1 (mod 3)$ и $r$ из $M.$ Тогда в $M$ содержится простое число

p =(qr− 2)r+ 2≡ (1− 2)r+2 =1 (mod q− 1).

Следовательно, $p− 1$ делится на $q − 1.$ Пусть $p− 1= k(q− 1).$ Тогда число

a =(qp− 2)p+ 2≡ (− 2)p+ 2= −2p+ 2= −2(2p−1− 1) (mod q)

делится на $q,$ поскольку по малой теореме Ферма $q−1 2 ≡ 1 (mod q)$ и, значит,

k 2p−1 = 2k(q− 1) = (2q−1) ≡ 1k =1 (mod q).

Таким образом, число $a$ принадлежит $M$ и является составным. Противоречие.

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

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

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

Задача 17#70862

Дано натуральное число $N.$ На доске написаны числа от $N3$ до $N3 +N.$ Среди них $a$ чисел покрасили в красный цвет, а какие-то $b$ из остальных — в синий. Оказалось, что сумма красных чисел делится на сумму синих. Докажите, что $a$ делится на $b.$

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

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

Если $b =1,$ то $a$ делится на $b.$ Поэтому можно считать, что $b≥ 2,$ тогда $a≤N − 1.$
Пусть сумма $a$ чисел равна $3 sa = aN + a1,$ а сумма $b$ чисел равна $3 3 sb =bN +b1 ≥ N .$ По условию $sa$ делится на $sb.$ Обозначим их отношение через $k.$ покажем, что $k≤ N.$ Действительно,

3 3 3 3 sa = aN +a1 ≤ (N − 1)N + a1 ≤(N − 1)(N + N)< (N + 1)N

(последний переход несложно проверить), и значит, $k= s∕s < (N + 1)N3 ∕N3 = N +1. a b$ Поскольку $s =ks , a b$ получим равенство $aN3 +a = k(bN3 + b), 1 1$ или, что то же самое,

3 (a− kb)N =kb1− a1.

Если $a$ не делится на $b$ , т.е. $a ⁄=kb,$ то $|(a − kb)N3 |≥N3,$ и значит, $|kb1− a1|≥ N3.$ Проверим, что на самом деле выполнено неравенство $kb1− a1 ≥ N3,$ т.е. что число $kb1 − a1$ не может быть слишком крупным отрицательным числом. Действительно, $0 ≤a1 ≤ aN$ и $0 ≤b1 < bN,$ и поэтому $kb1 − a1 ≥ −a1 ≥ −aN ≥ −N2.$ Тогда

3 2 3 N ≤ kb1 − a1 ≤ kb1 < kbN ≤ bN ≤ N .

Здесь как раз применяем, что $k ≤N.$ В итоге, противоречие.

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

Задача 18#70201

Назовём натуральное число почтенным, если сумма всех его делителей, включая $1,$ но не включая само число, на $1$ меньше этого числа. Найдите все почтенные числа, некоторая точная степень которых тоже почтенно.

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

Пусть $n$ — почтенное число. Тогда сумма $d +d + ...+ d 1 2 k$ его делителей, отличных от $n,$ равна $n− 1.$ У числа $nk$ заведомо есть делители

k−1 k−1 d1, d1n,..., d1n , d2, d2n,..., dk, dkn,..., dkn .

Все они различны и отличны от $nk,$ а их сумма равна

2 k−1 (1+ n+ n + ...+n )(d1+ d2+ ...+dk)=

= (1+n +n2 +...+ nk−1)(n− 1)= nk− 1.

Следовательно, у числа $nk$ нет делителей(так как оно тоже должно быть почтенным), отличных от вышеперечисленных. Это означает, что $n$ является степенью простого числа. В противном случае, если $n$ делится на $pt$ (и не делится на $pt+1$ ), то в приведённом выше списке делителей числа $nk$ отсутствует делитель $pt+1.$
Итак, пусть $n= pm.$ Тогда сумма отличных от $n$ делителей числа $n$ равна $1+p +p2+ ...+ pm −1,$ что по условию равно $pm − 1.$ Но

1+ p+ p2 +...+ pm−1 = pm-−1− 1, p− 1

что меньше $pm −1− 1$ при $p⁄= 2$ и равно $pm−1− 1$ при $p =2.$ Таким образом, числа $n =2m$ удовлетворяют условию задачи, а остальные числа не удовлетворяют условию.

Ответ:

все степени двойки, включая нулевую

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

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