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

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

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

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

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

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

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

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

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

Задача 1#82679

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

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

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

Из признака делимости на $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#89867

Несократимые дроби $a b$ и $c d$ записали в виде чисто периодических десятичных дробей. Оказалось, что любая конечная последовательность подряд стоящих цифр, встречающаяся в первой десятичной дроби после запятой, встречается и во второй (тоже подряд и тоже после запятой). Докажите, что $b= d.$

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

Давайте для удобства считать, что $0≤ a< b$ и $0 ≤c< d$ , иначе вычтем целую часть дробей, не изменив дробную часть, получив $a$ и $c$ в нужном диапазоне (условие на несократимость дробей останется). Скажем, что

a c b = 0,(T1) d = 0,(T2),

(1)

$m1$ — количество цифр в записи $T1$ , $m2$ – количество цифр в записи $T2$ ( $T1$ и $T2$ — периоды наших дробей).

Рассмотрим последовательно написанный $T1$ $m2$ раз (такая последовательность в первой дроби есть), по условию она же есть, и во второй, причём в ней $m1m2$ цифр, значит, во второй дроби эта последовательность является сдвигом $T2$ , записанным $m1$ раз. Тогда скажем, что во второй дроби построенная последовательность перед первым $T2$ имеет кусок $k1$ , оставшийся кусок из $T1$ назовём $k2$ , то есть $---- T1 = k1k2$ . Тогда эта же последовательность во второй дроби выглядит как $k1$ , $T2$ , написанный $m1− 1$ раз, и остаток $k$ , причём $--- T2 =kk1$ . Обозначим рассматриваемую последовательность за $T$ ( $--------- -------- k1k2...k1k2 =T = k1k...k1k$ ), тогда:

a =0,(k1k2)=0,(T) b

(2)

c --- d =0,(kk1)= 0,k(T)

(3)

Скажем, $m$ — количество цифр в $T$ , $n$ —- количество цифр в $k$ . Тогда верно следующее:

a⋅10m =T,(T ) b

(4)

c ⋅10n = k,(T) d

(5)

c --- d ⋅10n+m = kT,(T)

(6)

Вычитая (2) из (4) и (5) из (6) соответственно, получаем:

a ⋅(10m − 1)= T b

(7)

c⋅10n(10m − 1)= T +k(10m − 1) d

(8)

Подставим $T$ из (7) равенства в (8), получим:

c⋅10n(10m − 1)= a ⋅(10m− 1)+k(10m− 1) d b

c n a n d ⋅10 = b +k =⇒ bc⋅10 = ad+ bdk

. . ad..b и bc⋅10n..d

Вспомним, что пары чисел $(a,b)$ и $(c,d)$ взаимно просты. Значит, $d..b .$ и $b⋅10n ..d .$ .

Докажем, что $n 10$ и $d$ взаимно просты. Из (1):

c ⋅(10m2 − 1)=T2 =⇒ c⋅(10m2 − 1)= T2d =⇒ 10m2 − 1...d, d

ибо $c$ и $d$ взаимно просты.

Если НОД $(10n,d)...p$ — простое, то $10m2 − 1$ уж точно на $p$ не делится, но тогда и на $d$ делиться не может, противоречие, тогда рассматриваемый НОД равен 1, что эквивалентно искомой взаимной простоте, откуда следует, что $b⋅10n ...d ⇐ ⇒ b ...d$ . Тогда у нас $d...b$ и $b...d =⇒ b=d$ , что и требовалось.

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

Задача 3#89870

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

a-− k √ - a+1-− k a < {k 2} < a .

Применяя теорему Кронекера для

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

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

k< a{n√2}< k+ 1.

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

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

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

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

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

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

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

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

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

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

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.$ Стало быть, наше предположение неверно.

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

Задача 5#70485

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

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

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

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

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

$PIC$

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Так как в качестве $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$ обязательно найдётся.

Ответ:

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

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

Задача 6#69819

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

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

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

Способ 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#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$

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

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

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

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

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

Задача 10#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$ , откуда следует требуемое.

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

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

Ответ: нет

Интенсивы

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

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

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

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

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

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

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

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

Задача 16#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,$ что противоречит их простоте.

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

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

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

Задача 17#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$ удовлетворяют условию задачи, а остальные числа не удовлетворяют условию.

Ответ:

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

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

Задача 18#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.$ В итоге, противоречие.

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

Задача 19#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$ содержится простое число