ПитерГор (Санкт-Петербургская олимпиада) —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
ПитерГор (Санкт-Петербургская олимпиада)

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

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

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

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

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

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

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

Отбор Питергора

Алгебраические текстовые задачи на Питергоре

Квадратные трёхчлены на Питергоре

Комбинаторика на Питергоре

Планиметрия на Питергоре

Стереометрия на Питергоре

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

Многочлены на Питергоре

Уравнения, неравенства и системы на Питергоре

Последовательности и прогрессии на Питергоре

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

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

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

Задача 1#82683

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Ответ: 1

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

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

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

Задача 2#82682

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

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

Подсказка 1

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

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

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

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

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

Задача 3#82681

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

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

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

∠ABD = ∠ABC +∠CBD > ∠ABC

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

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

∠ABD = ∠CBA +∠ABD > ∠ABC

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

Задача 4#82679

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка З

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

Подсказка 4

Чтобы показать равенство Т₁К и КZ₁:

Подсказка 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.$

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

Задача 6#82677

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

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

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

Подсказка 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), но для всех меньших мы доказали. Что осталось написать по этой задаче? Является ли это полным решением?

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

Возьмём число $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

Курсы

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

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

Задача 7#82676

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

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

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

Подсказка 1

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

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

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


1	2	3	…	1

2	3	1	…	2

3	1	2	…	3

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

1	2	3	…	1

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

Ответ: Можно

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

Задача 8#70486

Есть $2n$ карточек, на каждой написано число от $1$ до $n$ (каждое — ровно на двух карточках). Карточки лежат на столе числами вниз. Набор из $n$ карточек называется хорошим, если на них каждое число встречается по одному разу. Барон Мюнхаузен утверждает, что он может указать $80$ наборов по $n$ карточек, из которых хотя бы один заведомо окажется хорошим. При каком наибольшем $n$ слова барона могут быть правдой?

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

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

Подсказка 1

Задача непростая, поэтому давайте сначала "причёсывать" её, наблюдать какие-то интересные свойства. Например, если у нас набор из n карточек хороший, то оставшиеся n карточек тоже образуют хороший набор(пусть дополнительный набор). Понятно, что слишком большое n взять не получится. Попробуйте изучить, перебрать какие-то n. Понятно, что n=10, наверное, уже слишком много, а n=5, n=6 маловато.

Подсказка 2

Надеюсь, вы порешали сами задачку, и догадываетесь какое примерно максимальное n, а может у вас получилось построить пример для него. При n = 8 и больше уже указать такой набор будет нельзя, т.е. ответ к задаче n = 7. Понятно, что если докажем для 8, то и для больших тоже. Наша цель — предъявить такой способ разметки карточек, чтобы ни один из 80 выбранных наборов не оказался хорошим. Давайте в наших 80 произвольных наборах рассмотрим какую-то карточку A. Можем ли мы сделать так, чтобы она была во всех наборах?

Подсказка 3

Да, меняя наш набор на дополнительный, мы добьёмся присутствия A во всех наборах. А дальше нам глобально нужно убрать плохие наборы, чтобы остались хорошие, но в конце концов, продолжая так делать, всё равно останется плохой набор. Мы докажем, что всегда можно так занумеровать карточки, что все 80 наборов окажутся плохими. Давайте этим и займёмся. Попробуйте понять с помощью принципа Дирихле, хотя бы сколько ещё других карточек B у нас будет? Тогда сколько наборов у нас может оказаться плохими, если цифра на B будет такая же, как у A?

Подсказка 4

Давайте просто аккуратно посчитаем. Оставшихся карточек всего у нас 80 * 7 = 560. А оставшихся карточек, кроме A, у нас 15. Отсюда по принципу Дирихле у нас будет хотя бы 38 карточек B(обозначение из предыдущей подсказки). И вот теперь у нас есть хотя бы 38 наборов с карточками A и B! Тогда пусть на них и оказалось какое-то число 8, теперь все эти наборы плохие. У нас остались 14 карточек(A и B мы убрали) и не больше 42 наборов, где в теории ещё может быть хороший. А теперь аналогично делаем дальше! Попробуйте проделать эти же шаги самостоятельно(их не так много, поэтому лучше, чтобы избежать путаницы и ошибок, сделать всё). Теперь, дойдя до конца процесса, поймите, почему мы доказали оценку? Сколько наборов и карточек остаётся на последнем шаге?

Подсказка 6

Ага, на последнем шаге должен был остаться 1 набор и 4 карточки. Тогда, написав на двух из них число 2, а на двух других число 1, мы победим(даже с запасом)! Мы доказали то, что было написано в 3 подсказке. Осталось разобраться с примером. Мы увидели, что 80 карточек хватает с запасом, поэтому, скорее всего, достаточно брать меньше наборов и среди них будет один хороший. Подумайте, сколько будет достаточно? Это число явно выражается через n.

Подсказка 7

Покажем, что для 2n карточек, мы можем выбрать 2^(n-1) наборов, среди которых точно есть один хороший. Это можно сделать по индукции. База понятна. Пусть на столе лежит 2n+2 карточки, а для 2n мы доказали. Попробуем взять 2 произвольные карточки. Какие варианты тогда возможны? Нужно рассмотреть их и применить предположение индукции!

Подсказка 8

Ага, возможны два варианта: мы вытащили карточки с одинаковыми числами или с различными. Первый случай совсем несложный и делается почти сразу. А во втором попробуйте объединить оставшиеся непарные карточки мысленно в одну и снова применить предположение индукции. Повозитесь со всем этим и у вас получится! Ну а исходную задачу мы тем самым решаем, так как 64<80. Победа!

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

Заметим, что если набор из $n$ карточек хороший, то набор из оставшихся $n$ карточек тоже хороший(назовём его дополнительным набором).

Покажем, что для $n≥ 8$ нельзя так указать $80$ наборов, чтобы хотя бы один из них оказался хорошим. Для этого достаточно убедиться в том, что при $n = 8$ нельзя указать такие $80$ наборов. Поскольку, барон выбирает наборы карточек, не зная, какие числа написаны на этих карточках снизу, мы можем считать, что изначально на карточках не было никаких надписей, а числа на карточках появляются уже после того, как выбор сделан. Наша цель — предъявить такой способ разметки карточек, чтобы ни один из $80$ выбранных наборов не оказался хорошим.

Итак, пусть выбрано $80$ наборов. Рассмотрим произвольную карточку $A.$ Меняя некоторые наборы на дополнительные, можно добиться того, что карточка $A$ будет присутствовать во всех наборах. Перечислим с учётом кратности все остальные карточки, встречающиеся в этих наборах. Всего будет перечислено $80⋅7= 560$ карточек. Кроме карточки $A$ у нас имеется $15$ карточек, значит, какая-то из них встретится не менее $38$ раз(так как $37⋅15 =555< 560$ ), назовём её карточкой $B.$ Напишем на карточках $A$ и $B$ число $8,$ тогда те $38$ (или более) наборов, в которых встречаются обе эти карточки, будут плохими. Уберём карточки $A$ и $B,$ останется $14$ карточек и $42$ (или менее) набора, среди которых должен найтись хотя бы один хороший.

Аналогично зафиксируем одну из оставшихся карточек $C$ и переделаем наборы так, чтобы карточка $C$ входила во все наборы. Выписав все остальные карточки, встречающиеся в наборах, получим $42⋅6= 252$ карточки. Поскольку, помимо карточки $C,$ у нас имеется $13$ карточек, какая-то из них — назовём её $D$ — встретится $20$ раз(так как $19⋅13= 247 <252$ ). Напишем на карточках $C$ и $D$ число 7 — в результате все эти наборы станут плохими. Уберём карточки $C$ и $D,$ останется $12$ карточек и $22$ набора, среди которых опять должен найтись хороший.

Действуя аналогично, получим, что какие-то две карточки встретятся вместе хотя бы в $212⋅15= 10$ наборах, напишем на них число $6$ и выкинем, останется $10$ карточек и $12$ наборов. Тогда, поскольку $12⋅94= 513,$ какая-то пара карточек встретится в одном наборе хотя бы $6$ раз. Написав на этих карточках число $5$ и выкинув, мы получим $8$ карточек и $6$ наборов. Какая-то очередная пара карточек встретится в одном наборе хотя бы $6⋅37 =2 47$ раз, напишем на них число 4 и выкинем, в результате получим $6$ карточек и $3$ набора. Далее какая-то пара карточек встретится в одном наборе хотя бы $3⋅25 = 115$ раз, записываем на них число $3$ и выкидываем, останется $4$ карточки и $1$ набор. Напишем на двух карточках из этого набора число $1,$ а на двух других — число $2,$ тогда и этот набор также окажется плохим. Мы доказали, что всегда можно так занумеровать карточки, что все $80$ наборов окажутся плохими.

Покажем теперь, что для $2n$ карточек всегда можно выбрать $2n−1$ наборов так, чтобы хотя бы один из них оказался хорошим. В нашем случае $n= 7$ и мы сможем выбрать $26 =64< 80$ наборов, что решает задачу. Набор из $2n$ карточек, на которых записаны $n$ различных чисел(каждое — в двух экземплярах), будем называть двойным.

Пример 1. Докажем индукцией по $n,$ что для любого двойного набора из $2n$ карточек всегда можно предъявить $2n−1$ наборов, среди которых есть хороший. База $n =1$ очевидна.

Пусть на столе лежит двойной набор из $2n+ 2$ карточек. Попробуем наудачу выбрать из них две одинаковые карточки, взяв произвольные карточки $a$ и $b.$ Самоуверенно отложим их в сторону. Если мы угадали, то на столе остался двойной набор из $2n$ карточек, для которого, применив предположение индукции, можно указать $2n−1$ наборов, среди которых есть хороший. Теперь для каждого указанного набора $M$ рассмотрим наборы

Ma = M ∪{a}, Mb = M ∪{b}.

Мы утверждаем, что среди наборов $M b$ и $Ma$ (а их в сумме получается ровно $2n$ штук) непременно найдётся хороший(для исходного множества карточек) набор. Если карточки $a$ и $b$ и в самом деле одинаковые, это очевидно — подойдут даже два набора.

Предположим теперь, что на карточках $a$ и $b$ написаны разные числа(обозначим их также $a$ и $b$ ). Тогда в оставшемся множестве из $2n$ карточек были “непарные” карточки с числами $a$ и $b$ — мысленно соединим их в новую пару и применим предположение индукции, указав $n−1 2$ наборов, среди которых есть хороший набор $M,$ содержащий по одной карточке из каждой пары. На самом деле он содержит ровно одно из чисел новой пары, скажем $a,$ и по одному представителю всех остальных пар. Но тогда набор $Mb$ в исходном множестве карточек является хорошим!

Пример 2. Построим граф, вершинами которого являются карточки. Каждую пару карточек с одинаковыми числами соединим красным ребром. Проивзольным образом разобьём карточки на пары и соединим карточки в каждой паре синим ребром. Полученный красно-синий граф(на самом деле мультиграф, поскольку между одной парой вершин может быть проведено и красное, и синее ребро) представляет собой несколько циклов чётной длины. Рассмотрим такой набор его вершин, что в каждом цикле вершины выбраны через одну, назовём его чередующимся набором. Тогда в этом наборе будет присутствовать ровно один конец каждого красного ребра и, значит, он будет хорошим. Проблема в том, что мы, т.е. Мюнхгаузен, не знаем как именно проведены красные рёбра. Но заметим, что любой чередующийся набор содержит ровно по одной вершине каждого синего ребра. Поэтому, указав все $n 2$ наборов, содержащих ровно по одной вершине каждого синего ребра, мы заведомо укажем и чередующийся набор. Поскольку набор и его дополнение лишь одновременно могут быть чередующимися, из каждой пары взаимодополняющих наборов достаточно брать только один. Стало быть, достаточно указать лишь $n−1 2$ наборов.

Ответ:

при $n = 7$

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

Задача 9#70485

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

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

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

Подсказка 1

Давайте для начала причешем задачу. Если r - рациональное и положительное, то x,y - просто целые, так как можно построить явную биекцию между решениями при просто рациональных x,y и целых. Также, можно заметить, что если мы уберем целую часть числа r , то отношение из условия останется таким же, а значит, можно сказать, что 0 < r < 1 . А тогда можно сказать, что {(1 - r)x} = {-rx}, аналогично с y. Значит, можно считать, что y - натуральное, а х - целое. Значит, у нас, существенно, два случая - когда наша дробь - положительное число, и когда отрицательное. Попробуйте теперь найти такую дробь, которая не может быть представлена в таком виде как мы описали, и с теми условиями, которые мы доказали.

Подсказка 2

Сейчас будет приведено совсем не строгое, но тем не менее, наталкивающее на мысли, объяснение, почему нужно брать конкретную дробь, при разборе случая , когда дробь - положительное число. Давайте распишем {rx} как rx - [rx], {ry} как ry - [ry]. Тогда, для некоторого n/k = {rx}/{ry}, выполнено, что n*{ry} = k*{rx}. Значит, nry - n*[ry] = krx + k*[rx]. Что мы из этого можем получить? Если мы хотим прийти к противоречию, то можно попытаться взять какие - то k и n, такие, чтобы что-то в этом равенстве стало плохо. Сейчас целое число слева равно целому справа, а что можно подставить, чтобы слева, после преобразований, стало нецелое, а справа целое?

Подсказка 3

Возьмем n = x + 1, k = y. Тогда, во первых, сократятся rxy и rxy слева и справа, а в итого, останется уравнение {ry} = x * [ry] - y * [rx]. А значит, слева будет что - то между 0 и 1, а справа что-то целое. Пришли к противоречию. То есть, случай, когда дробь больше нуля разобран. Осталось подумать над случаем, когда наша дробь отрицательна. Можно попытаться найти контрпример, однако сразу непонятно как его строить, рассуждения из прошлого пункта непримиримы. Тогда скажем, что наша дробь равна некоторому a/b, где а - отрицательное и попытаемся доказать, что для любых а и b такое r найдется. И кажется, что в такой непонятной конструкции, как дробная часть, могут спасти только оценки значений. Попробуйте их применить(само собой, после избавления от знаменателей).

Подсказка 4

После избавления от знаменателей, у нас получается выражение brx - b*[rx] = ary - a[ry]. А значит, r - одно из решений уравнения r(bx - ay) = n, для некоторого целого n. При этом, мы можем сказать, что (без ограничения общности) х < 0, а значит, по нашим рассуждениям из первой подсказки, {rx} = 1 - {r|x|}. Подставьте это значение в наше уравнение и попробуйте подумать над максимальным и минимальным значением нецелое части.

Подсказка 5

Получим, что b = a{ry} + b{r|x|}. При r бесконечно близком к нулю, получается, что правая часть будет стремиться к нулю, что меньше b. При r бесконечно близким к 1, но меньшим ее, правая часть будет стремиться к a+b, что больше b. Значит, найдется промежуточное значение, при котором в нашем выражении будет достигаться равенство. А значит, для любой пары а и b из второго случая, мы привели пример. Значит, только для xy<0 выполнено требуемое.

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

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

Так как в качестве $r$ можно взять любое положительное рациональное число, можно считать, что числа $x$ и $y$ целые. В этом случае замена числа $r$ на его дробную часть не изменит отношения ${rx} {ry},$ значит, можно дополнительно считать, что $0< r< 1.$ Наконец, замена r на $1− r$ соответствует смене знаков чисел $x$ и $y,$ поскольку

{(1 − r)x} {−rx} {(1-− r)y}-= {−ry}.

Таким образом, достаточно рассмотреть лишь случай, когда $y$ — натуральное число.
Пусть $x$ также является натуральным числом. Покажем, что уравнение

{rx}-= x+1- {ry} y

не имеет решений относительно $r.$ Домножив на знаменатели и выразив дробную часть через целую, получим уравнение

y⋅rx− y⋅[rx]= x⋅ry− x ⋅[ry]+ {ry},

или, что то же самое,

{ry} =x ⋅[ry]− y⋅[rx].

Но это уравнение не может иметь решений, поскольку левая часть положительна и меньше $1,$ а правая часть целая. Следовательно, если числа $x$ и $y$ одного знака, то требуемое $r$ не найдётся.
Пусть $x$ является отрицательным целым числом. Достаточно показать, что уравнение

{rx} a {ry} = b (∗)

для любых натуральных чисел $a$ и $b$ имеет вещественное решение $r.$ Тогда

b⋅rx− b⋅[rx]=a ⋅ry− a⋅[ry]

и, значит, $r$ является решением линейного уравнения

(bx− ay)r= n

для некоторого целого $n$ и, в частности, должно быть рациональным числом. Домножив уравнение $(∗)$ на знаменатели и воспользовавшись тем, что ${rx} =1 − {r|x|},$ получим уравнение

b= a{ry} +b{r|x|}.

При $r= 0$ правая часть равна нулю и поэтому меньше левой. А при $r,$ близких к $1,$ обе дробные части также будут близки к $1,$ поэтому правая часть будет близка к $a+ b$ и, в частности, будет больше левой. Следовательно, при некотором промежуточном $r$ правая часть будет равна левой. Поэтому если числа $x$ и $y$ разных знаков, то требуемое $r$ обязательно найдётся.

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

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

$PIC$

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

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

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

Ответ:

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

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

Задача 10#70484

Высоты $AA ,BB ,CC 1 1 1$ остроугольного треугольника $ABC$ пересекаются в точке $H.$ На касательную, проведенную из точки $C$ к описанной окружности треугольника $AB1C1,$ опущен перпендикуляр $HQ$ (точка $Q$ лежит внутри треугольника $ABC$ ). Докажите, что окружность, проходящая через точку $B1$ и касающаяся прямой $AB$ в точке $A,$ касается также и прямой $A1Q.$

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

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

Подсказка 1

На картинке даны какие-то касательные, присутствуют хорды - ну не просто же так! Стоит отметить равные между собой вписанные уголки в двух окружностях. Хочется доказать, что A₁Q- касательная…нет ли случайно походе конструкции на чертеже?

Подсказка 2

Из того, что AB - касательная, следует, что в двух окружностях на чертеже есть отсеченные дуги, равные удвоенному углу CAB. Мы знаем, что CQ - касательная. А хочется, чтобы A1Q стала касательной…можно ли их как-то связать? А как связать между собой окружности?

Подсказка 3

Если мы найдем преобразование, которой переведет СQ в А1Q, а окружности друг в друга, то мы сможем доказать, что A1Q тоже является касательной!

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

Обозначим через $s 1$ описанную окружность треугольника $AB C , 1 1$ а через $s 2$ — окружность, проходящую через точку $B 1$ и касающуюся прямой $AB$ в точке $A.$ Хорды $B1C1$ и $B1A$ этих окружностей отсекают от них дуги одинаковой угловой величины. В самом деле, половины этих дуг в обоих случаях равны $∠B1AC1$ : для окружности $s1$ это вписанный угол, а для $s2$ — угол между касательной и хордой.

Заметим также, что угол между прямыми $CC1$ и $CQ$ равен углу между прямыми $AA1$ и $A1Q:$ эти вписанные углы опираются на одну дугу $HQ$ в окружности с диаметром $CH.$

$PIC$

Точку пересечения прямой $AA1$ с окружностью $s2$ обозначим через $P$ и выделим на картинке два фрагмента: в окружности $s1$ проведена секущая $HC1,$ и на ней выбрана точка $C;$ в окружности $s2$ проведена секущая $AP,$ и на ней выбрана точка $A1.$ В каждом из этих двух фрагментов из точек на секущих проведены прямые под одинаковыми углами к секущим: $CQ$ и $A1Q.$ Первая из них касается $s1,$ и нам нужно доказать, что вторая касается $s2.$ Для доказательства нужно установить, что две описанные конфигурации подобны. Мы проверим это двумя способами. Углы треугольника, как обычно, будем обозначать греческими буквами, соответствующими названиям вершин.

Способ 1.(подсчёт отношения отрезков)

Угловые величины отсекаемых секущими дуг равны, поэтому остаётся проверить, что $ACP1H = ACA1C1.$ Отношение хорд $AP$ и $C1H$ (стягивающих равные дуги) равно отношению диаметров окружностей. Диаметр окружности $s1$ равен $AH;$ диаметр окружности $s2$ равен $sin∠ACB11AB1 =sAinB∠1A .$ Таким образом, $CA1PH = AHAsBin1α-= sisinnγα.$ С другой стороны, отношение высот $ACAC11$ равно отношению сторон $ABBC,$ которое по теореме синусов тоже равно $sisinnγα.$

$PIC$

Способ 2.(Поворотная гомотетия)

Рассмотрим поворотную гомотетию с центром в точке $B1,$ переводящую точку $C1$ в $A$ и $C$ в $A1.$ Она существует, ибо треугольники $B1C1A$ и $B1CA1$ подобны(и подобны треугольнику $BAC$ ). Окружность $s1$ перейдёт в $s2,$ ибо друг в друга переходят хорды $B1C1$ и $B1A,$ отсекающие равные дуги. При этом секущая $CC1$ окружности $s1$ переходит в секущую $AA1$ окружности $s2,$ и, следовательно, точка $H$ переходит в точку $P.$ Значит, первый фрагмент переходит во второй.

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

Задача 11#70483

Будем говорить, что набор чисел $a ,...,a 1 m$ сильнее набора чисел $b,...,b , 1 n$ если среди всех неравенств вида $a > b i j$ количество верных неравенств не менее чем в $2$ раза превосходит количество неверных. Докажите, что не существует трех наборов $A,B,C,$ таких, что $A$ сильнее $B,$ $B$ сильнее $C,$ $C$ сильнее $A.$

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

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

Подсказка 1

Нам дали факт о том, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных» и просят доказать, что какой-то факт не выполнен, скорее всего мы получим противоречие с тем, что какая-то величина будет одновременно больше и меньше какого-то числа или мы сможем показать, что она не меньше и не больше некоторой числа, а значит равна ему и такой случай уже намного проще разобрать.

Подсказка 2

Давайте теперь зафиксируем произвольную тройку (A_i, B_j, C_t) и распишем для неё условие, что A сильнее B, B сильнее C, C сильнее A. А сколько вообще может быть верных неравенств при таком условии? Может попробовать оценить сверху и снизу количество верных неравенств?

Подсказка 3

Действительно, количество верных неравенств не больше чем 2, мы показали это для произвольной тройки, а сколько всего троек? Теперь попробуем понять, как ограничить эту величину снизу. Мы не пользовались тем, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных». Как раз «не менее» намекает нам о том, что мы сможем оценить снизу.

Подсказка 4

Можно посмотреть на наборы A, B и поотвечать на вопросы. А сколько можно записать неравенств вида a_i > b_j? А сколько из них должны быть верными? А мы пользовались какими-либо особенностями множеств A и B или это можно сказать для любой пары множеств?

Подсказка 5

Ура, мы получили, что количество верных неравенств не меньше чего-то, но и не больше, а значит в точности равно этому числу. Это уже хорошее условие, но на самом деле мы знаем больше! Что должно выполняться, чтобы это равенство достигалось?

Подсказка 6

Верно, количество верных неравенств должно быть ровно в 2 раза больше количества неверных! Так как мы доказываем, что такого не бывает, то в какой-то из пар наборов количество верных больше, чем в 2 раза неверных, а для числа с каким свойством неравенство было бы выполнено для всех остальных чисел?

Подсказка 7

Верно, для наибольшего из всех чисел или для наименьшего, здесь мы пользовались принципом крайнего, который часто может встречаться в задачках, где что-то сравнивается. Вернёмся к условию, что A сильнее B, B сильнее C, C сильнее A, оно ведь тоже участвовало в оценке, тогда что должно быть верно, чтобы она достигалась? Как нам объединить это с прошлым фактом?

Подсказка 8

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

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

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

A = (a1,...,al),B = (b1,...,bm ),C =(c1,...,cn)

таковы, что $A$ сильнее $B,B$ сильнее $C,C$ сильнее $A.$ Можно считать, что число $a1$ наибольшее среди всех чисел этих трёх наборов. Для каждой тройки индексов $i,j,k(1 ≤i≤ l,1≤ m,1≤ k≤ n)$ посчитаем, сколько верных увтерждений имеется среди неравенств $a > b,b >c ,c >a , i j j k k i$ просуммируем эти числа по всем $i,j,k$ и обозначим полученную сумму через $S.$ Тогда

S ≤ 2lmn, (∗)

поскольку всего имеется $lmn$ троек и в каждой тройке не больше двух верных неравенств. Далее заметим, что каждое неравенство $ai > bj$ присутствует в $n$ таких тройках, поэтому в сумме $S$ оно учтено $n$ раз. По предположению среди неравенств $ai > bj$ не меньше $2lm 3$ верных, поэтому вклад всех неравенств вида $ai >bj$ в сумму $S$ не меньше чем $2lmn. 3$ Аналогично вклад всех неравенств вида $b > c j k$ в сумму $S$ и вклад всех неравенств вида $c > a k i$ в сумму $S$ также не меньше чем $2lmn. 3$ Следовательно, суммарное количество верных неравенств не меньше чем $3⋅ 2lmn ≥S. 3$

Сопоставляя это с неравенством $(∗),$ заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности $2 3mn$ верных неравенств вида $bj > ck,$ а в каждой тройке $ai > bj,bj >ck,ck >ai$ ровно два верных неравенства.

Рассмотрим теперь тройку чисел $a1,bj,ck.$ Среди неравенств $a1 >bj,bj > ck,ck >a1$ должно быть ровно два верных. Поскольку $a1$ — наибольшее число неравенство $ck > a1$ неверно, т.е. выолняется неравенство $bj > ck.$ Значит, все неравенства вида $bj > ck$ верные и всего их $mn$ штук. Но это противоречит тому, что их $2 3mn.$ Стало быть, наше предположение неверно.

Интенсивы

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

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

Задача 12#70482

Иван и Кощей играют в следующую игру. Изначально на доске записан многочлен $x− 1.$ За один ход можно заменить многочлен $f(x),$ записанный на доске, на многочлен $n+1 ax − f(− x)− 2,$ где $n$ — степень многочлена $f(x),$ а $a$ — один из его вещественных корней. Игроки ходят по очереди, начинает Иван. Выигрывает тот игрок, после хода которого на доске будет написан многочлен, не имеющий вещественных корней. Сможет ли Иван победить Кощея?

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

Подсказка 1

Вспомним полезную теорему про многочлен нечётной степени! Что в таком случае можно сказать про Ивана?

Подсказка 2

Да, он точно не проиграет, ведь на его ходе всегда будет получаться многочлен нечётной степени, у которого всегда есть хотя бы один вещественный корень! А что можно сказать про Кащея? Для ответа на этот вопрос: рассмотрите f(0), где f - многочлен чётной степени, с положительным старшим коэффициентом!

Подсказка 3

Да, поскольку у нас изначально многочлен равен x-1(корень 1), то Кащей может на каждом шаге брать вместо a - положительный корень предыдущего многочлена(который всегда существуют)! А тогда, у многочлена Кащея тоже всегда будет вещественный корень!

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

Ивану достаётся многочлен нечетной степени, поэтому он не может проиграть. Однако Кощей тоже не может проигрывать: для этого ему достаточно каждый раз выбирать положительный корень. Заметим, что свободный член всегда равен $− 1.$ Легко проверить, что при такой стратегии Кощея Ивану будут доставаться многочлены нечетной степени с чередующимися знаками коэффициентов (старший - положительный), и поэтому у них есть лишь положительные корни; а Кощею будут доставаться многочлены четной степени с положительным старшим коэффициентом и свободным членом $− 1,$ поэтому у них существует положительный корень

Ответ:

Нет

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

Задача 13#70481

В остроугольном треугольнике $ABC$ с углом $45∘$ при вершине $A$ проведены высоты $AD,$ $BE$ и $CF.$ Луч $EF$ пересекает прямую $BC$ в точке $X.$ Оказалось, что $AX||DE.$ Найдите углы треугольника $ABC.$

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

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

Подсказка 1

Даны параллельность и вписанность - это сразу же намекает нам на углы! Попробуем поотмечать, а потом воспользуемся условием на угол A) Что узнаем?

Подсказка 2

Понимаем, что AF = FC! Теперь мы можем посчитать достаточно большое количество углов на картинке...но все из них равны либо 90, либо 90/2. На что это может намекать? Обратим внимание на точку F.

Подсказка 3

Угол AFC в 2 раза больше чем AXC. Чем тогда является F для треугольника AXC? Когда мы это поймем, мы сможем по аналогии связать углы AFX=EFB и ACB. Не забываем про вписанность!)

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

$PIC$

Из условия следует, что $AF =F C$ . Из вписанностей $∠CDE = 45∘$ , и теперь из параллельности $∠AXD = 45∘$ . В треугольнике $AXC$ точка $F$ оказалась центром описанной окружности (равноудалена от вершин $A$ и $C$ и центральный угол в два раза больше вписанного). Поэтому $2∠ACB = ∠AF X = ∠BF E$ , что вместе со вписанностью $BF EC$ дает $∠ACB = 60∘$

Ответ:

$45∘,60∘,75∘$

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

Задача 14#70480

Можно ли на параболе $y = x2$ отметить точки $A,B,C,D,$ а на параболе $y = 2x2$ — точки $E,F,G,H$ так, чтобы выпуклые четырехугольники $ABCD$ и $EFGH$ оказались равными?

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

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

Подсказка 1

Первое, что нужно сказать про эту задачу - это то, что на самом деле эта задача на конструктив, но при этом не как конкретный пример, который чем-то единственным образом задан, а просто приведение какого-то непонятного примера. Подумайте над тем, что будет, если два «вписанных» в параболу четырехугольника равны. А как тогда построить такой четырехугольник?

Подсказка 2

Верно, если они равны, то они совпадают наложением, а значит мы можем так повернуть параболы, что четырехугольник будет «вписан» в обе параболы. А как теперь самим построить пример?

Подсказка 3

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

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

Достаточно расположить эти параболы на плоскости так, чтобы они пересекались в четырёх точках. Эти четыре точки взять в качестве $A,B,C,D$ и одновременно $E,F,G,H.$ Одинаковые четырёхугольники являются равными.

Ответ: да

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

Задача 15#71960

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

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

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

Разрежем единичный квадрат на два равных прямоугольников, сделаем один из них синим, а другой красным. Тогда одно отношение равно $2,$ а другое — $1 2.$

Поскольку в задаче фигурируют только отношения длин сторон, можно считать, что исходный квадрат имел сторону 1. Тогда суммарная площадь прямоугольников каждого цвета равна $1 2.$ Занумеруем синие прямоугольники числами от $1$ до $m,$ а красные прямоугольники числами от $1$ до $n.$ Пусть $ak$ и $bk$ — соответственно длины вертикальной и горизонтальной сторон $k−$ го синего прямоугольника, а $ck$ и $dk$ — соответственно длины вертикальной и горизонтальной сторон $k−$ го красного прямоугольника. Тогда

∑m n∑ akbk = ckdk = 1. k=1 k=1 2

Так как стороны всех прямоугольников не превосходят $1,$ имеем

m∑ ak ∑m 1 n∑ ck n∑ 1 B = bk ≥ akbk = 2 R = dk-≥ ckdk = 2. k=1 k=1 k=1 k=1

Теперь достаточно показать, что хотя бы одна из сумм $B$ и $R$ не меньше $2.$ Начнём с того, что справедливо хотя бы одно из двух неравенств

m∑ ∑n k=1ak ≥1, k=1dk ≥ 1. (∗)

И в самом деле, спроецируем синие прямоугольники на вертикальную сторону квадрата, а красные — на горизонтальную. Если, например, $m∑ d <1, k=1 k$ то какой-то промежуток на горизонтальной стороне квадрата не будет покрыт проекциями красных прямоугольников. Тогда полоса над этим промежутком полностью синяя, так как в неё не могут залезать красные прямоугольники. Следовательно, сумма длин вертикальных сторон синих прямоугольников, покрывающих эту полосу, не меньше $1,$ и, значит, $m ∑ ak ≥1. k=1$

Пусть для определённости верно первое из неравенств (*). Тогда по неравенству Коши - Буняковского

( )2 ( )2 B-=∑m a b m∑ ak≥ ∑m ∘a-b-ak- = m∑ a ≥1. 2 k=1 k kk=1bk k=1 k kbk k=1 k

Следовательно, $B ≥ 2$ и $B+ R ≥2 + 12 = 52.$

Ответ:

$5 2$

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

Задача 16#71959

Точка $M$ — середина основания $AD$ трапеции $ABCD,$ вписанной в окружность $ω.$ Биссектриса угла $ABD$ пересекает отрезок $AM$ в точке $K.$ Прямая $CM$ вторично пересекает окружность $ω$ в точке $N.$ Из точки $B$ проведены касательные $BP$ и $BQ$ к описанной окружности треугольника $MKN.$ Докажите, что прямые $BK,MN$ и $P Q$ пересекаются в одной точке.

$PIC$

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

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

Решение 1.

Пусть луч $BK$ пересекает описанную окружность в точке $T$ — середине дуги $AD.$ Заметим, что

∠BT N = ∠BCN = ∠AMN.

Следовательно, описанная окружность треугольника $MKN$ проходит через точку $T.$ Кроме того, $∠KMT$ прямой, поэтому прямая $BT$ содержит диаметр этой окружности. Пусть прямая $CN$ пересекает этот диаметр в точке $X,$ а прямая $PQ$ пересекает его в точке $X ′.$

$PIC$

Для решения задачи требуется установить, что $X =X ′.$ Пусть $O$ и $r$ — центр и радиус этой окружности. Точка $X ′$ обладает известным свойством: $OB ⋅OX ′ = r2.$ Поэтому нам осталось проверить, что $OB ⋅OX = r2.$

Обозначим

ϕ = ∠AKB = ∠OKM = ∠OMK,

ψ =∠KMB = ∠CMD = ∠XMK.

Тогда $∠KBM =ϕ − ψ =∠XMO.$ Это означает, что треугольник $OMX$ и $OBM$ подобны и $OB ⋅OX = OM2 = r2.$

Решение 2.

Как и предыдущем решении, докажем, что $X = X′.$ Для этого достаточно проверить, что

(B,X,K,T)= (B,X′,K,T ).

$PIC$

Мы докажем, что обе эти четвёрки гармонические. Заметим, что четырёхугольник $KQT P$ гармонический, так как касательные в точках $P$ и $Q$ пересекаеются на $KT.$ Проецируя эту четвёрку точек из точки $P$ на прямую $BT,$ получим $(B,X′,K,T)= −1.$ С другой стороны, проецируя четвёрку $B,X,K,T$ из точки $M$ на прямую $BC,$ получим

(B,X,K,T )=(B,C,L ,M ′), ∞

где $L∞$ — бесконечно удалённая точка направления $BC.$ Осталось заметить, что, так как $T$ — середина дуги $AD,$ а $M$ — середина отрезка $AD,$ прямая $MT$ — серединный перпендикуляр к основанию вписанной трапеции $ABCD.$ Следовательно, $M ′$ — середина отрезка $BC$ и $(B,C,L∞,M ′)= −1.$

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

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

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

Задача 17#71958

Дано натуральное число $n.$ Для каждого простого числа $p$ из промежутка $[n,n2]$ посчитали число $1, p$ и все полученные числа сложили. Докажите, их сумма меньше $2.$

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

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

Выпишем числа от $1$ до $n2$ и для каждого простого числа $p$ из отрезка $[n,n2]$ подчеркнём те числа, которые делятся на $p.$ Для каждого $p$ будет подчёркнуто в точности $[n2] n2 p > p − 1$ чисел, причём каждое число будет подчёркнуто не больше одного раза. Действительно, если число $k$ подчеркнули как делящееся на простые числа $p$ и $q,$ то $k$ делится и на $2 pq > n ,$ что невозможно. Таким образом, всего подчёркнуто не менее чем $∑ (n2 ) p − 1$ чисел(суммирование ведётся по всем простым числам от $n$ до $2 n$ ). Количество слагаемых в сумме не превосходит $2 n ,$ поэтому вычитается не более $2 n$ единиц. Поскольку количество чисел не меньше $2 n$ и каждое подчёркнуто не более одного раза, всего подчёркиваний меньше, чем $2 n.$ Следовательно,

∑ (n2 ) ∑ n2 n2 > -p − 1 > -p − n2

откуда после сокращения на $n2$ получаем требуемое неравенство $∑ 1p <2.$

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

Задача 18#71957

На доске написаны функции

2 12 ( 2) F (x)= x + x2, G(x)= sin πx и H(x)=1.

Если на доске уже написаны функции $f(x)$ и $g(x),$ то можно выписать на доску еще и функции

f(x)+ g(x), f(x)− g(x), f(x)g(x), cf(x)

(последнюю - с любым вещественным коэффициентом $c$ ). Может ли на доске появиться такая функция $h(x),$ что $1 |h(x)− x|< 3$ при всех $x∈ [1,10]?$

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

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

Заметим, что при совершаемых операциях значения в точках $1$ и $√12$ всегда остаются равными, потому что

√-- √-- √-- F(1)= 13= F( 12), G(1)= 0= G( 12), H(1)= 1= H( 12)

Теперь предположим, что требуемая функция $h(x)$ нашлась. Тогда $h(1)= h(√12)= a.$ По условию должно быть

1 √-- 2 |a− 1|< 3 и |a− 12|<3

Следовательно,

√-- 2 12− 1< 3

Пришли к противоречию.

Ответ: нет

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

Задача 19#71956

В пирамиде $SA A ...A 1 2 n$ все боковые рёбра равны. Точка $X 1$ — середина дуги $A A 1 2$ описанной окружности треугольника $SA A , 1 2$ точка $X2$ — середина дуги $A2A3$ описанной окружности треугольника $SA2A3$ и т. д., точка $Xn$ — середина дуги $AnA1$ описанной окружности треугольника $SAnA1.$ Докажите, что описанные окружности треугольников $X1A2X2,X2A3X3,...,XnA1X1$ пересекаются в одной точке.

$PIC$

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

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

Заметим, что точки $A ,A ,...,A 1 2 n$ лежат и на сфере с центром в точке $S,$ и в одной плоскости. Следовательно, они лежат на окружности $ω,$ являющейся пересечением сферы с плоскостью. Пусть $O$ — центр этой окружности. Тогда $SO$ перпендикулярно плоскости основания и любая точка на прямой $SO$ равноудалена от всех точек окружности $ω.$ Поэтому на $SO$ найдётся и такая точка $P,$ для которой $P S = PA1.$ Тогда на сфере $σ$ с центром в точке $P$ и радиусом $PS$ лежат все вершины пирамиды, а также все окружности $SAkAk+1.$

$PIC$

Следовательно, на этой сфере лежат все точки $Ak$ и $Xk.$ Пусть $N$ — точка на сфере $σ,$ диаметрально противоположная точке $S.$ Покажем, что описанные окружности треугольников $Xk− 1AkXk$ проходят через точку $N.$ Поскольку точки $N, Xk−1,Xk$ и $Ak$ лежат на сфере, достаточно проверить, что они лежат на сфере, достаточно в одной плоскости. Эта плоскость перпендикулярна прямой $SAk$ и проходит через точку $Ak.$ В самом деле, $∠SAkN = 90∘,$ поскольку они опирается на диаметр $SN$ сферы $σ,∠SAkXk =90∘$ и $∠SAkXk −1 = 90∘,$ поскольку они опираются на диаметры $SXk$ и $SXk −1$ описанных окружностей треугольников $SAkXk$ и $SAkXk −1.$

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

Задача 20#71955

Клетки таблицы $100×100$ окрашены в белый цвет. За один ход разрешается выбрать любые $99$ клеток из одной строки или из одного столбца и перекрасить каждую из них в противоположный цвет — из белого в черный, а из черного в белый. За какое наименьшее количество ходов можно получить таблицу с шахматной раскраской клеток?

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

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

Оценка.

Покажем, что $100$ ходов обязательно придётся сделать.

Первый способ. Предположим, что мы получили шахматную раскраску. Рассмотрим диагональ, покрашенную в чёрный цвет. За ход можно перекрасить не более одной клетки этой диагонали, следовательно, потребовалось не менее $100$ ходов.

Второй способ. Предположим, что мы сделали менее $100$ ходов. Тогда найдётся строка, которую мы не задействовали. Но в этой строке в результате появилось $50$ чёрных клеток, значит, было сделано как минимум $50$ “вертикальных” ходов. Аналогично показывается, что было сделано как минимум $50$ “горизонтальных” ходов, т.е. всего не менее $100$ ходов.

Пример.

Покажем, как за $100$ ходов можно получить шахматную раскраску, для этого перекрасим первый столбец без первой клетки, третий столбец без третьей клетки, пятый столбец без пятой клетки, $...,$ $99−$ й столбец без $99−$ й клетки. Дальше перекрасим первую строку без первой клетки, третью строку без третьей клетки, пятую без пятой клетки, $...,$ $99−$ ю строку без $99−$ й клетки. Тогда все клетки, у которых номер строки и номер столбца имеют разную чётность, окажутся переркашенными ровно один раз и, значит, чёрными, а остальные клетки будут белыми.

Ответ:

$100$ ходов

Предыдущий раздел

Следующий раздел


1	2	3	…	100

101	102	103	…	200

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

9901	9902	9903	…	10000