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

ПитерГор - задачи по годам → .11 ПитерГор 2024

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

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

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

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

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

Разделы подтемы ПитерГор - задачи по годам

ПитерГор 2014 и ранее

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

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

Задача 1#82676Максимум баллов за задание: 7

Таблица $100×100$ заполнена числами как показано на рисунке:

Можно ли переставить некоторые числа так, чтобы в каждой клетке по прежнему стояло одно число, и чтобы во всех прямоугольниках из трех клеток сумма чисел не изменилась?

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

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

Подсказка 1

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

Подсказка 2

Диагональная в 3 цвета! Тогда в каждом прямоугольнике из 3х клеток будет каждый цвет. Тогда попробуем воздействовать на каждый цвет по отдельности так, чтобы сумма в таких прямоугольниках не изменилась.

Подсказка 3

Если в каких-то клетках прибавляем, в каких-то надо отнимать.

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

Рассмотрим раскраску таблицы в три цвета, как показано на рисунке:


1	2	3	…	1

2	3	1	…	2

3	1	2	…	3

$...$	$...$	$...$	$...$	$...$

1	2	3	…	1

Если в исходной таблице к числам цвета 2 прибавить единицу, а из чисел цвета 3 вычесть единицу, то мы получим такую перестановку, что набор чисел сохранится. А сумма в каждой тройке тоже.

Ответ: Можно

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

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

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

Задача 2#82677Максимум баллов за задание: 7

Дана последовательность $a n$ : 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, $...$
(одна единица, две двойки, три тройки, четыре четверки и т.д.) и еще одна последовательность $bn$ такая, что $abn =ban$ для всех натуральных $n$ .

Известно, что $bk = 1$ при некотором $k> 100$ . Докажите, что $bm =1$ при всех $m >k$ .

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

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

Подсказка 1

Для начала давайте поймем что-то про последовательность {a_i}. Как минимум поймем на каких местах у нас стоит число k. Это важно для нас, так как если мы хотим выбрать какое-то конкретное m(и посмотреть откуда же может быть получено противоречие), то нам надо понимать, как связан номер и значение a_m. Как зависит значение от m?

Подсказка 2

Для любых номеров m, которые располагаются между t(t + 1)/2 + 1 и (t + 1)(t + 2)/2, a_m = t + 1. Если от нас требуется доказать, что начиная с какого-то номера у нас b_i = 1, не будем мелочиться и докажем, начиная почти для всех(с какого-то маленького), по индукции. Но давайте, для начала, так сказать, для создания благоприятной обстановки, поймем, как все таки делать индукцию. Ведь переход от n к n + 1 здесь кажется странным. Однако переход от k(k + 1)/2 к (k + 1)(k + 2)/2 выглядит более разумно, ведь мы знаем все значения a_i, для i из этого отрезка.

Подсказка 3

Верно, переход такой нам легко дается, так как a_i из этого промежутка равно t + 1, а значит, это b_(t + 1), но для всех меньших мы доказали. Что осталось написать по этой задаче? Является ли это полным решением?

Подсказка 4

Не является, так как t + 1 не всегда входят в уже доказанный промежуток. Для t = 1, 2 - это неверно. Значит, надо в качестве базы использовать t >= 3. Но это подходит под условие нашей задачи, а значит, если у нас b_k = 1, то и все последующие будут равны 1.

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

Возьмём число $m : t(t+1)+ 1≤ m ≤ (t+1)(t+2) 2 2$ , заметим, что для любого такого $m$ $a = t+1 m$ , тогда $b = b = a t+1 am bm$ , тогда если $bm =1$ , то $abm =1$ , тогда $bt+1 =1$ , и наоборот.

Значит, $bt+1 = 1 ⇐⇒ bm = 1$ для $t(t+1) (t+1)(t+2) m ∈ [ 2 + 1; 2 ]$

Значит, и $bt+1 ⁄=1 ⇐⇒ bm ⁄= 1$

Если $b3 =1$ , то

2× 3 3× 4 ∀m ∈ [-2-+ 1;-2--]:bm = 1 т.е. b4 = b5 =b6 = 1

Докажем тогда по индукции, что $∀m > 3 bm = 1.$

База уже есть. Переход будем делать от $m ∈ [3;t(t+21)]$ к $m ∈[3;(t+1)2(t+2)].$

Заметим, что $t+ 1< t(t+21)$ при $t>3 ⇒ bt+1 = 1$ , но по предположению индукции $∀m ∈ [t(t+21)+ 1≤ m≤ (t+1)2(t+2)]:bm =1$ , значит,

∀m ≥3 :bm = 1, если b3 = 1

Аналогичными рассуждениями

∀m ≥3 :bm ⁄= 1, если b3 ⁄= 1

Итого т.к. $bk =1$ , $k> 100$ , то $b3 =1$ , а значит, $∀m > 3$ :

bm = 1⇒ ∀m > k bm =1

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

Задача 3#82678Максимум баллов за задание: 7

В неравнобедренном треугольнике $ABC$ проведена биссектриса $AK$ . Диаметр $XY$ его описанной окружности перпендикулярен прямой $AK$ (порядок точек на описанной окружности $B − X− A − Y − C$ ). Окружность, проходящая через точки $X$ и $Y$ , пересекает отрезки $BK$ и $CK$ в точках $T$ и $Z$ соответственно. Докажите, что если $KZ = KT$ , то $XT ⊥Y Z$ .

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

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

Подсказка 1

Если сделать аккуратный чертеж, то кажется, что продолжения ХТ, АК и YС пересекаются в одной точке на описанной окружности треугольника АВС.

Подсказка 2

Предыдущий факт сложно доказывать напрямую, стоит применить обратный ход.

Подсказка З

Обозначим пересечение луча АК с описанной окр-тью АВС за L. Пересечение LХ и LY с ВС обозначим Т₁ и Z₁. Хотим показать, что XТ₁Z₁Y является вписанным. Используя, что дуги ВL и LС равны (из-за биссектрисы), можно посчитать сумму противоположных углов данного четырехугольника. Следующий шаг — показать равенство Т₁К и КZ₁.

Подсказка 4

Чтобы показать равенство Т₁К и КZ₁:
1) Посмотрите чему равен ∠T₁LZ₁ и чем же тогда является Т₁Z₁ в описанной окружности △T₁LZ₁.
2) Подобие каких треугольников даёт вписанность XТ₁Z₁Y? Тогда через что пройдёт прямая LK в T₁LZ₁?

Подсказка 5

Осталось показать, что такой четырехугольник единственный. Пересечением чего является центр описанной окружности вписанного четырехугольника? Посмотрите, где лежит центр окружности описанной около XT₁Z₁Y.

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

Применим обратный ход. Обозначим пересечение луча $AK$ с $(ABC )$ за $L.$ Пересечение $LX$ и $LY$ с $BC$ обозначим $T 1$ и $Z. 1$ Теперь нам надо доказать, что $XY Z1T1$ вписанный и $KZ1 = KT1,$ так как получится, что точки $T$ и $Z$ из условия совпадают с ними.

$PIC$

∠XY L = ⌣-LYX-= ⌣-XY-B+-⌣-BY-L = ⌣-BT1X+-⌣-LT1C-=∠LT1C 2 2 2

Тогда получили, что $T1XY Z1$ вписанный, так как внутренний угол равен противоположному внешнему. Теперь обратим внимание на то, что треугольники $XYL$ и $T1Z1L$ подобные, а в прямоугольном треугольнике высота и медиана образуют равны углы со сторонами. Поэтому так как $LK$ высота в треугольнике $XY L,$ то $LK$ является медианой в треугольнике $LT1Z1.$ Значит, $K$ середина $T1Z1,$ откуда получаем то, что мы хотели в начале.

Заметим, что четырехугольник из условия единственный, ведь его центр лежит на серединном перпендикуляре к $XY$ и на перпендикуляре к $BC,$ восставленному в $K.$

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

Задача 4#82679Максимум баллов за задание: 7

Дано $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$ по китайской теореме об остатках.

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

Задача 5#82681Максимум баллов за задание: 7

На плоскости отмечено 100 точек общего положения (т.е. никакие три не лежат на одной прямой). Докажите, что можно выбрать три отмеченные точки $A$ , $B$ , $C$ так, чтобы для любой точки $D$ из оставшихся 97 отмеченных точек, прямые $AD$ и $CD$ не содержали бы точек, лежащих внутри треугольника $ABC$ .

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

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

Подсказка 1

Прямые, соединяющие точки A, B, CЮ делят плоскость на 7 частей, включая треугольник внутри. Рассмотрите эти части. Точки D из каких частей нам подходят?

Подсказка 2

Видно, что подходящие части тем больше, чем больше угол АВС. Воспользуемся принципом крайнего и возьмём такие 3 точки, чтобы АВС был максимальным. Проверим, подходит ли нам этот случай, пойдя от противного: пусть они не подходят. Тогда в каких частях может находиться точка D?

Подсказка 3

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

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

Применим принцип крайнего: выберем среди всех троек точек треугольник $ABC$ с самым большим углом $B.$

Предположим, что точки $A$ , $B$ , $C$ не подходят. Тогда существует точка $D$ в объединении частей плоскости, одна из которых заключена между прямыми $AC$ и $AB,$ а другая — между прямыми $CA$ и $CB.$

При этом $D$ не может лежать внутри треугольника $ABC$ , иначе $∠ADC >∠ABC$ .

$PIC$

Рассмотрим случай, когда $D$ лежит между лучами $AC$ и $AB$ (когда $D$ и $A$ лежат в разных полуплоскостях относительно $BC$ ). Тогда

∠ABD = ∠ABC +∠CBD > ∠ABC

получаем противоречие. То же работает для случая, когда $D$ лежит между лучами $AC$ и $BC$ .

$PIC$

Оставшиеся два случая (когда $D$ и $C$ лежат в разных полуплоскостях относительно $AB$ ) рассматриваются аналогично: в них

∠ABD = ∠CBA +∠ABD > ∠ABC

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

Задача 6#82682Максимум баллов за задание: 7

Дан многочлен $P(x)$ с целыми коэффициентами. Для некоторого натурального $n$ числа $P (0),P(1),...,P (2n+ 1)$ делятся на $22n$ . Докажите, что значения многочлена $P(x)$ во всех целых точках делятся на $2n 2$ .

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

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

Подсказка 1

Чтобы доказать, что у нас многочлен во всех точках кратен чему-то, бывает удобно представлять этот многочлен в виде, когда мы поделили его на какой-то другой с остатком, то есть представить P(x) = Q(x) * S(x) + R(x), и делили мы на многочлен на Q(x). Тогда если мы докажем, что во всех точках Q и R кратны чему-то, то докажем это и для P(x). Тогда, давайте сразу возьмём в качестве Q какой-то многочлен, который кратен 2^2^n. К примеру, x(x - 1)…(x - (2^n + 1)). Докажите, что такой многочлен действительно кратен 2^2^n, а после поймите какие условия тогда мы получаем на R(x).

Подсказка 2

Q(x) кратен, поскольку у нас произведениe k последовательных целых чисел кратно k!, и при этом у k! мы можем посчитать степень вхождения 2. В таком случае, на R(x) накладываются ровно такие же условия, как на P(x). А что значит, если многочлен, который принадлежит Z[x](поймите почему), и имеет степень меньшую, чем у Q, а также в хотя бы в deg(Q) подряд идущих целых точках кратен некоторому числу?

Подсказка 3

Это значит, что он кратен этому числу во всех целых точках, поскольку мы можем поделить на это целое число и индукцией показать, что если многочлен целочисленный в хотя бы t+1 подряд идущей целой точке, при том, что его степень не больше t, то он целочисленный во всех целых точках. Что тогда это нам даёт в рамках задачи?

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

Среди $2n +2$ подряд идущих целых чисел $x$ , $x − 1$ , …, $x− (2n +1)$ есть хотя бы $[(2n+ 2)∕2]$ кратных двум, хотя бы $[(2n+ 2)∕4]$ кратных $4$ , и т.д. Значит, суммарная степень вхождения $2$ в их произведение не меньше

∑ n k ∑ n−k n−1 n−2 n− 3 n [(2 +2)∕2 ]= 1+ [2 ]= (2 + 1)+2 + 2 +...+1= 2 k k

Поэтому все значения многочлена $Q(x)= x(x− 1)...(x− (2n +1))$ в целых точках кратны $22n.$

Поделим $P(x)$ на $Q(x)$ с остатком: $P(x)=Q (x)S(x)+R(x)$ . Поскольку старший член $Q(x)$ равен 1, $R (x)∈ ℤ[x]$ , причем $R(x)$ будет удовлетворять тем же условиям, которым удовлетворяет $P(x)$ , и к тому же будет иметь степень не выше $2n+ 1$ . Поделив его на $22n$ , мы получим многочлен степени не выше $2n+1$ , значения которого $2n+2$ подряд идущих целых точках целые. Из этого следует, что целыми являются все его значения в целых точках (это доказывается по индукции с использованием разностного многочлена). Таким, образом, у многочлена $R(x)$ все значения в целых точках кратны $22n$ , а тогда это верно и для многочлена $P (x)$ .

Курсы

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

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

Задача 7#82683Максимум баллов за задание: 7

Турист прибыл на остров, где живут 100 волшебников, каждый из которых может быть рыцарем или лжецом. Он знает, что на момент его приезда один из ста волшебников — рыцарь (но не знает, кто именно), а остальные — лжецы. Турист может выбрать любых двух волшебников $A$ и $B$ и попросить $A$ заколдовать $B$ заклинанием Вжух!, которое меняет сущность (превращает рыцаря в лжеца, а лжеца в рыцаря). Волшебники выполняют просьбы туриста, но если в тот момент волшебник $A$ — рыцарь, то сущность $B$ действительно меняется, а если $A$ — лжец, то не меняется. Турист хочет после нескольких последовательных просьб одновременно знать сущность хотя бы $k$ волшебников. При каком наибольшем $k$ он сможет добиться своей цели?

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

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

Подсказка 1

Можно для начала попробовать побыть в роли туриста и посмотреть на количество рыцарей. Какую закономерность можно заметить? Помним, что турист не знает, кто кем был изначально, но можно посмотреть на ситуацию с двух сторон.

Подсказка 2

Докажем, что ни в один момент времени ни про какое множество волшебников нельзя доказать, что в нём четное число рыцарей.

Подсказка 3

Рассмотрите первый такой случай. А что было до?

Подсказка 4

В целом не за что зацепиться, кроме как за последний "вжух" в этом множестве. Разберем случаи роли человека, который мог его сказать?

Подсказка 5

Осталось лишь придумать пример...так как мы хотим узнать роль одного, попробуем минимизировать число людей, которые меняли свой облик!

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

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

Изначально такого множества точно нет. Рассмотрим первый момент, когда удалось про некоторое множество $A$ доказать, что в нем четное число рыцарей. Пусть последним ходом «Вжух!» говорил волшебник $b$ . Несложным переборов вариантов можно убедится, что на прошлом ходу симметрическая разность $A$ и $b$ тоже содержала четное количество рыцарей, что противоречит выбранному первому такому моменту.

_________________________________________________________________________________________________________________________________________________________________________________

Пример. Пусть все волшебники с $1$ -го по $99$ -го поменяют сущность $100$ -го. Легко видеть, что в результате он в любом случае станет рыцарем.

Ответ: 1

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

Задача 8#139322Максимум баллов за задание: 7

Даны одинаковые на вид 32 настоящие и 32 фальшивые монеты. Все фальшивые монеты весят поровну и меньше настоящих, которые тоже все весят одинаково. Как за шесть взвешиваний на весах с двумя чашами определить тип хотя бы семи монет?

Источники: СПбОШ - 2024, 10.2 (см. pdmi.ras.ru)

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

Если за $k ≤$ 6 ходов мы сможем определить тип хотя бы $k+ 1$ монет, то можно сравнивать монеты с известными, и за $6$ взвешиваний узнаем тип $7$ монет. Такую ситуацию назовём победой.

Сначала сравним две монеты, если они разные, то мы знаем тип $2$ монет и это победа. Если они одинаковые, сравним эту пару с любой парой оставшихся монет. Если они одинаковые, то мы знаем тип первых двух монет, поменяем пару монет при взвешивании и тогда узнаем, по результату взвешивания мы узнаём тип четырёх монет, это победа. Если весы показали равенство, то мы знаем что у $4$ монет одинаковый тип.

Потом взвесим эту четверку с другой четвёркой, если неравенство, то за три взвешивания опередили тип четырёх монет, это победа. Если равенство, то знаем что у $8$ монет одинаковый тип. Действуя таким образом еще три раза, мы либо победим, либо найдём $64$ одинаковых монет, но это противоречит условию.

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

Задача 9#139331Максимум баллов за задание: 7

Рассмотрим всевозможные квадратные трехчлены вида $x2+ax+ b,$ где $a$ и $b$ — натуральные числа, не превосходящие некоторого натурального числа $N.$ Докажите, что количество пар таких трехчленов, имеющих общий корень, не превосходит $2 N .$

Источники: СПбОШ - 2024, 10.4 (см. pdmi.ras.ru)

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

Подсказка 1

Не совсем ясно, с чего начать. Давайте для начала попробуем доказать, что для двух произвольных трехчленов, соответствующих условию, общий корень — целое число.

Подсказка 2

Первый шаг к тому, что корень является целым, — его рациональность. Подумайте, есть ли какой-то способ представить корень в виде частного.

Подсказка 3

Если всё ещё ничего не приходит в голову, припомните факт о том, что общий корень так же будет корнем разности трехчленов.

Подсказка 4

Рациональность есть, чтобы доказать, что корень целый, обратите внимание, что коэффициент при старшем члене многочлена — 1.

Подсказка 5

Теперь имеем, что общий корень двух трехчленов — целое число, едем дальше. Теперь было бы очень сподручно как-то оценить количество пар сверху.

Подсказка 6

Сравните общий корень и N, пользуясь фактом, что наш корень — делитель свободного члена.

Подсказка 7

Обозначим общий корень буквой k, где k принимает все значения от 1 до N. Тогда при фиксированном k, сколько значений может принимать коэффициент a? Постройте оценку количества пар сверху и расширьте её на все k от 1 до N.

Подсказка 8

В полученной оценке имеем сумму обратных квадратов. Припомните общеизвестный факт об оценке суммы обратных квадратов и приведите доказательство.

Подсказка 9

Воспользуйтесь сравнением с телескопической суммой.

Подсказка 10

Если Вы из прошлой подсказки ничего не поняли из-за страшных слов, то на самом деле всё просто. Сравните сумму 1/k² c 1/(k(k-1)).

Подсказка 11

Если всё ещё чувствуете затруднения, представьте каждый член суммы, с которой сравниваем, как разность, чтобы лишние члены схлопнулись.

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

Любой общий корень $x 0$ трёхчленов $x2+a x+ b 1 1$ и $x2 +a x+ b 2 2$ также является корнем их разности:

(a1− a2)x+ (b1− b2)= 0

Отсюда следует, что $x0$ — рациональное число. Но у квадратных трёхчленов со старшим коэффициентом $1$ все рациональные корни автоматически являются целыми. Итак, любой общий корень $x0$ двух таких трёхчленов — целое число. К тому же, видно, $x0 <0$ и $|x|≤ N, 0$ так как $x 0$ является делителем свободного члена.

Оценим количество пар трёхчленов, имеющих общий корень $− k,$ где $k∈ {1,2,...,N}.$ При заданном $k$ коэффициент $a$ такого трёхчлена однозначно задаётся коэффициентом $b,$ который может принимать не более $N- k$ значений, поскольку он должен делиться на $k.$ Таким образом, количество таких пар не больше чем:

1 N (N ) N2 2 ⋅k- k-− 1 < 2k2

Складывая такие оценки по всем $k$ от $1$ до $N,$ получаем, что общее число пар не превосходит:

N2( 1-+ 1-+ ⋅⋅⋅+ 1-) = N2-N∑ 1- 2 12 22 N2 2 k=1 k2

Как известно, сумма обратных квадратов меньше $2.$

Докажем оценку:

N∑ 1 N∑ 1 1 1 1 k2 < 1+ (k−-1)k = 1+ 1⋅2 + 2⋅3 + ⋅⋅⋅+ (N-− 1)N k=1 k=2

Это телескопическая сумма:

1+ (1 − 1)+ (1 − 1) + ⋅⋅⋅+(--1--− 1) = 1+1 −-1 =2− -1< 2 1 2 2 3 N − 1 N N N

Следовательно, общее число пар можно оценить:

2∑N 2 N-- 12 < N-⋅2= N2 2 k=1k 2

Таким образом, оцениваемое количество пар меньше $2 N .$

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

Задача 10#139335Максимум баллов за задание: 7

На числовой оси отмечено 2 000 000 точек с целыми координатами. Рассматриваются отрезки длин 97, 100 и 103 с концами в этих точках. Какое наибольшее количество таких отрезков может быть?

Источники: СПбОШ - 2024, 10.5 (см. pdmi.ras.ru)

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

Подсказка 1

Возьмем, например, отрезки длины 97. Рассмотрите цепочки из них и ответьте на следующий вопрос: чему будет равно количество отрезков в такой цепочке?

Подсказка 2

Да, отрезков в цепочке будет на 1 меньше, чем точек в цепочке. Тогда суммарное количество отрезков длины 97 будет (N - a), где a — количество цепочек.

Подсказка 3

Проделайте аналогичные рассуждения для отрезков длины 100 и 103. Предъявите в виде равенства общее число отрезков и критерий состоятельности оценки.

Подсказка 4

Критерий: a + b + c ≥ 97 + 100 + 103, где b и c — количества цепочек для чисел 100 и 103 соответственно.

Подсказка 5

Для проверки критерия предположите, что по какому-то из модулей присутствуют не все остатки.

Подсказка 6

Дело за малым: вычислите точное количество отрезков и предъявите ответ.

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

Пример: Указанное количество отрезков получается, если отметить на числовой оси $2000000$ последовательных целых чисел.

Оценка: Покрасим отрезки длины $97,100$ и $103$ в красный, синий и зелёный цвета соответственно. Все $N = 2000000$ точек разобьются на $a$ красных цепочек. В каждой такой цепочке остатки всех чисел по модулю $97$ одинаковы, а количество отрезков ровно на $1$ меньше, чем точек. Поэтому суммарное количество красных отрезков равно $N − a.$

Аналогично, пусть имеется $b$ синих и $c$ зелёных цепочек. Тогда общее количество отрезков равно:

(N − a)+ (N − b)+(N − c)= 3N − (a+ b+c)

Оценка будет доказана, если мы проверим, что

a+ b+ c≥97+ 100+103

Если у исходных $N$ чисел присутствуют все возможные остатки по каждому из модулей $97,100$ и $103,$ то $a≥ 97,b≥ 100,c≥ 103,$ и нужное неравенство очевидно.

Предположим теперь, что по одному из трёх модулей (например, по модулю $97$ ) присутствуют не все остатки. Тогда в каждой синей цепочке (которая соответствует отрезкам длины $100$ ) содержится не более чем $96$ точек. Действительно, переход от числа $k$ к числу $k+ 100$ по синему отрезку соответствует прибавлению $3$ по модулю $97.$ Если бы присутствовали все $97$ остатков, то в цепочках было бы не менее $97$ точек. Следовательно,