Тема ПитерГор - задачи по годам

ПитерГор 2019

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

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

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

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

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

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

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

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

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

Подсказка 1

Предположим, что могло! Значит были изначально какие-то три числа (a < b < c), превратившиеся в одинаковые. Что можно сказать про НОД, которые к ним прибавили?

Подсказка 2

Поняли, что добавленный к a НОД — делитель c - b! Какую оценку тогда можно сделать?

Подсказка 3

Получим, что a + НОД < c!

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

Предположим, что числа $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)

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

Подсказка 1

У нас есть два типа кусков – те, которые Малыш еще сможет разрезать (назовем их большими), и те, которые разрезать уже нельзя (назовём их малыми). Сколько у нас есть больших кусков в начале и конце игры?
—-
Подсказка 2
Изначально есть 1 большой кусок, в самом конце их ноль. Подумайте, как может меняться четность больших кусков в ходе игры
—-
Подсказка 3
Видим, что четность количества больших кусков в итоге изменилась, может ли Карлсон сделать так, чтобы после его хода эта четность менялась всегда? Если удастся придумать такой алгоритм, то Карлсон точно сможет выиграть!

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

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

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

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

Задача 4#71910

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

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

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

Подсказка 1

Начнём, как всегда, с построения аккуратного чертежа. Нам нужно узнать какую-то связь между сторонами треугольника △ABC, чтобы имея периметр, смочь найти длину ВС. В работе с отношениями нам часто помогают биссектрисы (не только внутренние) углов треугольника, как мы можем тут это применить?

Подсказка 2

Вероятно, вы не раз уже встречали свойство об описанной окружности треугольника △ABC, которая также является окружностью 9 точек для другого треугольника. Постройте его! Чем в таком случае является PQ?

Подсказка 3

Чем является точка пересечения PQ с высотой вновь построенного треугольника, основание которой лежит в вершине А? Проведите биссектрису в △ВАС и попробуйте доказать, что эта точка и есть её основание.

Подсказка 4

Посмотрим для этого на четырёхугольник сбоку: проведите дополнительно внешнюю биссектрису △ВАС. Что за фигура выходит? Это не просто параллелограмм!

Подсказка 5

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

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

Пусть $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)

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

Подсказка 1

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

Подсказка 2

Рассмотрите в качестве кандидатов на веса гирек разности соседних степеней двоек. Также можно заметить, что достаточно брать всего по одной гирьке данных весов.

Подсказка 3

А почему же наш способ выбрать вес будет единственным? Хммм, ах да, можно заметить, что мы замена одной степени двойки на 2 меньших увеличит сумму.

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

Пусть $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)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Рассмотрим всевозможные графы из условия (со степенями вершин, равными 100), пусть они составляют множество M. Все эти графы построены на множестве V. Так как мы хотим следить за несовпадениями, то полезно будет следующие обозначения: F(G, G') — множество необщих рёбер у графов G и G' из множества M, f(G, G') = |F(G, G')| — их количество. Какие первые замечания можно сделать про функции F(G, G') и f(G, G'), учитывая, что в любом графе из M степень каждой вершины равна 100?

Подсказка 4

Во-первых, в F(G, G') одинаковое количество рёбер из G и G'. Во-вторых, чуть менее простой факт: f(G, G') — чётно (осознайте это). Вернёмся к нашему предположению. Пусть существует два непереводимых друг в друга графа A и B. Что нужно ещё сказать про эти графы, чтоб получить противоречие при перестроении?

Подсказка 5

Воспользоваться принципом крайнего! Пусть А и B — такая пары непереводимых, что f(A,B) — минимально. Хотим переводить один граф в другой, но пока что это отдельные графы и с ними не прям удобно работать. Что можно сделать?

Подсказка 5:

Рассмотрим граф H = (V, F(A,B)), рёбра из А в H — красные, из B — синие. Вспомним условие, мы можем менять пару "противоположных сторон квадратика" (набора из 4 вершин) на другую пару. Хотим, чтоб все синие рёбра наложились на красные. Какую самую естественную конструкцию в таком случае мы хотим найти в H?

Подсказка 6

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

Подсказка 7

В Н точно есть цикл с чередованием. Рассмотрим такой цикл (понятно, что он чётной длины) Z = a₁a₂...a₂ₙ вновь с применением принципа крайнего, то есть Z минимальной длины. Самостоятельно докажите, что в нём всегда найдётся 4 подряд идущих различных вершины. Не забывайте про суть графа H и F(A, B).

Подсказка 8

Не умаляя общности, это a₁, a₂, a₃, a₄. Пусть рёбра a₁-a₂, a₃-a₄ — красные, a₂-a₃ — синие. Осталось перебрать несколько случаев, относительно ребра a₁-a₄.

Подсказка 9

Все случаи легко привести к противоречию, если вспомнить про то, что мы использовали принцип крайнего. У вас всё получится! Успехов!

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

Рассмотрим множество $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.

Подсказка 2

Что же делать теперь? Не очень понятно как доказывать, что (⋅)O лежит на прямой PQ. А что можно сделать, когда есть точка и много окружностей? Правильно, можно рассмотреть степень точки O относительно разных окружностей.

Подсказка 3

Ну и послежний трюк в этой задаче. Для того, чтобы доказательство было красивым, надо внимательно посмотреть на рисунок и что-то заметить... И правда ведь на рисунке присутствуют сразу 2 гармонических четырёхугольника!!!

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

Решение 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.$ По доказанному выше имеем