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

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

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

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

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

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

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

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

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

ПитерГор 2015

ПитерГор 2016

ПитерГор 2017

ПитерГор 2018

ПитерГор 2019

ПитерГор 2020

ПитерГор 2021

ПитерГор 2022

ПитерГор 2023

ПитерГор 2024

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

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

Задача 1#71907

Дан многочлен $f(x)$ степени $2000.$ При этом у многочлена $f(x2− 1)$ ровно $3400$ корней, а у многочлена $f(1− x2)$ ровно $2700$ корней. Докажите, что расстояние между какими-то двумя корнями $f(x)$ меньше $0,002.$

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

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

Подсказка 1

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

Подсказка 2

Несложно заметить, что х²-1≥-1. Значит, не может возникнуть много корней f(x), которые не меньше, чем -1, ведь у f(х²-1) 3400 корней.

Подсказка 3

Аналогично, 1-х²≤1. Значит, не может возникнуть много корней f(x), которые не больше, чем 1. Тогда на отрезке [-1, 1] корней достаточно много.

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

Пусть $f(x)$ имеет корни $c,...,c, 1 k$ где $k ≤2000.$ Так как многочлен $f(x2− 1)$ имеет ровно $3400$ корней, а уравнение $2 x − 1= ci$ имеет не более двух решений, то не более чем $k− 1700$ корней $f$ лежат за пределами $[−1,∞)$ — множества значений $2 x − 1.$ Аналогично, так как $( 2) f 1− x$ имеет ровно $2700$ корней, а уравнение $2 1− x = ci$ — не более двух решений, то не более чем $k− 1350$ корней $f$ лежат за пределами $(−∞, 1]$ — множества значений $2 1 − x .$ Значит, не менее

k− (k − 1350)− (k− 1700)= 3050− k≥ 1050

корней $f(x)$ лежат на $[−1,1],$ откуда следует, что среди них есть два на расстоянии менее $0,002.$

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

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

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

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

Ответ: нет

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

Задача 3#71909

В начале игры у Малыша и Карлсона есть один кусок шоколадки в виде квадрата $2019× 2019$ клеточек. Каждым ходом Малыш делит какой-нибудь кусок по клеточкам на три прямоугольных куска, а Карлсон съедает один из этих трёх кусков по своему выбору. Игра заканчивается, когда сделать очередной ход невозможно. Если всего было сделано чётное число ходов — побеждает Малыш, если нечётное — Карлсон. Кто выигрывает при правильной игре?

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

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

Назовем кусок шоколадки $большим,$ если его можно разрезать, и $малым,$ если нельзя. Изначально есть только один большой кусок, а в конце игры их $0.$ Карлсон может играть так, чтобы четность количества больших кусков после его хода обязательно менялась: один большой кусок уничтожается ходом Малыша, после чего появляется от $0$ до $3$ новых больших кусков. Если количество новых больших кусков нечетно, то один точно есть и Карлсон его съест. Если же количество больших кусков четно, то есть хотя бы один малый и Карлсон съест именно малый кусок. Итак, число больших кусков после каждой пары полуходов меняет четность, а по окончании игры чётность чисел больших кусков должна измениться, значит, будет сделано нечётное количество ходов, т.е. Карлсон выиграет.

Ответ: Карлсон

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

Задача 4#71910

Неравнобедренный треугольник $ABC$ периметра $12$ вписан в окружность $ω.$ Точки $P$ и $Q$ — середины дуг $ABC$ и $ACB$ соответственно. Касательная, проведенная к окружности $ω$ в точке $A,$ пересекает луч $PQ$ в точке $R.$ Оказалось, что середина отрезка $AR$ лежит на прямой $BC.$ Найдите длину отрезка $BC.$

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

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

Пусть $I ,I ,I A B C$ — центры вневписанных окружностей треугольника $ABC,$ касающихся сторон $BC,CA$ и $AB$ соответственно. Тогда прямые $AIA,BIB,CIC$ — биссектрисы треугольника $ABC$ , а прямые $IBIC,ICIA,IAIB$ — его внешние биссектрисы. Следовательно, точки $A,B,C$ будут основаниями высот треугольника $IAIBIC,$ а окружность $ω$ — его окружностью девяти точек. Тогда точки $P$ является отличной от $B$ точкой пересечения $IAIC$ с $ω.$ Следовательно, $P$ — середина $IAIC.$ Аналогично, $Q$ — середина $IAIB.$ Таким образом, $PQ$ — средняя линия треугольника $IAIBIC.$

Обозначим через $K$ и $L$ соответственно основания внешней и внутренней биссектрис угла $A$ треугольника $ABC$ и через $M$ — точку пересечения прямых $AR$ и $BC.$ По условию мы знаем, что $AM = MR.$

$PIC$

Точка $M$ лежит на луче $BC$ , поскольку $R$ — на $PQ,$ так что

∠MAL = ∠MAC + ∠CAL = ∠ABC + ∠LAB =∠ALM

Тогда $AM = ML,$ а поскольку треугольник $AKL$ прямоугольный, то и $AM =MK.$

Следовательно, $ALRK$ — прямоугольник и $LR ∥IBIC.$ Мы получаем, что прямые $PQ$ и $LR$ параллельны $IBIC$ и имеют общую точку $R.$ Тогда эти прямые совпадают. Это означает, что точка $L$ лежит на средней линии треугольника $IAIBIC$ и, следовательно, делит пополам отрезок $AIA.$

Далее, применив свойство внешней биссектрисы к треугольникам $ABL$ и $ACL$ , получим

AB-= AC-= AIA-= 2. BL CL IAL

Тогда $AB + AC = 2BC$ и, следовательно, $BC = 4.$

Ответ:

$4$

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

Задача 5#71911

У барона Мюнхгаузена есть набор гирь $1000$ различных целых весов, по $21000$ гирь каждого веса. Барон утверждает, что если взять по одной гире каждого веса, то общий вес этих $1000$ гирь будет меньше $1010 2 ,$ причём этот вес невозможно набрать гирями из этого набора другим способом. Могут ли слова барона оказаться правдой?

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

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

Пусть $k =1000.$ Докажем, что подойдет набор гирь с весами

k k−1 k k−2 k 0 ak−1 =2 − 2 ,ak−2 = 2 − 2 ,...,a0 = 2 − 2 .

Если взять по одной гире каждого веса, сумма весов равна

k k−1 1 0 k 2010 s =k ⋅2 − 2 − ⋅⋅⋅− 2 − 2 = (k − 1)⋅2 +1 <2 .

Заметим, что

s≡ 1 (mod 2k),a≡ −2i (mod 2k) i

Тогда любой способ набрать этими гирями суммарный вес $s$ повзоляет представить число $s,$ дающее остаток $1$ по модулю $2k,$ как сумму нескольких слагаемых с остатком $− 2i.$ Следовательно, можно набрать некторое число $t,$ сравнимое с $2k− 1$ по модулю $2k,$ как сумму нескольких слагаемых вида $2i.$

Будем в такой сумме заменять две одинаковые степени двойки на одну более крупную, пока это возможно. В результате получится, что $2k− 1,$ набрано как сумма различных степеней двойки. Но это можно сделать единственным способом: сложив все меньшие степени двойки, этот соответствует сумме

a + a +⋅⋅⋅+ a k−1 k−2 0

Остается лишь добавить, что замена одной степени двойки на две меньших (обратная приведённым операциям) дает замену $ai$ на $2ai− 1,$ что увеличивает сумму. Значит, наш способ единственен.

Ответ: да

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

Задача 6#71912

Пусть между городами $A,B,C$ и $D$ есть дороги $AB$ и $CD,$ но нет дорог $BC$ и $AD.$ Назовем пеpecтройкой замену пары дорог $AB$ и $CD$ на пару дорог $BC$ и $AD.$ Изначально в стране было несколько городов, некоторые пары городов были соединены дорогами, причем из каждого города выходило по $100$ дорог. Министр нарисовал новую схему дорог, в которой из каждого города по-прежнему выходит $100$ дорог. Известно, что как в старой, так и в новой схемах никакие два города не соединены более, чем одной дорогой. Докажите, что новую схему можно получить из старой с помощью нескольких перестроек.

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

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

Рассмотрим множество $M,$ состоящее из всех возможных $100$ -регулярных(степени всех вершин в графе равны 100) графов на данном множестве вершин $V$ (наши две схемы дорог — среди них). Докажем что любые два графа из $M$ можно перевести друг друга серией перестроек. Для двух графов $′ G,G ∈ M$ пусть $′ F(G,G )$ - множество необщих рёбер этих графов, а $′ ′ f(G,G )= |F (G,G )|$ . Очевидно, что число $′ f (G,G )$ всегда четно, и в множестве $′ F (G,G )$ поровну рёбер из $G$ и $′ G .$

Предположим, что существуют пары непереводимых друг в друга перестройками графов в $M.$ Рассмотрим такую прару графов $(A,B)$ с минимальным $f(A,B).$ Граф $H = (V,F (A,B ))$ имеет в каждой вершине поровну рёбер из $A$ и из $B$ . Следовательно, в $H$ существует чередующийся цикл(в котором рёбра $A$ и $B$ чередуются). Рассмотрим цикл $Z =a1a2...a2k$ с минимальным числом вершин(это не обязательно простой цикл, вершины в нем могут повторяться). Первая наша цель - найти на этом цикле четыре последовательные различные вершины. В самом деле, пусть среди $a1,a2,a3,a4$ есть совпадающие. Очевидно, возможно лишь совпадение $a1 =a4$ . Так как рёбра цикла не повторяются, тогда $a2 ⁄= a5$ и в качестве искомой четверки подойдет $a2,a3,a4,a5.$

Итак, не умаляя общности будем считать, что все вершины $a1,a2,a3,a4$ различны, причем $a1a2,a3a4 ∈$ $E(A)$ и $a2a3 ∈ E(B).$ Рассмотрим три случая.

(а) $a1a4 ∈E (B ).$ Тогда проведем перестройку $a1a2a3a4$ в графе $B$ (это возможно, так как $a1a2,a3a4∈∕E(B)$ ) и получим граф $C$ с $f(A,C)= f(A,B)− 2.$ По предположению, $C$ можно получить из $A$ перестройками, значит, можно получить и $B.$

(b) $a1a4 ∈ E(A )∖E(B)$ . Тогда $a1a4a5...a2k$ — чередующийся цикл, меньший чем $Z,$ противоречие.

(c) $a1a4 ∕∈E (A)∪ E(B).$ Тогда проведем перестройку $a1a2a3a4$ в графе $A$ (это возможно, так как $a2a3,a4a1 ∕∈$ $E (A))$ и получим граф $C$ с $f(B,C )=f(A,B)− 2.$ По предположению, $C$ можно получить из $B$ перестройками, значит, можно получить и $A.$

Курсы

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

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

Задача 7#71913

Треугольник $ABC$ вписан в окружность $ω$ с центром $O.$ Прямая $AO$ вторично пересекает окружность $ω$ в точке $A′.$ Точки $MB$ и $MC$ — середины сторон $AC$ и $AB$ соответственно. Прямые $′ A MB$ и $′ AMC$ пересекают окружность $ω$ вторично в точках $′ B$ и $′ C,$ а также пересекают сторону $BC$ в точках $DB$ и $DC$ соответственно. Описанные окружности треугольников $′ CDBB$ и $′ BDCC$ пересекаются в точках $P$ и $Q.$ Докажите, что точки $O,P$ и $Q$ лежат на одной прямой.

$PIC$

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

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

Решение 1.

Сделаем поворот с центром в точке $O,$ переводящий $′ B$ в $A,$ и обозначим образ точки $C$ при этом повороте через $′′ B .$ Пусть $X$ — точка пересечения прямых $′ AA$ и $′′ BB .$ Из равенства дуг $′′ AB$ и $′ B C$ легко следует равенство углов $′′ ′ ∠AXB =∠B DBC.$ Тогда описанная окружность треугольника $′ CDBB$ при этом повороте переходит в описанную окружность треугольника $′′ AXB .$ При этом точка $O,$ очевидно, будет иметь одинаковые степени относительно этих двух окружностей.

Аналогично, рассмотрев поворот с центром в $O,$ переводящий $′ C$ в $A$ и обозначив образ точки $B$ через $′′ C$ и точку пересечения $′ AA$ с $′′ CC$ через $Y,$ мы получим, что точка $O$ имеет одинаковые степени относительно описанных окружностей треугольников $′ BDCC$ и $′′ AYC .$

$PIC$

Таким образом, вместо утверждения “точка $O$ лежит на прямой $P Q$ ”, эквивалентного тому, что точка $O$ имеет одинаковые степени относительно описанных окружностей треугольников $CDBB ′$ и $BDCC ′,$ достаточно доказать, что точка $O$ имеет одинаковые степени относительно описанных окружностей треугольников $AXB ′′$ и $AY C′′,$ т.е. что точки $X$ и $Y$ совпадают.

Заметим, что медиана треугольника $AA ′C$ лежит на прямой $A ′B′$ и $∠(AA′,A′B ′)= ∠(B′′A′,A′C ).$ Значит, $A′B ′′$ — симедиана треугольника $AA′C$ и тогда четырехугольник $AA ′CB ′′$ гармонический. Аналогично, четырехугольник $AA′BC′′$ также гармонический. Но тогда обозначив через $S$ точку пересечения прямых $AA′$ и $BC,$ мы получим равенство двойных отношений

(A,S,A′,X)= (A,C,A′,B′′)= −1 =(A,B,A′,C ′′)= (A,S,A′,Y ),

откуда $X = Y.$

Решение 2.

Пусть прямая $C ′O$ пересекает описанную окружность треугольника $BDCC ′$ в точках $C′$ и $K,$ а прямая $B ′O$ пересекает описанную окружность треугольника $CDBB ′$ в точках $B ′$ и $L.$ Тогда

∠(C′K,KB )= ∠(MCDC, DCB)

Кроме того,

′ ′ ′ ′ ′ ′ ∠(DCB,BK )= ∠(DCC ,C K )=∠(AA ,AC )= ∠(AB,BC ),

следовательно, $∠(DCB,BMC ) =∠(KB,BC ′).$ Значит треугольники $BC′K$ и $BMCDC$ подобны и одинаково ориентированы.

Из этого, учитывая, что треугольники $MCBC ′$ и $MCA ′A$ также подобны, получаем

C′K = MCDC-⋅C′D = MCDC-⋅AA′- BMC A′MC

Аналогично

′ MBDB ⋅AA′ B L= ---AMB----

Из этих равенств и параллельности $MBMC$ и $BC$ следует, что $C′K =B ′L.$

$PIC$

Докажем, что точка $O$ лежит на луче $C ′K$ (и, аналогично, на луче $B′L$ ). Для этого сначала заметим, что хорда $A ′C′$ окружности $ω$ пересекает во внутренних точках стороны $BC$ и $AB,$ следовательно, один конец хорды лежит на дуге $BC,$ а другой — на дуге $AB$ (здесь и далее рассматриваются дуги с концами в двух вершинах треугольника $ABC,$ не содержащие третью вершину). Аналогично один из концов хорды $A′B′$ лежит на дуге $BC,$ а другой — на дуге $CA.$ Это возможно, только если точки $A′,B ′$ и $C ′$ лежат на дугах $BC,CA$ и $AB$ соответственно. Из этого следует, что углы $B$ и $C$ треугольника $ABC$ острые, а также что точки $A′,DC,MC,C ′$ лежат на прямой именно в таком порядке. Далее заметим, что треугольник $BC ′K$ ориентирован так же, как треугольник $BMCDC,$ по доказанному выше; треугольник $BMCDC$ ориентирован так же, как треугольник $BC ′C,$ поскольку точки $C ′$ и $C$ лежат на продолжениях сторон $DCMC$ и $BDC$ за точки $MC$ и $DC$ соответственно; наконец, треугольник $BC ′C$ ориентирован так же, как треугольник $BC′O,$ поскольку $∠C ′CB < ∠ACB < 90∘.$ Итак, треугольники $BC ′K$ и $BC′O$ ориентированы одинаково, а это и означает, что точка $O$ лежит на луче $C′K.$ По доказанному выше имеем