Тема Заключительный этап ВсОШ

Закл (финал) 9 класс

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

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

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

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

Подтемы раздела заключительный этап всош

Разделы подтемы Закл (финал) 9 класс

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

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

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

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

Источники: ВСОШ, ЗЭ, 2025, 9.1 (olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте придумать пример такого разделения и раскраски.

Подсказка 2:

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

Подсказка 3:

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

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

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

Докажем, что такая раскраска подойдёт. Рассмотрим общий отрезок границы двух треугольников. Если этот отрезок диагональный, то сверху к нему примыкает чёрный треугольник, а снизу белый. Если отрезок горизонтальный, то к нему сверху примыкает белый треугольник, а снизу — чёрный; случай вертикального отрезка аналогичен. Поэтому такая раскраска подходит.

Ответ:

да, верно

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

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

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

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

Диагонали выпуклого четырёхугольника $ABCD$ пересекаются в точке $E.$ Точки касания описанных окружностей треугольников $ABE$ и $CDE$ с их общими внешними касательными лежат на окружности $ω.$ Точки касания описанных окружностей треугольников $ADE$ и $BCE$ с их общими внешними касательными лежат на окружности $γ.$ Докажите, что центры окружностей $ω$ и $γ$ совпадают.

Источники: ВСОШ, ЗЭ, 2025, 9.2 (см. olympiads.mccme.ru)

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

Подсказка 1:

Давайте введём следующие обозначения: O_{AB}, O_{BC}, O_{CD}, O_{AD} — центры окружностей (ABE), (BCE), (CDE), (ADE), a T₁, T₂ — точки касания одной из внешних касательных к окружностям, описанным около ABE и CDE. Обратите внимание на прямоугольную трапецию O_{AB}T₁T₂O_{CD}. В частности, на середину O_{AB}O_{CD}. Что можно про неё сказать?

Подсказка 2:

Если сделать симметрию относительно точки O, во что перейдет окружность ω? Какие выводы можно сделать?

Подсказка 3:

Точка O — центр ω. Аналогичные рассуждения можно проделать с серединой O_{AD}O_{BC}. Значит, мы хотим показать, что середины отрезков O_{AD}O_{BC} и O_{AB}O_{CD} совпадают. А что для этого достаточно доказать?

Подсказка 4:

Достаточно доказать, что четырехугольник O_{AB}O_{BC}O_{CD}O_{AD} — параллелограмм. Попробуйте для этого показать, что его противолежащие стороны параллельны.

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

Обозначим центры описанных окружностей треугольников $ABE,$ $BCE,$ $CDE,$ $ADE$ через $O , AB$ $O , BC$ $O , CD$ $O AD$ соответственно. Пусть $T1,$ $T2$ — точки касания одной из общих касательных с описанными окружностями треугольников $ABE$ и $CDE$ соответственно; обозначим через $O$ и $T$ середины отрезков $OABOCD$ и $T1T2$ соответственно. Тогда в прямоугольной трапеции $OABT1T2OCD$ прямая $OT$ — средняя линия, поэтому она является серединным перпендикуляром к отрезку $T1T2.$ Заметим, что окружность $ω$ симметрична относительно прямой $OABOCD,$ на которой также лежит точка $O,$ значит, $O$ — центр $ω.$

$PIC$

Аналогично получаем, что середина отрезка $O O AD BC$ является центром $γ.$ Поэтому утверждение задачи равносильно тому, что $O O O O AB BC CD AD$ — параллелограмм. Для доказательства этого достаточно заметить, что $O O AB BC$ и $O O CD AD$ — серединные перпендикуляры к отрезкам $EB$ и $ED,$ поэтому $OABOBC ∥ OCDOAD;$ аналогично, $OABOAD ∥ OBCOCD,$ откуда и следует требуемое.

$PIC$

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

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

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

2 n (a− 1)(a − 1)...(a − 1)

является точным квадратом.

Источники: ВСОШ, ЗЭ, 2025, 9.3 (см. olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте сначала вручную разобраться с n = 1, 2, 3. Для этих случаев достаточно вспомнить утверждение о том, что если произведение двух взаимно простых чисел — квадрат, то каждое из них также является квадратом. В частности, при n = 3 надо поработать с нодами скобок a - 1, a + 1, a² + a + 1. Быть может, этот ход мыслей можно развить и для больших n?

Подсказка 2:

Итак, скорее всего вы поняли, что n = 1, 2 подойдёт, а n = 3 — нет. Чем остальные случаи отличаются. Например, если n > 3, то оно находится между двумя натуральными степенями двойки. То есть существует такое натуральное k, что 2^k ≤ n < 2^{k + 1}. Подумайте, как это можно использовать.

Подсказка 3:

Если записать скобку a^{2^k} – 1 как (a^{2^{k – 1}} – 1)(a^{2^{k – 1}} + 1), то становится ясно, что все произведение состоит из скобки a^{2^{k – 1}} + 1 и скобок вида a^m – 1. А как насчёт того, чтобы посмотреть на нод выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с произвольной скобкой a^m – 1?

Подсказка 4:

Нод второго выражения и a^m – 1 кратен ноду первого выражения и a^m - 1. Чтобы было проще работать, вот вам интересный факт: нод второй скобки и a^m – 1 равен a^нод(2^k, m) – 1. Осталось поработать с нодом 2^k и m.

Подсказка 5:

Исходя из выбора k, ясно, что нод 2^k и m не превышает 2^{k – 1}. Попробуйте теперь показать, что ноды выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с a^m – 1 совпадают. Кажется, это раскроет идею подсказки 3.

Подсказка 6:

Стало быть, a^{2^{k – 1}} + 1 — точный квадрат. А вас это не смущает?

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

Заметим, что для $n= 1$ подойдёт $a =10.$ Для $n =2$ подойдёт $a= 8.$

Предположим, что для $n =3$ нашлось требуемое число $a.$ Тогда число

2 3 3 2 (a − 1)(a − 1)(a − 1)= (a− 1) (a +1)(a + a+ 1)

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

2 a + a+ 1= a(a+ 1)+1,

числа $a+ 1$ и $a2+ a+ 1$ взаимно просты. Раз число $a+1$ нечётно, числа $a+ 1$ и $a− 1$ также взаимно просты. Следовательно, числа $a+ 1$ и $(a− 1)(a2+a +1)$ — точные квадраты. В частности, число $a+ 1$ при делении на 3 может давать лишь остаток 0 или 1, а тогда число $a− 1$ не делится на 3. Отсюда

2 НО Д(a− 1,a + a+1)= НОД (a − 1,(a +2)(a − 1)+ 3)= НО Д(a − 1,3)=1,

значит, числа $a− 1$ и $a2 +a+ 1$ также являются точными квадратами. Но второе являться квадратом не может, поскольку

a2 < a2 +a+ 1< (a+1)2.

Противоречие.

Осталось доказать, что требуемого $a$ не существует при $n ≥4.$ Предположим, что такое $a$ нашлось. Возьмём такое натуральное $k ≥2,$ что $2k ≤n < 2k+1.$ Поскольку

a2k − 1= (a2k−1 − 1)(a2k−1 + 1),

число

(a− 1)(a2 − 1)...(an− 1)

представляется в виде произведения $2k−1 a +1$ и нескольких множителей вида $m a − 1,$ где $1≤ m ≤n$ и $k m ⁄=2 .$

Докажем, что множитель $2k−1 a +1$ взаимно прост со всеми остальными множителями в этом разложении. Пусть $2k−1 a + 1$ и $am − 1$ имеют некоторый общий делитель $d.$ Тогда и НОД $k a2 − 1$ и $am − 1$ кратен $d.$ Но

k k НОД(a2 − 1,am− 1)= aНОД(2 ,m)− 1.

Поскольку $k m ⁄= 2$ и $k+1 m ≤n < 2 ,$ число $m$ не может делиться на $k 2 .$ Таким образом, $k Н ОД(2,m )$ — степень двойки, не превосходящая $k−1 2 .$ Следовательно, $2k−1 a − 1$ делится на НОД $2k a − 1$ и $m a − 1,$ а, значит, делится и на $d.$ Поскольку $a$ чётно, числа $2k−1 a − 1$ и $2k−1 a + 1$ не имеют общих делителей, отличных от 1, значит, $d= 1,$ что и требовалось.

Множитель $2k−1 a + 1$ взаимно прост со всеми остальными множителями в произведении, являющемся точным квадратом, поэтому он сам является точным квадратом. Тогда $k−1 a2 +1$ и $k−1 a2$ — отличающиеся на 1 квадраты натуральных чисел, что невозможно. Значит, наше предположение неверно, и для $n≥ 4$ требуемых чисел $a$ не найдётся.

Ответ:

$n =1$ и $n =2$

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

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

Шахматного короля поставили на клетку доски 8 × 8 и сделали им 64 хода так, что он побывал на всех клетках и вернулся в исходную клетку. В каждый момент времени вычислялось расстояние от центра клетки, в которой находился король, до центра всей доски. Назовём сделанный ход приятным, если в результате хода это расстояние стало меньше, чем было до хода. Найдите наибольшее возможное количество приятных ходов. (Шахматный король за один ход передвигается на клетку, соседнюю по стороне или по углу.)

Источники: ВСОШ, ЗЭ, 2025, 9.4 (см. olympiads.mccme.ru)

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

Подсказка 1:

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

Подсказка 2:

Давайте клеткам, соответствующим самому маленькому значению, сопоставим 1, клеткам, соответствующим следующему значению — 2 и так далее. Как, используя эту нумерацию, сделать оценку?

Подсказка 3:

Смотрите, например, ход из клетки с номером 2 будет приятным лишь в том случае, если он сделан в клетку с номером 1. Но клеток с номером 2 — 8, а с номером 1 — 4, значит, как минимум, 4 хода из клеток с номером 2 будут неприятными. Попробуйте развить эту мысль на другие клетки.

Подсказка 4:

Если рассмотреть переходы из клеток с номером 1 и 2 в клетки с номерами, не меньшими 6, должна получиться оценка в 44 приятных хода. Не забудьте придумать пример.

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

Докажем, что среди ходов должно быть хотя бы 20 неприятных (а значит, количество приятных ходов не больше 44). Расставим в клетках числа, как показано на первом рисунке; клетки с одинаковыми числами удалены на одно и то же расстояние от центра, а клетки с меньшими номерами ближе к центру, чем клетки с большими.

$PIC$

Каждый ход из клетки с числом 1 не уменьшает расстояния до центра и потому неприятен — таких ходов 4. Ход из клетки с числом 2 может быть приятным, только когда он идёт в клетку с числом 1. Но на доске восемь чисел 2 и только четыре числа 1, поэтому хотя бы четыре хода из клеток с числом 2 будут неприятными.

Рассмотрим теперь ходы, ведущие в 32 клетки с числами, не меньшими 6. Заметим, что эти ходы не могут идти из клеток с числами 1 и 2, то есть в рассуждении выше они не учтены. Такой ход может быть приятным, только если он идёт из клетки с номером, не меньшим 7; однако таких клеток всего 20. Значит, среди рассмотренных ходов ещё $32 − 20= 12$ неприятных, и общее количество неприятных ходов не меньше, чем $4+ 4+ 12 =20.$

Пример обхода, в котором 44 приятных хода (синие), приведён на втором рисунке (начинаем движение королём с левой нижней клетки вверх).

$PIC$

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

Ответ:

44 хода

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

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

Пусть $P (x) 1$ и $P (x) 2$ — приведённые квадратные трёхчлены, а точки $A 1$ и $A 2$ — соответственно вершины парабол $y = P (x) 1$ и $y =P2(x).$ Через $m(g(x))$ будем обозначать наименьшее значение функции $g(x).$ Известно, что разности

m(P1(P2(x)))− m(P1(x)) и m(P2(P1(x)))− m (P2(x))

оказались равными положительными числами. Найдите угол между прямой $A1A2$ и прямой, содержащей ось $Ox.$

Источники: ВСОШ, ЗЭ, 2025, 9.5 (см. olympiads.mccme.ru)

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

Обозначим данные трёхчлены:

2 P1(x)=(x− x1)+ y1

2 P2(x) =(x− x2) + y2,

где $A1(x1;y1)$ и $A2(x2;y2)$ — координаты вершин парабол. Тогда $m(P1(x))= y1,$ а

P (P (x))= ((x − x )2+y − x )2+ y . 1 2 2 2 1 1

Если $y2 ≤x1,$ то минимальное значение выражения

((x− x2)2+ y2− x1)2

равняется нулю, откуда

m(P1(P2(x)))− m(P1(x))=y1− y1 = 0.

Последнее противоречит тому, что

m (P1(P2(x)))− m(P1(x))

— положительное число. Таким образом, $y2 > x1,$ откуда

m(P1(P2(x)))= (y2− x1)2+ y1, m(P1(P2(x)))− m(P1(x))=(y2− x1)2.

Аналогично, $y1 > x2$ и

2 m (P2(P1(x)))− m(P2(x))= (y1− x2).

Теперь условие равенства разностей переписывается в виде $(y − x)2 = (y − x )2. 1 2 2 1$ Отсюда, поскольку $y > x 2 1$ и $y >x , 1 2$ получаем $y − x = y − x , 1 2 2 1$ то есть $y − y = −(x − x). 2 1 2 1$ Значит, искомый угол равен $45∘.$

Ответ:

$45∘$

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

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

Петя выбрал 100 попарно различных положительных чисел, меньших 1, и расставил их по кругу. Затем он проделывает с ними операции. За одну операцию можно взять три стоящих подряд (именно в таком порядке) числа $a,b,c$ и заменить число $b$ на $a− b+ c$ . При каком наибольшем $k$ Петя мог выбрать исходные числа и сделать несколько операций так, чтобы после них среди чисел оказалось $k$ целых?

Источники: ВСОШ, ЗЭ, 2025, 9.6 (olympiads.mccme.ru)

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

Оценка. Покажем, что целых чисел никогда не станет больше 50. Будем следить за разностями между числом и следующим за ним по часовой стрелке. Если подряд стояли числа $a,$ $b,$ $c,$ то их разности были равны $a− b$ и $b− c.$ После применения операции к числу $b$ получаются числа $a,a− b+c$ и $c,$ разности которых равны

a− (a− b+c)= b− c, (a− b+ c)− c= a− b.

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

Пример. Для начала расставим по кругу попеременно числа $0,$ $1$ и $0,$ $2.$ Если с каждым числом $0,2$ проделать операцию, то оно будет заменено на $0,1− 0,2+ 0,1 =0,$ и числа через одно будут целыми. Осталось подправить пример так, чтобы все числа стали различными. Для этого достаточно прибавить к каждому числу $0,1$ по своему маленькому числу, а к каждому числу $0,2$ — сумму чисел, прибавленных к его соседям. Например, выбрав $t=0,001,$ можно прибавить к последовательным числам $0,1$ числа $0,$ $t,$ $2t,...,47t,$ $48t,$ $50t;$ тогда к числам $0,2$ будут прибавляться числа $t,$ $3t,$ $5t,...,95t,$ $98t,$ $50t.$ В результате все числа станут различными.

Ответ:

при $k = 50$

Курсы

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

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

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

В строку выписаны числа 1, 2, 3, …, 60 (ровно в таком порядке). Игорь и Руслан по очереди ставят знаки $+,−$ и $×$ между ними, начинает Игорь; за ход каждый ставит один знак. Когда между каждыми двумя соседними числами поставлен знак, вычисляется значение полученного выражения. Если оно делится на 3, то победа присуждается Игорю, иначе Руслану. Кто из игроков может выиграть, независимо от действий соперника?

Источники: ВСОШ, ЗЭ, 2025, 9.7 (см. olympiads.mccme.ru)

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

Подсказка 1:

Ясно, что в контексте задачи все числа для удобства можно заменить на остатки при делении на 3. Попробуйте придумать какую-то простую стратегию за Игоря, основанную на симметрии, чтобы все слагаемые взаимно уничтожились.

Подсказка 2:

Значит, Игорь должен сделать так, чтобы для любого слагаемого со знаком + нашлось слагаемое, равное по модулю, но со знаком минус.

Подсказка 3:

Всего имеется 59 мест, в которые нужно поставить знаки. Как насчёт того, чтобы Игорь первым ходом поставил некоторый знак в центральный, а потом как-то отвечал на ходы Руслана в другую половину?

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

Заменим все числа в строке на их остатки от деления на 3, от этого результат игры не изменится. Получим строку $1,$ $2,$ $0,$ …, $1,$ $2,$ $0.$ Промежутки между числами пронумеруем слева направо от 1 до 59. Первым ходом Игорь ставит знак минус в 30-й промежуток, а все остальные промежутки он разбивает на пары вида $(i,30+ i).$ Если Руслан ставит в какой-то промежуток знак плюс или минус, то Игорь в парный промежуток ставит минус или плюс соответственно. А если Руслан ставит знак умножить, то Игорь ставит в парный промежуток также знак умножить. Когда все знаки расставлены, полученное выражение разбивается на несколько слагаемых. При этом в левой и правой половинах выражения набор слагаемых одинаковый, но берутся они с противоположными знаками. Следовательно, его значение будет давать остаток 0 при делении на 3.

Ответ:

Игорь

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

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

На периметре треугольника $ABC$ выбраны точки $D , 1$ $D , 2$ $E , 1$ $E , 2$ $F , 1$ $F 2$ так, что при обходе периметра точки встречаются в порядке $A,$ $F1,$ $F2,$ $B,$ $D1,$ $D2,$ $C,$ $E1,$ $E2.$ Оказалось, что

AD1 = AD2 = BE1 = BE2 = CF1 =CF2.

Докажите, что периметры треугольников, образованных тройками прямых $AD1,$ $BE1,$ $CF1$ и $AD2,$ $BE2,$ $CF2,$ равны.

Источники: ВСОШ, ЗЭ, 2025, 9.8 (см. olympiads.mccme.ru)

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

Начнём со следующей полезной леммы.

Лемма. Пусть точки $F$ и $E$ выбраны соответственно на сторонах $AB$ и $AC$ параллелограмма $ABKC$ так, что $BE =CF.$ Тогда точка $K$ равноудалена от прямых $BE$ и $CF.$

Доказательство. Поскольку $BK ∥EC$ и $CK ∥FB,$ имеем $SKBE =SKBC = SKFC.$ Так как $BE = CF,$ отсюда и следует, что расстояния от точки $K$ до прямых $BE$ и $CF$ равны.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Перейдём к решению. Пусть прямые из условия образуют треугольники $X1Y1Z1$ и $X2Y2Z2$ (точки обозначены как на рис.). Выберем точку $K$ так, что $ABKC$ — параллелограмм; согласно лемме, точка $K$ равноудалена от прямых $BE1,CF1,BE2$ и $CF2$ ; значит, существует окружность с центром $K,$ касающаяся этих прямых в некоторых точках $P1,Q1,P2$ и $Q2$ соответственно. Тогда из равенств отрезков касательных вытекает, что

BX − CX = BP + X P − X Q + CQ =BP +CQ = 1 1 1 1 1 1 1 1 2 2

BP2− X2P2+ X2Q2+ CQ2 = CX2 − BX2.

$PIC$

Аналогично получаем, что $CY1− AY1 = AY2− CY2$ и $AZ1− BZ1 =BZ2 − AZ2.$ Складывая полученные три равенства, получаем требуемое равенство периметров.

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

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

Петя и Вася знают лишь натуральные числа, не превосходящие $109 − 4000.$ Петя считает хорошими числа, представимые в виде

abc +ab+ ac+bc,

где $a,b$ и $c$ — натуральные числа, не меньшие 100. Вася считает хорошими числа, представимые в виде

xyz − x − y− z,

где $x,y$ и $z$ — натуральные числа, большие 100. Для кого из них хороших чисел больше?

Источники: ВСОШ, ЗЭ, 2024, 9.1 (см. olympiads.mccme.ru)

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

Подсказка 1:

Чтобы сравнить количества чисел, можно построить какое-то соответствие. Например, каждому числу одного человека сопоставить какое-то число другого человека.

Подсказка 2:

Попробуйте сопоставить числу Пети какое-то число Васи. А потом найдите какое-нибудь число Васи, которому не сопоставлено число Пети.

Подсказка 3:

Пусть k — число Пети. Что можно сказать про число k − 2?

Подсказка 4:

Пусть k = abc + ab + ac + bc, тогда k − 2 = (a + 1)(b + 1)(c + 1) − (a + 1) − (b + 1) − (c + 1).

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

Если число

9 k= abc+ ab+ ac+ bc≤ 10 − 4000

хорошее для Пети, то число

k− 2= (a+1)(b+1)(c+ 1)− (a+ 1)− (b+ 1)− (c+1)

является хорошим для Васи. Значит, если для Пети есть $p$ хороших чисел, то мы предъявили $p$ различных чисел, хороших для Васи, и все они строго меньше, чем $109− 4000.$ Но число

109− 4000 =(1000 − 1)⋅1000⋅(1000 +1)− (1000− 1)− 1000− (1000+ 1)

также является хорошим для Васи; поэтому для Васи есть хотя бы $p+1$ хорошее число.

Ответ:

для Васи

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

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

У натурального числа ровно 50 делителей. Может ли оказаться, что никакая разность двух различных его делителей не делится на 100?

Источники: ВСОШ, ЗЭ, 2024, 9.2 (см. olympiads.mccme.ru)

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

Подсказка 1:

Ясно, что нужно смотреть на последние две цифры всех чисел. Если у каких-то двух они совпадают, то их разность будет делиться на 100.

Подсказка 2:

Давайте назовём последние две цифры числа "хвостом". Заметим, что хвост числа n даёт такие же остатки при делении на некоторые числа, что и само n.

Подсказка 3:

Если число делится на 5, может ли оно обладать таким свойством? Сколько у него будет делителей, кратных 5? А сколько всего существует "хвостов", кратных 5?

Подсказка 4:

Покажите, что у числа хотя бы половина делителей будет делиться на 5. Попробуйте аналогично разобрать случаи, когда n нечётно и когда n кратно 2, но не 4.

Подсказка 5:

Итак, кажется, вы пришли к тому, что такое число не делится на 5 и делится на 2 хотя бы во второй степени. Попробуйте обозначить через r степень вхождения 2 в n и поработать с ней.

Подсказка 6:

Докажите, что количество делителей кратно r + 1. Для этого достаточно разбить делители некоторым образом на цепочки по r + 1 делителю в каждой.

Подсказка 7:

Используя всю информацию, попробуйте оценить количество нечётных делителей, делителей, кратных 2, но не 4, и кратных 4.

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

Предположим, что такое число $n$ существует. Условие равносильно тому, что все числа, образованные последними двумя цифрами делителей, различны (мы считаем, что к однозначным числам спереди приписаны нули). Назовём такую пару последних цифр хвостом числа. Заметим, что хвост числа имеет те же остатки от деления на $4$ и на $5,$ что и исходное число.

Предположим, что $n$ делится на 5. Тогда для любого его делителя $d,$ не кратного $5,$ существует и делитель $5d,$ кратный $5.$ При этом для разных делителей $d$ мы получаем разные делители $5d;$ поэтому количество кратных $5$ делителей не меньше половины, то есть не меньше $25.$ Но такие делители имеют хвосты, оканчивающиеся либо на $0,$ либо на $5.$ Таких возможных хвостов не больше $20,$ поэтому два из них совпадают. Это противоречие показывает, что $n$ не делится на $5,$ и хвосты его делителей не могут оканчиваться на $0$ или $5.$

Если число $n$ нечётно, то все его делители также нечётны. Однако существует всего $50$ возможных нечётных хвостов, и $10$ из них оканчиваются на $5,$ то есть не могут появиться. Поэтому и в этом случае найдутся два одинаковых хвоста.

Если число $n$ делится на $2,$ но не на $4,$ то все его делители разбиваются на пары $(d,2d),$ где $d$ — нечётный делитель $n.$ При этом все числа вида $2d$ имеют хвосты, не делящиеся на $4,$ а таких хвостов (при этом не делящихся на $5$ ) всего $20.$ Значит, два из этих хвостов одинаковы.

Наконец, пусть наибольшая степень двойки, на которую делится $n,$ равна $2r,$ где $r≥ 2.$ Тогда, если $d$ — нечётный делитель $n,$ то числа $d,$ $2d,$ $22d,$ …, $2rd$ также будут делителями $n,$ и этим исчерпываются все делители $n.$ Поэтому общее число делителей $n$ будет кратно $r+1.$ Таким образом, $50$ делится на $r+ 1$ и, значит, $r ≥4.$

Тогда $n$ имеет

-50-≤ 10 r+ 1

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

Ответ:

нет

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

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

Двум мальчикам выдали по мешку картошки, в каждом мешке по 150 клубней. Ребята по очереди перекладывают картошку, каждый своим очередным ходом перекладывает ненулевое количество клубней из своего мешка в чужой. При этом они должны соблюдать условие новой возможности: на каждом ходе мальчик должен переложить больше клубней, чем у него было в мешке перед любым из его предыдущих ходов (если такие ходы были). Так, первым своим ходом мальчик может переложить любое ненулевое количество, а своим пятым ходом мальчик может переложить 200 клубней, если перед его первым, вторым, третьим и четвёртым ходами количества клубней в его мешке были меньше 200. Какое максимальное суммарное количество ходов могут совершить ребята?

Источники: ВСОШ, ЗЭ, 2024, 9.3 (см. olympiads.mccme.ru)

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

Подсказка 1.

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

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

Пусть в процессе было $N$ ходов.

Рассмотрим $k$ -й ход. Обозначим через $ak$ количество клубней у мальчика, делавшего этот ход, сразу после хода. Тогда у другого мальчика после хода $300− ak$ клубней. Также обозначим через

a0 = 150= 300− a0

количество клубней у (любого) мальчика перед первым ходом.

В этих обозначениях, перед $k$ -м ходом у мальчика, делавшего его, было $300− a k−1$ клубней, а после него — $a k$ клубней. Значит, на этом ходу он передавал $300− a − a k−1 k$ клубней. Если $k≥ 3,$ то это количество должно быть больше, чем количество клубней у этого мальчика перед его предыдущим ( $(k− 2)$ -м) ходом, то есть не меньше, чем $300− a . k−3$ Итак,

300− ak−1− ak >300− ak−3 ⇐ ⇒ ak−3 > ak−1 +ak.

Поскольку все числа $ai$ целые, получаем, что

ak−3 ≥ak−1+ ak+1

при всех $k =3,4,$ $...,N.$

Теперь можно получить оценки на числа $ai,$ действуя «с конца». Определим числа $b0,b1,$ $b2,...,$ условиями

b =b = b = 0; b = b + b+ 1. 0 1 2 k+3 k+1 k

Докажем, что $aN −k ≥ bk$ и $bk+1 ≥bk,$ индукцией по $k= 0,1,...,N.$ При $k =0,$ $1,2$ неравенства очевидны; для перехода, чтобы доказать неравенство при некотором $k ≥3,$ достаточно заметить, что

aN−k ≥aN −k+2 +aN−k+3+ 1≥ bk− 2+bk−3+ 1= bk,

bk+1 = bk−1+ bk− 2+1 ≥bk−2+ bk−3+ 1= bk.

Итак, мы получаем, что $a0 ≥ bN.$ Приведём таблицу первых значений чисел $bk :$


$k$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

$bk$	0	0	0	1	1	2	3	4	6	8	11	15	20	27	36	48	64	85	113	150	199

Значит, из условия $b ≤150 N$ получаем, что $N ≤19.$

Пример, когда дети могут сделать $19$ ходов, следует из построения выше. Изначально у каждого ребёнка по $b =150 19$ клубней. Пусть дети действуют так, чтобы после $k$ -го (с начала) хода у перекладывавшего оставалось ровно $b 19−k$ клубней; тогда на $k$ -м (с начала) ходе ребёнок перекладывает

300− b20−k− b19−k

клубней, а перед любым предыдущим его ходом у него будет $300− b i$ клубней при $i≥17− k,$ причём

300 − bi ≤ 300− b17−k < 300− b19−k− b20−k.

Значит, этот ход удовлетворяет условию, и дети могут сделать 19 таких ходов.

Ответ:

Интенсивы

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

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

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

Дан вписанный четырёхугольник $ABCD,$ в котором $∠A+ ∠D = 90∘.$ Его диагонали пересекаются в точке $E.$ Прямая $ℓ$ пересекает отрезки $AB,$ $CD,$ $AE$ и $ED$ в точках $X,$ $Y,$ $Z$ и $T$ соответственно. Известно, что $AZ =CE$ и $BE = DT.$ Докажите, что длина отрезка $XY$ равна диаметру окружности, описанной около треугольника $ETZ.$

Источники: ВСОШ, ЗЭ, 2024, 9.4 (см. olympiads.mccme.ru)

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

Применяя теорему Менелая к треугольнику $ETZ$ и секущим $AXB$ и $CY D,$ получаем

AZ- BE- XT- CE- DT- YZ- AE ⋅BT ⋅XZ = CZ ⋅DE ⋅ YT =1.

Из равенств $AZ = CE$ и $BE = DT$ следует, что $AE = CZ$ и $BT = DE.$ Подставляя все эти равенства, получаем, что

XT YZ XZ- = YT;

это означает, что точки $X$ и $Y$ симметричны относительно середины $S$ отрезка $ZT$ (см. рис.).

Из условия следует, что лучи $AB$ и $DC$ пересекаются в некоторой точке $F$ под прямым углом. Тогда в прямоугольном треугольнике $XF Y$ медиана $FS$ равна половине гипотенузы $XY.$

Обозначим через $M$ и $N$ середины $AD$ и $BC$ соответственно, а через $O$ — центр окружности $(ABCD ).$ Тогда $O$ — точка пересечения серединных перпендикуляров к $AC$ и $BD,$ которые совпадают с серединными перпендикулярами к $EZ$ и $ET$ соответственно. Значит, $O$ — также центр окружности $(ET Z),$ а $OE$ — её радиус. Поэтому нам достаточно доказать, что $OE = FS.$ Мы докажем, что $OEF S$ — параллелограмм, откуда это и следует.

Поскольку $EN$ — медиана в треугольнике $EBC,$ а $MS$ — отрезок, соединяющий середины противоположных сторон четырёхугольника $AZT D,$ имеем

$PIC$

−−→ −−→ −−→ −→ −−E→N = EB-+EC--= DT +-AZ-= −M−→S. 2 2

В прямоугольном треугольнике $FBC$ проекции вектора медианы $−N−→F$ на прямые $BF$ и $CF$ равны $−−B→F∕2$ и $−C→F ∕2$ соответственно. Поскольку $O$ и $M$ — центры окружностей $(ABCD )$ и $(ADF )$ соответственно, при проекции на те же прямые первая попадает в середины отрезков $AB$ и $CD,$ а вторая — в середины $AF$ и $DF.$ Поэтому проекции вектора

−−→ −−→ −→ −−→ −−→ OM = AM − AO =− DM − DO

на эти прямые равны

−→ −→ −−→ −−→ −−→ −→ AP −-AB-= BF-, DF-−DO-= CF-. 2 2 2 2

Значит, проекции векторов $−N−→F$ и $−O−→M$ на наши две прямые соответственно равны, откуда $−N−→F =−O−M→.$

Итак,

−O→S = −−O→M +−M−S→ =−N−F→+ −E−→N = −−E→F,

откуда и следует, что $OEF S$ — параллелограмм.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Есть и другие доказательства того, что $OEF S$ — параллелограмм. Например, можно использовать тот факт, что точки $O$ и $F$ изогонально сопряжены относительно треугольника $ADE.$

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

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

Квартал представляет собой клетчатый квадрат $10× 10.$ В новогоднюю ночь внезапно впервые пошёл снег, и с тех пор каждую ночь на каждую клетку выпадало ровно по 10 см снега; снег падал только по ночам. Каждое утро дворник выбирает один ряд (строку или столбец) и сгребает весь снег оттуда на один из соседних рядов (с каждой клетки — на соседнюю по стороне). Например, он может выбрать седьмой столбец и из каждой его клетки сгрести снег в клетку слева от неё. Сгребать снег за пределы квартала нельзя. Вечером сотого дня года в город приедет инспектор и найдёт клетку, на которой лежит сугроб наибольшей высоты. Цель дворника — добиться, чтобы эта высота была минимальна. Сугроб какой высоты найдёт инспектор?

Источники: ВСОШ, ЗЭ, 2024, 9.5 (см. olympiads.mccme.ru)

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

Подсказка 1.

Хочется верить, что в оптимальном примере во всех непустых ячейках почти поровну снега.

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

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

Докажем, что после сотого утра найдется сугроб высотой не менее $112$ дм. Предположим, что такого сугроба нет. Так как дворник в сотое утро полностью сгреб снег с какого-то ряда, в десяти клетках квадрата снега нет. В каждой из оставшихся $90$ клеток, по нашему предположению, не более $111$ $3 дм$ снега, то есть всего снега не больше, чем $9990$ $3 дм .$ Однако за $100$ ночей суммарно выпало $10000$ $3 дм$ снега. Противоречие.

Покажем, как может действовать дворник, чтобы после сотого утра каждый сугроб имел высоту не более $112$ дм, то есть в каждой клетке было не более $112$ $3 дм$ снега.

Способ 1. Первые $11$ дней дворник сгребает снег из второго столбца в первый, следующие $11$ дней дворник сгребает снег из третьего столбца во второй, затем $11$ дней из четвёртого в третий, и т. д. Через $99$ дней в десятом столбце не будет снега. Посчитаем, сколько снега стало в столбце $i≤ 9$ через $99$ дней. Вечером $11(i− 1)$ -го дня в столбце номер $i$ не было снега, а в столбце $i+ 1$ в каждой клетке было по $11(i− 1)$ $дм3$ снега. На следующий вечер в столбце $i$ станет по $11(i− 1)+ 2$ $дм3$ снега в каждой клетке. Затем ещё десять дней количество снега в каждой клетке $i$ -го столбца будет увеличиваться на $2,$ а затем $11(9− i)$ дней — на $1.$ Итого, через $99$ дней в каждой клетке столбца $i$ будет по

11(i− 1)+22+ 11(9− i) =110 дм3 снега.

В сотую ночь выпадет ещё по $1$ $дм3$ в каждую клетку. А сотым утром дворник сгребёт снег из десятого столбца в девятый. Таким образом, в каждой клетке будет не более $112$ $дм3$ снега.

_________________________________________________________________________________________________________________________________________________________________________________

Способ 2. Пусть дворник сгребёт снег из $2$ -го столбца в $1$ -ый, из $3$ -го во $2$ -й, …, из $10$ -го в $9$ -ый. Тогда вечером девятого дня в первых девяти столбцах будет по $10$ дм $3$ снега в каждой клетке, а в десятом столбце снега не будем. Затем дворник проделывает аналогичный процесс в обратном порядке: из $9$ -го в $10$ -ый, из $8$ -го в $9$ -ый, …, из $2$ -го в первой. Тогда вечером $18$ -го дня в клетках последних девяти столбцов будет по $20$ $дм3$ снега, а в первом столбце не будет снега. Аналогично повторим такие сдвиги (каждый длится $9$ дней) ещё $9$ раз (всего $11$ сдвигов), и через $99$ дней получим в клетках девяти столбцов по $110$ $дм3$ снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более $112$ $дм3$ снега в каждой клетке.

Ответ:

1120 см

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

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

Высоты остроугольного треугольника $ABC,$ в котором $AB <AC,$ пересекаются в точке $H,$ а $O$ — центр описанной около него окружности $Ω.$ Отрезок $OH$ пересекает описанную около треугольника $BHC$ окружность в точке $X,$ отличной от $O$ и $H.$ Окружность, описанная около треугольника $AOX,$ пересекает меньшую дугу $AB$ окружности $Ω$ в точке $Y.$ Докажите, что прямая $XY$ делит отрезок $BC$ пополам.

Источники: ВСОШ, ЗЭ, 2024, 9.6 (см. olympiads.mccme.ru)

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

Подсказка 1

Как ортоцентр треугольника связан с серединой одной из сторон? При чём здесь центр описанной окружности?

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

Пусть $H ′$ и $X ′$ — точки, симметричные точкам $H$ и $X$ относительно середины стороны $BC$ соответственно (см. рис.). Тогда $′ ′ HXH X$ — параллелограмм. Так как

′ ∘ ∠BX C = ∠BHC = ∠BHC =180 − ∠BAC,

точки $X ′$ и $H ′$ лежат на окружности $Ω.$

$PIC$

При этом, поскольку $H′B ∥ CH ⊥AB,$ точка $H′$ диаметрально противоположна точке $A$ на этой окружности; следовательно, $AH ′$ проходит через $O.$ Вспоминая, что

XO ∥ H′X ′,

получаем

∠AYX ′ = 180∘− ∠AH ′X ′ =180∘− ∠AOX = ∠AYX,

это и означает, что точки $Y,X$ и $′ X$ лежат на одной прямой, делящей $BC$ пополам.

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

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

На доске написаны 8 различных квадратных трёхчленов; среди них нет двух, дающих в сумме нулевой многочлен. Оказалось, что если выбрать любые два трёхчлена $g1(x),g2(x)$ с доски, то оставшиеся 6 трёхчленов можно обозначить как $g3(x),$ $g4(x),$ …, $g8(x)$ так, что у всех четырех многочленов $g1(x)+ g2(x),$ $g3(x)+ g4(x),$ $g5(x)+ g6(x)$ и $g7(x)+g8(x)$ есть общий корень. Обязательно ли все трёхчлены на доске имеют общий корень?

Источники: ВСОШ, ЗЭ, 2024, 9.7 (см. olympiads.mccme.ru)

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

Построим пример 8 квадратных трёхчленов, удовлетворяющих условию задачи:

2 2 2 f1(x)= −x + 2; f2(x)= 3x − 2; f3(x)= −4x +3;

2 2 2 f4(x)=2x − 3; f5(x)= −4x + x+ 4; f6(x)= 4x +x− 4;

f (x) =− 5x2− x+ 5; f (x)= 5x2− x − 5. 7 8

Данные многочлены составлены так, чтобы их значения в точках $x =− 1,0,1$ соответствовали следующей таблице:


$x$	$f1(x)$	$f2(x)$	$f3(x)$	$f4(x)$	$f5(x)$	$f6(x)$	$f7(x)$	$f8(x)$

$−1$	1	1	$−1$	$−1$	$−1$	$−1$	1	1

0	2	$−2$	3	$−3$	4	$−4$	5	$− 5$

1	1	1	$−1$	$−1$	1	1	$−1$	$− 1$

У трёхчленов этого примера нет общего корня, его нет даже у $f1(x)$ и $f2(x).$ Осталось показать, что они удовлетворяют условию. Очевидно, никакие два из этих трёхчленов не дают в сумме ноль.

Пусть выбрана какая-то пара из этих квадратных трёхчленов. Если была выбрана пара $(f2k−1(x),f2k(x)),$ где $k= 1,$ $2,3,4,$ то все многочлены можно разбить на пары $(f1(x),f2(x));$ $(f3(x),f4(x));$ $(f5(x),f6(x));$ $(f7(x),f8(x)),$ каждая сумма этих пар имеет корень $0.$

В противном случае нетрудно убедиться, что значение суммы двух выбранных трёхчленов или в точке $x0 = −1,$ или в точке $x0 =1$ (а может быть, и в обеих сразу) равняется нулю. Выберем такое $x0.$ Оставшиеся многочлены в точке $x0$ принимают значения $−1$ и $1$ ровно по три раза, и их можно разбить на пары так, чтобы в $x0$ суммы всех четырёх пар равнялись нулю, то есть $x0$ было их общим корнем.

Ответ:

нет, не обязательно

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

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

1000 детей, среди которых нет двух одинакового роста, выстроились в шеренгу. Назовём пару различных детей $(a,b)$ хорошей, если между ними не стоит ребёнка, рост которого больше роста одного из $a$ и $b,$ но меньше роста другого. Какое наибольшее количество хороших пар могло образоваться? (Пары $(a,b)$ и $(b,a)$ считаются одной и той же парой.)

Источники: ВСОШ, ЗЭ, 2024, 9.8 (см. olympiads.mccme.ru)

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

Подсказка 1.

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

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

Докажем, что в аналогичной задаче для шеренги из $2n$ детей наибольшее возможное количество хороших пар равно $2 (n+ 1)− 3.$

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

n +1,n+ 2,...,2n, 1,2,...,n,

то все пары $(i,j),$ где $i≤ n <j,$ окажутся хорошими; таких пар всего $n2.$ Кроме этого, все пары вида $(i,i+ 1)$ также окажутся хорошими; таких пар всего $2n− 1.$ При этом пара $(n,n +1)$ учтена дважды, так что общее количество хороших пар равно

2 2 n +(2n− 1)− 1 =(n+ 1)− 3.

Осталось доказать, что хороших пар не может быть больше, чем $(n+ 1)2− 3.$ Сделаем это индукцией по $n.$ При $n =1$ утверждение тривиально, ибо есть всего одна пара детей.

Пусть теперь $n> 1.$ Рассмотрим произвольную шеренгу и выберем в ней хорошую пару $(a,b),$ в которой $|a − b|$ — наибольшее; пусть для определённости $a< b,$ и ребёнок $a$ стоит левее, чем $b.$ Назовём ребёнка $c$ прекрасным, если он образует хорошие пары как с $a,$ так и с $b.$

______________________________________________________________________________________________________________________________________________________

Лемма. Существует не больше двух прекрасных детей.

Доказательство. Если $c$ прекрасен, то по выбору пары $(a,b)$ имеем $c− a ≤b− a$ и $b− c≤ b− a,$ откуда $a< c<b.$ Такой ребёнок $c$ не может стоять между $a$ и $b,$ иначе пара $(a,b)$ не была бы хорошей; значит, любой прекрасный ребёнок стоит либо слева от $a,$ либо справа от $b.$

Предположим, что есть два прекрасных ребёнка $c1 < c2,$ стоящих левее $a;$ тогда

a< c1 <c2 < b.

Ребёнок $c 1$ не может стоять между $a$ и $c, 2$ иначе пара $(a,c) 2$ не хорошая; поэтому $c 1$ стоит левее $c. 2$ Но тогда $c 2$ стоит между $c 1$ и $b,$ и пара $(c,b) 1$ — не хорошая, что невозможно. Это противоречие показывает, что левее $a$ стоит не более одного прекрасного ребёнка. Аналогично, не более одного стоит правее $b,$ откуда и следует доказываемое утверждение.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь несложно совершить переход индукции. Выкинув $a$ и $b,$ мы получим, что все хорошие пары, не содержащие $a$ и $b,$ остались хорошими; по предположению индукции, их не больше, чем $n2 − 3.$ Осталось оценить количество хороших пар, содержащих $a$ или $b.$ Это пара $(a,b),$ пары $(a,c)$ и $(b,c)$ для любого прекрасного ребёнка $c,$ и максимум по одной из пар $(a,c)$ и $(b,c)$ для остальных детей $c.$ Всего получаем не более чем

1+(2n− 2)+2= 2n+ 1 пар,

откуда общее количество хороших пар не превосходит

2 2 (n − 3)+ (2n +1)= (n +1) − 3,

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

Ответ:

$5012− 3$

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

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

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

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

Рассмотрим все 100-значные числа, делящиеся на 19.

Докажите, что количество таких чисел, не содержащих цифр 4,5 и 6, равно количеству таких чисел, не содержащих цифр 1, 4 и 7.

Источники: Финал ВсОШ - 2023, 9.6, автор И.А. Ефремов (см. olympiads.mccme.ru)

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

Подсказка 1

В задаче просят доказать, что какие-то 2 множества равны. Попробуйте сделать биекцию между элементами множества.

Подсказка 2

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

Подсказка 3

Предлагается операцией умножить цифру на что-нибудь. При такой операции делимость на 19 сохранится(поймите это). Как сделать в обратную сторону?

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

Каждому остатку $a$ от деления на 19 сопоставим остаток $b(a)$ такой, что $b(a) ≡ 3a. 19$

Заметим, что остаткам $0,1,2,3,7,8,9$ сопоставлены остатки $0,3,6,9,2,5,8$ соответственно. Более того, по остатку $b$ восстанавливается остаток $a =a(b) ≡19 −6b$ такой, что $a(b(a)) ≡19− 18a ≡19a$ и $b(a(b))=b$ (из аналогичных соображений).

Обозначим теперь через $𝒜$ множество чисел из условия, не содержащих цифр $4,5,6$ , а через $ℬ$ — множество таких чисел, не содержащих $1,4,7$ . Каждому числу $--------- A= a99a98...a0 ∈ 𝒜$ сопоставим число $---------------- B = b(a99)b(a98)...b(a0)$ . Заметим, что $b(ai)$ — цифра (причём $b(a99)⁄= 0$ ), так что получилось 100 -значное число. Кроме того,

99 B = b0+ 10b1+ ...+(10 b99 ≡ ) ≡ 3a0+ 10a1+...+1099a99 = 3A (mod19),

так что $B$ делится на 19 и $B ∈ ℬ$ . Поскольку разным числам из $𝒜$ соответствуют разные числа из $ℬ$ , количество чисел в $ℬ$ не меньше, чем в $𝒜$ .

Наконец, каждому числу $--------- B =b99b98...b0 ∈ℬ$ соответствует число $---------------- A= a(b99)a(b98)...a(b0)$ , которое по аналогичным причинам лежит в $𝒜$ . Отсюда следует, что количества чисел в $𝒜$ и $ℬ$ равны.

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

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

Даны два приведённых квадратных трёхчлена $f(x)$ и $g(x);$ известно, что трёхчлены $f(x)$ , $g(x)$ и $f(x)+g(x)$ имеют по два корня. Оказалось, что разность корней трёхчлена $f(x)$ равна разности корней трёхчлена $g(x).$ Докажите, что разность корней трёхчлена $f(x)+g(x)$ не больше этих разностей. (В каждой разности из большего корня вычитается меньший.)

Источники: ВСОШ, ЗЭ, 2023, 9.1 (см. olympiads.mccme.ru)

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

Подсказка 1:

Любой приведённый квадратный трёхчлен с двумя корнями можно записать в виде (x – p)² – q² для некоторых p, q. Чему равна разность его корней и наименьшее значение в этих терминах?

Подсказка 2:

Разность равна 2q, а наименьшее значение –q². Чтобы сделать такие же рассуждения с f(x) + g(x), стоит рассмотреть трёхчлен (f(x) + g(x)) / 2. Он приведённый и имеет те же корни, что и f(x) + g(x).

Подсказка 3:

Попробуйте сначала оценить минимальное значение (f(x) + g(x)) / 2, а потом перейти к разности корней.

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

Первое решение. Заметим, что разность корней приведённого квадратного трёхчлена $x2 +bx+ c$ равна корню из его дискриминанта, то есть $√-2--- b − 4c.$

Пусть два данных трёхчлена — это

2 f(x)=x + b1x+c1

2 g(x)= x + b2x+ c2.

Согласно условию, у них общий дискриминант

D= b2− 4c = b2− 4c . 1 1 2 2

Вместо суммы трёхчленов удобно рассмотреть их полусумму — она тоже является приведённым квадратным трёхчленом. Квадрат разности его корней (то есть дискриминант) равен:

(b1+-b2)2 b21-+b22 (b1−-b2 )2 2 − 2(c1 +c2)= 2 − 2(c1+ c2)− 2 .

Значит, он не больше, чем

2 2 b1+-b2− 2(c1+ c2)= D-+ D-= D. 2 2 2

Отсюда и следует, что разность корней полусуммы не больше, чем $√D,-$ то есть разность корней каждого из данных трёхчленов.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Заметим, что любой приведённый квадратный трёхчлен с двумя корнями имеет вид

(x − p)2− q2

при $q ≥ 0.$ При этом разность его корней равна $2q,$ а его наименьшее значение равно $− q2.$

Теперь условие означает, что два данных трёхчлена имеют равные наименьшие значения $− q2.$ Наименьшее значение их полусуммы, очевидно, не меньше $− q2$ (оно является полусуммой каких-то значений исходных трёхчленов), то есть оно равно $− r2$ при $0≤ r≤ q.$ Поэтому и разность корней полусуммы, то есть $2r,$ не превосходит $2q.$

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

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

Изначально в строку выписывают 250 букв — 125 букв A и 125 букв B в некотором порядке. Затем за одну операцию можно взять любой кусок из нескольких подряд стоящих букв, среди которых поровну букв A и B, и переставить буквы в этом куске в обратном порядке, поменяв в этом куске все буквы A на буквы B и буквы B на буквы A. (Например, из строки ABABBAB можно одной операцией получить строку ABBAABAB.) Можно ли выписать исходную строку и совершить несколько операций так, чтобы в результате на доске оказалась та же строка, буквы которой записаны в обратном порядке?

Источники: ВСОШ, ЗЭ, 2023, 9.2 (см. olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте найти какой-нибудь инвариант для операции из условия.

Подсказка 2:

Можно посмотреть на количество букв, обладающих каким-либо свойством.

Подсказка 3:

Обратите внимание на количество букв А на нечётных позициях. Как оно меняется при проведении операции?

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

Первое решение. Пронумеруем позиции в строке слева направо числами от 1 до 250. Пусть в исходной строке $x$ букв A стоят на нечётных местах (т. е. местах с нечётными номерами). Покажем, что в полученных строках это количество не изменится.

Действительно, пусть для некоторой операции выбран кусок, в котором по $y$ букв A и B, причём $t$ из этих букв A стоят на нечётных местах. Тогда на чётных местах в куске стоят $y− t$ букв A и, следовательно, $y− (y− t)= t$ букв B. После операции именно из этих $t$ букв B возникнут буквы A, стоящие на нечётных местах куска — значит, количество таких букв A не поменяется.

Итак, в любой полученной строке будет ровно $x$ букв A на нечётных местах. Однако, если строка развернётся задом наперёд, то на нечётных местах должны оказаться ровно те буквы, которые раньше были на чётных местах, а там было ровно $125− x$ букв A. Поскольку $125− x⁄= x,$ требуемое невозможно.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. В строке всего $1252$ пар, состоящих из буквы A и буквы B. Назовём такую пару левой, если в ней A стоит левее B, и правой иначе. Покажем, что при операции количество левых пар не изменяется. Из этого будет следовать невозможность требуемого, ибо при развороте строки все пары меняют тип, а значит, количество левых пар меняет чётность.

Рассмотрим одну операцию с куском длины $2y.$ При этой операции пары из букв, не лежащих в куске, сохраняют свой тип. Далее, для каждой буквы вне куска было ровно $y$ пар, содержащих её и букву из куска; столько же таких пар осталось, и все эти пары были и стали одного и того же типа.

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

Ответ:

нельзя

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

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

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

Источники: ВСОШ, ЗЭ, 2023, 9.3 (см. olympiads.mccme.ru)

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

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

Если число $n$ синее, то числа $n− 1$ и $n+ 1$ обязаны быть красными. Тогда их произведение $2 (n − 1)(n +1)= n − 1$ должно быть синим, а значит, $2 n$ должно быть красным.

Возьмём любое синее число $k> 1001.$ Тогда $2 k$ красное. Если $3 k$ синее, то $6 32 k =(k )$ красное. Но $6 2 4 k = k ⋅k,$ где $2 k$ и $6 k$ красные, значит, $4 k$ должно быть синим. Тогда $8 42 k =(k )$ красное, но $8 2 6 k = k ⋅k$ — произведение красных чисел, что невозможно.

Если же $3 k$ красное, то $5 2 3 k =k ⋅k$ синее, а $10 52 k =(k )$ красное. Так как

k10 = k2⋅k8 = k3 ⋅k7,

где $2 k$ и $3 k$ красные, то $7 k$ и $8 k$ должны быть синими. Тогда $14 7 2 k = (k)$ и $16 82 k = (k)$ красные, но $16 2 14 k =k ⋅k$ — произведение красных чисел, что приводит к противоречию.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что такая раскраска существует. Если $a$ и $b$ различные красные числа, то $ab$ синее, а $ab+ 1$ красное.