ТурГор (Турнир Городов) —Каталог задач по Олимпиадной математике

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

Тема ТурГор (Турнир Городов)

ТурГор (Турнир Городов)

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

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

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

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

Разделы подтемы ТурГор (Турнир Городов)

Базовый вариант осеннего тура Турнира Городов

Сложный вариант осеннего тура Турнира Городов

Базовый вариант весеннего тура Турнира Городов

Сложный вариант весеннего тура Турнира Городов

Алгебраические текстовые задачи на устном туре Турнира Городов

Комбинаторика на устном туре Турнира Городов

Планиметрия на устном туре Турнира Городов

Стереометрия на устном туре Турнира Городов

Теория чисел на устном туре Турнира Городов

Тождественные преобразования и многочлены на устном туре Турнира Городов

Квадратные трёхчлены на устном туре Турнира Городов

Функции на устном туре Турнира Городов

Подтемы раздела тургор (турнир городов)

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

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

Задача 1#85519

У Вани есть клетчатая бумага двух видов: белая и чёрная. Он вырезает кусок из любой бумаги и наклеивает на серую клетчатую доску $45× 45,$ делая так много раз. Какое минимальное число кусков нужно наклеить, чтобы «раскрасить» клетки доски в шахматном порядке? (Каждый кусок — набор клеток, в котором от любой клетки до любой другой можно пройти, переходя из клетки в соседнюю через их общую сторону. Можно наклеивать куски один поверх другого. Все клетки имеют размер $1× 1.)$

Источники: Турнир городов - 2024, весенний тур, 11.6 (см. turgor.ru)

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

Подсказка 1

Когда сложно понять, как устроена наша конструкция, можно попробовать рассмотреть “маленькие” поля, со стороной 1,2 или 3, в них будет легче понять закономерность и прийти к мысли об оценке и примере.

Подсказка 2

Если мы увидели предположительную закономерность на маленьких числах, для оценки можно попытаться применить индукцию. Для того чтобы осуществить шаг индукции, можно воспользоваться тем, что шахматная доска состоит из большого числа отдельных белых и черных “кусочков”. Как это формализовать?

Подсказка 3

Шахматная раскраска означает, что при переходе в соседнюю по стороне клетку мы всегда меняем цвет. И для оценки можно как раз считать количество таких “смен цвета”, в данной задаче эта конструкция очень и очень поможет!

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

Оценка.

Можно считать, что первый наклеенный кусок — весь квадрат, от этого ничего не испортится. Считаем его нулевым. Докажем индукцией по $k$ утверждение:

_________________________________________________________________________________________________________________________________________________________________________________

После еще $k$ кусков между любыми двумя клетками есть путь с не более чем $2k$ сменами цвета.

_________________________________________________________________________________________________________________________________________________________________________________

База при $k= 0$ верна.

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим наклеивание $k$ -го куска $S$ . Пусть до этого между двумя клетками был путь с не более $2(k− 1)$ сменами цвета. Если он не заходил в $S$ , то он таким и остался. Иначе заменим его кусок от первой его клетки в $S$ до последней такой клетки на путь по $S$ между этими клетками. Тогда количество смен цвета в новом пути увеличилось не более чем на 2 по сравнению со старым. Переход доказан.

_________________________________________________________________________________________________________________________________________________________________________________

В конце между противоположными углами любой путь имеет хотя бы 88 смен цвета. Значит, поверх нулевого куска наклеено еще хотя бы 44.

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

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

Ответ: 45

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

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

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

Задача 2#85517

Вписанная сфера треугольной пирамиды $SABC$ касается основания $ABC$ в точке $P$ , а боковых граней - в точках $K,M$ и $N$ . Прямые $P K,PM,PN$ пересекают плоскость, проходящую через середины боковых рёбер пирамиды, в точках $′ ′ ′ K ,M ,N$ . Докажите, что прямая SP проходит через центр описанной окружности треугольника $′ ′ ′ K M N$ .

Источники: Турнир городов - 2024, весенний тур, 11.5 (см. turgor.ru)

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

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

Сделаем гомотетию с центром $P$ и коэффициентом 2. Пусть $′′ ′′ ′′ K ,M ,N$ — образы точек $′ ′ ′ K ,M ,N ,T$ — точка пересечения прямой $SK$ с плоскостью $ABC$ . Тогда $TK =T P$ как касательные к сфере, и, поскольку треугольники $PKT$ и $′′ K KS$ подобны, то $′′ SK = SK$ . Аналогично $′′ ′′ SM = SM,SN = SN$ . Но $SK = SM = SN$ как касательные, следовательно $S$ — центр окружности $′′ ′′ ′′ K M N$ , а середина $SP$ — центр окружности $KMN.$

______________________________________________________________________________________________________________________________________________________

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

Обозначим сферу, проходящую через точки $K,M,N$ , с центром в точке $S$ , через $ω$ , вписанную сферу пирамиды — через $γ$ , а плоскость, проходящую через середины рёбер пирамиды — через $α$ .

Сделаем инверсию с центром в точке $P$ , переводящую $γ$ в $α$ . Тогда точки $K,M, N$ перейдут в точки $K′,M′,N′$ . Так как $ω ⊥γ$ , то образ $ω$ будет перпендикулярен $α$ . Следовательно, образом $ω$ будет сфера, построенная на окружности ( $K′M′N′$ ) как на диаметральной окружности.

Тогда утверждение задачи следует из того, что центр инверсии, центр сферы и центр её образа лежат на одной прямой.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание.

Утверждение задачи является частным случаем следующего факта.

Рассмотрим стереографическую проекцию сферы $S$ на плоскость $π$ из точки $P ∈ S$ . Пусть $Q$ — точка вне сферы $S$ , а окружность $ω$ на $S$ , образованная касательными к $S$ из $Q$ , не проходит через $P$ . Тогда образом $ω$ будет окружность $ω′$ с центром в точке пересечения плоскости $π$ с лучом $PQ$ .

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

Задача 3#85513

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

Источники: Турнир городов - 2024, весенний тур, 11.4 (см. turgor.ru)

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Можно указать точку $O$ явно - например, подойдёт точка $√ -√- ( 2, 3)$ . Пусть на прямой, проходящей через эту точку, есть две рациональные точки $(a,b)$ и ( $c,d$ ) (где $a,b,c,d$ рациональные). Тогда вектора ( $√- √- a− 2,b− 3)$ и $(a− c,b− d)$ пропорциональны, откуда

√- √- (a− 2)(b− d)=(b− 3)(a− c),

откуда $√ - √- a(b− d)− b(a− c)=(b− d) 2− (a− c) 3$ . Возводя в квадрат и перенося заведомо рациональные слагаемые в левую часть, получим, что будет рациональным число $√- 2(b− d)(a− c) 6$ , что возможно только при $b= d$ или $a= c$ . Но из равенства (*) видим, что если выполнено хоть одно из равенств $b= d,a =c$ , то выполнено и второе, откуда точки $(a,b)$ и $(c,d)$ совпадают.

_________________________________________________________________________________________________________________________________________________________________________________

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

Ответ: да

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

Задача 4#85511

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

Источники: Турнир городов - 2024, весенний тур, 11.3 (см. turgor.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

То есть нужны группы, в которых все клетки не могут быть плохими. А что будет, если все клетки будут плохими? Как это переформулировать?

Подсказка 4

Нужны такие клетки, чтобы у нас уж точно сумма по столбцам была не больше, чем сумма по строкам

Подсказка 5

А что если сделать так, чтобы эти столбцы и строки образовывали всю доску?

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

Оценка.

Разобьём все клетки таблицы на $N$ грушп по $N$ клеток так, чтобы в каждой груше все клетки находились в разных строках и разных столбцах. Пример такого разбиения для $N =5$ см. на рисунке:


1	2	3	4	5

5	1	2	3	4

4	5	1	2	3

3	4	5	1	2

2	3	4	5	1

Для других $N$ разбиение аналогично: например, в одну группу берём главную диагональ (идущую сверху слева вниз вправо), во вторую — диагональ над ней и число в левом нижнем углу, в третью — следующую диагональ и диагональ из двух клеток слева внизу, и т.д.

Предположим, что в какой-то группе все клетки плохие. Тогда для каждой клетки этой группы сумма чисел содержащей её строки меньше суммы чисел содержащего её столбца. Суммируя эти неравенства по всем клеткам групшы, получаем, что сумма чисел во всей таблице, подсчитанная по строкам, меньше, чем эта же сумма, подсчитанная по столбцам - противоречие, Значит, в каждой группе есть хорошая клетка, и число хороших клеток не меньше числа групп, то есть не меньше $N$ .

_________________________________________________________________________________________________________________________________________________________________________________

Пример, подтверждающий точность полученной оценки

$N$ хороших клеток уже возможно.

Пусть в первой строке стоят единицы, а в остальных нули. Тогда все клетки первой строки хорошие, а остальные плохие.

Ответ: N

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

Задача 5#85508

Точки $P,Q$ лежат внутри окружности $ω$ . Серединный перпендикуляр к отрезку $PQ$ пересекает $ω$ в точках $A$ и $D$ . Окружность с центром $D$ , проходящая через $P$ и $Q$ , пересекает $ω$ в точках $B$ и $C$ . Отрезок $PQ$ лежит внутри треугольника $ABC$ . Докажите, что $∠ACP =∠BCQ$ .

Источники: Турнир городов - 2024, весенний тур, 11.2 (см. turgor.ru)

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

Подсказка 1

Про окружность ω пока толком ничего не известно, а вот окружность с центром в D даёт сразу 4 равных отрезка (равенство радиусов) на чертеже. Посмотрите, что из этого можно взять для окружности ω.

Подсказка 2

Так как BD=DC, то дуги ВD и DC в ω равны, значит, AD — биссектриса ∠BAC.

Подсказка 3

Пусть I — точка пересечения отрезка АD и дуги BPQC, тогда по теореме о трилистнике I — центр вписанной в ΔABC окружности. Что же можно взять из этого факта, если в задаче нам нужно доказать равенство углов?

Подсказка 4

Конечно! То, что CI — биссектриса ∠BСА. Для завершения доказательства не хватает равенства ∠PCI и ∠ICQ, но это совсем несложно получить, если Вы ещё не забыли, чем по условию является AD для отрезка PQ.

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

$PIC$

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

Пусть $I$ — точка пересечения отрезка $AD$ и дуги $BPQC$ . Так как $DB = DC$ , то $AD$ — биссектриса угла $BAC$ и по теореме о трилистнике $I$ — центр вписанной в треугольник $ABC$ окружности. Следовательно, $CI$ — биссектриса угла $ACB$ . С другой стороны, так как $AD −$ серединный перпендикуляр к $P Q$ , то $PI = QI$ , то есть $CI$ — биссектриса угла $PCQ$ . Из этих двух утверждений следует утверждение задачи.

_________________________________________________________________________________________________________________________________________________________________________________

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

Обозначим $∠ACQ =α,∠QCP = β,∠PCB = γ$ . Необходимо доказать, что $γ = α$ .

Заметим, что

α+ β+ γ = ∠ACB = ∠ADB = ∠BDP +∠PDA

Далее, $∠BDP = 2∠BCP = 2γ$ , как центральный и вписанный в окружность ( $DP Q$ ), а также $∠P DA = 12∠PDQ = 12 ⋅2∠PCQ = β$ , как центральный и вписанный в окружность ( $DPQ$ ). Тогда

α+ β+ γ = ∠BDP + ∠PDA = 2γ+β

γ =α

______________________________________________________________________________________________________________________________________________________

Замечание.

В условии задачи дано, что точки $P$ и $Q$ лежат не только внутри окружности $ω$ , но и внутри вписанного в неё треугольника $ABC$ . Последнее условие на самом деле излишне. Из остальных условий задачи следует, что точки $P$ и $Q$ изогонально сопряжены относительно треугольника $ABC$ . Но если обе изогональные точки лежат внутри описанной окружности, то они лежат и внутри треугольника, поскольку при изогональном сопряжении три сегмента, ограниченные сторонами треугольника и дугами описанной окружности, переходят в три угла, вертикальных углам треугольника

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

Задача 6#85505

Дано натуральное число $n$ . Можно ли представить многочлен $x(x− 1)...(x − n)$ в виде суммы двух кубов многочленов с действительными коэффициентами?

Источники: Турнир городов - 2024, весенний тур, 11.1 (см. turgor.ru)

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

Подсказка 1

Ну если доказывать, что для любого многочлена подобного вида он всегда разложим в сумму двух многочленов-кубов, то либо конструктивно предъявлять два таких многочлена(и как вы потом будете доказывать, что они тождественно равны, уж не раскрывать ли скобки?), либо как-то в общем случае говорить, но тоже абсолютно непонятно как. Тогда, если сложно доказать ответ «Да», попробуем доказать ответ «Нет». Тогда пусть он представим в виде суммы двух многочленов-кубов. Если бы у нас были вместо многочленов числа, то можно было бы посмотреть на делимость чего-то на что-то, так как слева у нас произведение из условия, а правую часть можно разложить как сумму кубов. Попробуйте это сделать, ведь вам ничего не мешает говорить про делимость, только уже многочлена на многочлен!

Подсказка 2

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

Подсказка 3

Что эта скобка не разложима на линейные сомножители над R. То есть, ее нельзя представить в виде произведения скобок вида (x - k)^t. Осталось только посмотреть на степень неполного квадрата разности и на левую часть и понять, что мы решили задачу.

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

Предположим противное — существуют такие многочлены $f$ и $g$ , что выполнено тождество $x(x− 1)...(x − n)= f3+ g3$ .

_________________________________________________________________________________________________________________________________________________________________________________

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

У многочленов $f$ и $g$ нет общих корней, иначе это будет кратный корень суммы кубов, а у многочлена $x(x − 1)...(x− n)$ кратных корней нет.

Тогда многочлен $2 2 f − fg +g$ имеет степень $2max(degf,degg$ ) (старшие коэффициенты не сократятся) и не имеет корней, поскольку выражение $2 2 a − ab+b$ равно 0 только при $a= b=0$ . Но такого делителя у многочлена $x(x− 1)...(x − n)$ нет.

_________________________________________________________________________________________________________________________________________________________________________________

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

Применим формулу суммы кубов:

( ) x(x− 1)...(x − n)= (f + g) f2− fg+g2 .

При $x= 0,1,...,n$ имеем $3 3 f(x)= −g(x)$ , откуда $f(x)= −g(x)$ , то есть $f(x)+ g(x)= 0$ .

Значит, многочлен $f + g$ имеет корнями числа $0,1,2,...,n$ , откуда его степень не меньше $n +1$ (поскольку он не тождественный ноль). В частности, у одного из многочленов $f$ и $g$ степень не меньше $n +1$ — не теряя общности, пусть у $g$ . Тогда, из равенства (*), степень многочлена $f2− fg +g2$ равна 0 , то есть это ненулевая константа. Но это невозможно, так как из представления $f2− fg+ g2 =(f − 0,5g)2 +0,75g2$ видно, что у этого многочлена старшая степень не меньше, чем максимум из степеней многочленов $(f − 0,5g)2$ и $0,75g2$ , то есть, не меньше $2(n+ 1)$ . (Можно сказать иначе: $0,75g2$ принимает сколь угодно большие значения, откуда $(f − 0,5g)2+ 0,75g2$ - тоже, то есть, последний многочлен не может быть константой).

Ответ: нет

Курсы

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

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

Задача 7#85488

Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, $...$ , одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?

Источники: ММО - 2024, первый день, 11.6 (см. mmo.mccme.ru)

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

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

Рассмотрим всевозможные мелодии из нот до и си длины $13$ , коих $13 2$ штук. Каждую такую мелодию периодически продолжим в обе стороны, получив бесконечную в обе сторону мелодию. Назовём две получившиеся бесконечные мелодии эквивалентными, если одна получается из другой сдвигом.

Наименьший период всех бесконечных мелодий, кроме двух, состоящих только из нот до и только из нот си, равен $13.$ Количество не эквивалентных друг другу бесконечных мелодий равно

213− 2 --13--+ 2= 632

(каждой бесконечной мелодии $X$ периода $13$ эквиваленты $13$ мелодий (включая саму $X$ с периодом, который будет циклическим сдвигом $13$ нот, дающих мелодию $X$ )

Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше

(28+ 27 +...+ 21)+18= 528

(в скобках учтены запретные мелодии длины $≤ 12$ , полученные дописыванием $k$ символов к запретной мелодии длины $13− k$ , а за скобками — все остальные).

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

______________________________________________________________________________________________________________________________________________________

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

Пусть $Ln$ - число мелодий длины $n$ , не содержащих запретных последовательностей нот. Будем считать, что $L0 = 1.$ По индукции докажем, что $Ln+1 ≥ Ln+ Ln−1$ для всех натуральных $n$ .

База индукции $(n= 1):$ $L2 = 4≥ 2+ 1= L1+ L0.$

Предположим, что неравенство $Lk+1 ≥Lk +Lk−1$ верно для всех $k$ , меньших $n.$ Покажем, что тогда $Ln+1 ≥ Ln+ Ln−1.$ Заметим, что

Ln+1 ≥2Ln − Ln−4− Ln−5− ...− L0

Действительно, мы можем добавить в конец ноту двумя способами к уже имеющейся незапрещенной мелодии из $n$ нот. При добавлении ноты могла возникнуть запретная мелодия длины $5$ в конце последовательности, однако она "испортит"максимум $L n−4$ последовательности нот, так как первые $n− 4$ ноты до "запрещенной"мелодии - незапрещенная мелодия длины $n − 4$ . Аналогично могли получить запретную последовательность из $6$ нот и испортить разрешённую мелодию из $n− 5$ нот и т. д. (Здесь мы можем вычесть лишнее, если $n> 30$ , и часть вычитаемых мелодий могут быть одинаковыми, но поскольку мы пишем оценку снизу, всё правильно.)

Из предположения индукции для $k< n$ $(Lk+1 ≥Lk +Lk−1)$ также следуют неравенства:

Lk+1− Lk ≥Lk−1

Lk+1− Lk−1 ≥Lk

Применим эти следствия, а также неравенство выше, для доказательства перехода индукции и получим:

Ln+1 − Ln − Ln−1 ≥(Ln− Ln−1)− Ln−4 − Ln−5− Ln−6− ...L0 ≥

≥(L − L )− L − L − ...− L ≥ L − L − L − ...L ≥ n−2 n−4 n−5 n−6 0 n−3 n−5 n−6 0

≥ Ln−4− Ln− 6− ...− L0 ≥...≥L1 = 2> 0

Следовательно, $Ln+1 ≥ Ln+ Ln−1$ и переход доказан.

Тогда из-за положительности $L0,L1$ последовательность $Ln$ возрастающая, а значит $L300 > 0$ , откуда следует, что Иван справится с испытанием Кощея.

Ответ: да

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

Задача 8#67560

В ряд слева направо стоят $N$ коробок, занумерованных подряд числами $1,2,...,N$ . В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми. Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок № $i$ и № $j$ », где $i$ и $j$ — числа. Для каждого ли $N$ существует инструкция, в которой не больше $100N$ команд, со свойством: для любой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков?

Источники: Тургор-2023, 11.6 (см. www.turgor.ru)

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

Подсказка 1

Сразу вот такое наблюдение: у нас всего N коробок, а длина инструкции может быть 100N...Да и еще шарики в коробках лежат не наугад, а подряд, т.е. еще меньше вариаций для расположения шаров в коробках... На какой ответ в задаче это намекает?

Подсказка 2

Как будто всегда можно придумать такую инструкцию) А если мы доказываем что-то, что должно работать для любого натурального числа, то давайте доказывать это по индукции! А именно, будем доказывать, что для любого N существует нужная инструкция длины меньше чем 100N. Как можно это сделать?

Подсказка 3

База понятное дело проверяется, а вот что делать с переходом...Нам в нем, очевидно, нужно пользоваться меньшим числом K, для которого условие верно. Значит, нам нужно свести ситуацию для N к меньшей ситуации. То есть, по факту нужно перенести все шарики в меньший промежуток, где они также стоят подряд. Как это можно сделать и какой промежуток брать для этого?

Подсказка 4

Давайте мы будем переносить все в левую половину (если N = 2k, то в первые k коробок, если N = 2k+1, то в первые k+1 коробок). И самая важная идея: представьте, что в коробках, в которых есть шарики - синие шарики, а в которых нет мы положили красные шарики. То есть, нам нужно синие шары положить левее красных, но при таком условии мы можем сделать наоборот, и с помощью дополнительных инструкций поменять нам на нужную ситуацию)

Подсказка 5

Если сейчас в лоб не получается придумать как перетащить все шарики синие шарики в левую половинку, то вот что поймите: мы же можем перетащить любые шарики влево а оставшиеся будут справа, а после сделать ситуацию наоборот. Поэтому перетаскивайте те шары, которых меньше (и кстати, их будет <не больше k как раз).

Подсказка 6

Раз наших шаров не больше k, то значит в i-ой и k+i-ой коробкой не больше одного нужного шарика....Попробуйте применить это и раскрутить дальше, возможно добавив какие-то инструкции)

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

Давайте считать, что все шарики синие. В пустые коробки положим по красному шарику. Теперь пустых коробок нет. Покажем даже более сильное утверждение: что для любого $N$ есть инструкция не длиннее чем $3N$ со следующим свойством.

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

Воспользуемся методом математической индукции. Понятно, что для $N = 1$ такая инструкция есть. Это база индукции. Теперь покажем, как из инструкции для $k ≥1$ сделать инструкцию для $2k$ и для $2k− 1,$ этого будет достаточно. Обозначим $N = 2k$ или $2k− 1.$ Инструкция для $N$ будет выглядеть так:

I группа: сначала все пары вида $(i,k+ i)$ в любом порядке

Если $N$ нечетно, сюда приходится добавить все пары вида $(i+1,i+k)$ при $i≥1$ (назовём эти команды дополнительными).

II группа: инструкция для $k$ первых коробочек из индукционного предположения

III группа: все пары различных чисел вида $(i,N + 1− i)$ в любом порядке

При $N = 2k$ длина этой инструкции не превышает $k+ 3k +k =5k ≤3N.$

При $N = 2k− 1$ длина этой инструкции не превышает $2(k− 1)+3k+ (k − 1)=$ $= 6k− 3= 3N.$ Теперь почему она работает. Есть тот цвет, которого не больше $k$ , назовём его основным. Покажем, что можно выполнить часть инструкций I группы так, чтобы все шарики основного цвета лежали среди первых $k$ коробочек, и при этом конфигурация среди первых $k$ коробочек будет тоже непрерывной.

Есть четыре варианта того, как могут располагаться шарики основного цвета.

1) Они идут подряд, и все они среди левых $k$ коробок — ничего делать не надо;

2) Они идут подряд, и все они среди правых коробок — используем все пары вида $(i,k+ i)$ ;

3) Они есть и среди левых $k$ коробок, и среди остальных правых, при этом они идут подряд. Заметим, что ни в какой паре вида $(i,i+ k)$ нет двух шариков основного цвета. Все основные шарики тогда перенесем справа налево (тогда шарики не основного цвета будут среди первых $k$ шариков лежать подряд.

4) Шарики основного цвета — самые первые и самые последние. Перенеся последние влево (при нечётном $N$ используя дополнительные операции), получаем требуемое.

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

После этого применим часть инструкций II группы, чтобы среди первых $k$ коробочек слева оказались все шарики основного цвета.

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

Ответ: да

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

Задача 9#67559

Назовём рассадку $N$ кузнечиков на прямой в различные её точки $k$ -удачной, если кузнечики, сделав необходимое число ходов по правилам чехарды, могут добиться того, что сумма попарных расстояний между ними уменьшится хотя бы в $k$ раз. При каких $N ≥ 2$ существует рассадка, являющаяся $k$ -удачной сразу для всех натуральных $k$ ? (В чехарде за ход один из кузнечиков прыгает в точку, симметричную ему относительно другого кузнечика.)

Источники: Тургор-2023, 11.5 (см. www.turgor.ru)

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

Подсказка 1

Случай N=2 рассмотрите отдельно, он очевиден. Для всех N>2 попробуйте придумать пример такой рассадки.

Подсказка 2

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

Подсказка 3

На геометрическую прогрессию! Она и поможет нам придумать такую рассадку. Только вот рассадка 1, q, q^2, ... не очень то работает. Как можно подкорректировать координаты кузнечиков?

Подсказка 4

Давайте посадим кузнечиков в точки с координатами 0, 1, 1+q, 1+q+q^2, ... Какой тогда можно сделать первый ход, чтобы картинка стала подобна предыдущей (возможно, со сдвигом и с подбором нужного q)?

Подсказка 5

Нужно чтобы первый кузнечик перепрыгнул через второго и оказался на последнем месте! Отсюда мы получаем условие на q. И остаётся только одно: доказать, что найдётся q, удовлетворяющее этому условию, и притом оно будет из (0; 1).

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

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

Для любого $N > 2$ предъявим явно начальную рассадку, которая является $k$ -удачной для любого натурального числа $k.$

Сначала для данного $N > 2$ построим конечную геометрическую прогрессию $N−1 1,q,...,q ,$ со знаменателем $q ∈ (0,1),$ для которой выполнено условие

1= q+ q2 +⋅⋅⋅+ qN−1

Требуемый набор существует при любом целом $N > 2,$ поскольку уравнение

2 N−1 q+q + ⋅⋅⋅+ q − 1= 0

имеет решение на интервале $(0,1),$ так как левая часть меняет знак на его концах.

Расположим теперь $N$ кузнечиков в следующих начальных точках:

0,1,(1+ q),(1 +q+ q2),...,(1 +q+ ⋅⋅⋅+ qN−3),(1+ q+⋅⋅⋅+qN−2)

Рассмотрим прыжок первого кузнечика через второго; тогда его новая координата будет равна $2 =1 +1 =1+ q+ q2+⋅⋅⋅+qN−1.$ Получилось, что прыгнувший кузнечик стал самым правым, а все кузнечики теперь расположены в точках

1,(1+ q),(1+ q+q2),...,(1+q +⋅⋅⋅+ qN−2),(1+ q+ ⋅⋅⋅+qN− 1)

Сдвинув начало координат на 1 вправо, получим координаты кузнечиков

0,q,(q+ q2),...,(q+ ⋅⋅⋅+ qN −2),(q+⋅⋅⋅+qN−1)

Таким образом, кузнечики уменьшили свои координаты ровно в $1 q$ раз. Если указанный шаг (прыжок самого левого кузнечика через ближайшего соседа) повторять $r$ раз, то попарные расстояния уменьшатся в $-1 qr$ раз, что позволит достичь любого нужного уменьшения $-1. K$

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

При $N = 2$ как бы кузнечики ни прыгали, расстояние между ними не меняется.

Пусть $N ≥ 3.$ Рассадим 1-го, 2-го и 3-го кузнечиков на прямой в точках с координатами 0, 1, $√2,$ назовём этих кузнечиков $V,$ $Q,$ $R.$ Остальные произвольно рассаживаются в другие попарно различные точки. Покажем, что для всякого $k$ кузнечики далее смогут прыгать так, чтобы сумма попарных расстояний уменьшилась хотя бы в $k$ раз (исходную сумму обозначим через $P ).$

Лемма.

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

Доказательство леммы.

Покажем, что эти условия сохраняются при прыжке. Предположим, для некоторого кузнечика отношение расстояний до двух других рационально, тогда эти расстояния имеют вид $a$ и $aq,$ где $q$ рационально. Тогда расстояние между другими двумя кузнечиками ненулевое и имеет вид $|a± aq|,$ тогда отношение любых двух расстояний между кузнечиками рационально, противоречие. Пусть какой-то кузнечик перепрыгнул через кузнечика $A,$ тогда расстояния от $A$ до обоих кузнечиков не изменились, а значит, отношение этих расстояний осталось иррациональным, в частности расстояния различны, и потому кузнечики по-прежнему находятся в попарно различных точках.

Вернёмся к задаче.

Пусть первые несколько ходов будут прыгать только кузнечики $V,$ $Q,$ $R$ и только через друг друга, согласно лемме при таких прыжках они всегда будут оставаться в попарно различных точках. Покажем, что спустя любое количество таких ходов они смогут далее прыгать так, чтобы текущее минимальное из попарных расстояний между ними уменьшилось не менее чем в два раза.

Пусть, не умаляя общности, в текущий момент минимально расстояние между кузнечиками $V,$ $Q$ с координатами $a$ и $b,$ а $R$ имеет координату $c$ . Отметим на прямой все точки с координатами, отличающимися от $a$ на число, кратное $(a − b).$ Понятно, что прыгая друг через друга кузнечики $V,$ $Q$ смогут занять любые две соседние отмеченные точки, тогда $R$ не находится в отмеченной точке (по лемме прыгая только через друг друга $V,$ $Q,$ $R$ остаются в попарно различных точках), тогда $V$ , $Q$ могут занять две соседние отмеченные точки между которыми лежит $c,$ и расстояние от $R$ до одного из кузнечиков будет не более $12|a− b|,$ то есть наименьшее расстояние уменьшилось хотя бы в 2 раза.

Тогда за несколько ходов кузнечики $V,$ $Q,$ $R$ могут уменьшить наименьшее расстояние между ними хотя бы в 2 раза, потом за несколько ходов ещё хотя бы в 2 раза, потом ещё, и т.д, могут за несколько ходов добиться того, чтобы расстояние между какими-то двумя из них было равно некоторому числу $t$ , меньшему $----P----- 2N (N − 1)⋅k$ — пусть они так и сделают. Назовём каких-нибудь двух кузнечиков, между которыми расстояние $t,$ хорошими, и одного из них назовём $D,$ далее эти кузнечики уже не прыгают.

Далее, любой кузнечик не из пары хороших может прыгая через пару хороших (в подходящем порядке) смещаться на $2t$ в любую сторону на прямой, и тогда может за несколько прыжков через них оказаться на расстоянии меньшем $2t$ от $D,$ пусть все кузнечики кроме хороших сделают прыжки таким образом. Тогда расстояние от любого кузнечика до $D$ будет меньше $2t,$ а значит, все попарные расстояния меньше $4t,$ а значит, их сумма меньше $4t⋅N-(N-−-1)- P- 2 < k.$

Ответ:

при $N ≥ 3$

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

Задача 10#67558

Дан треугольник $ABC.$ Пусть $I$ — центр его вписанной окружности, $P$ — такая точка на стороне $AB,$ что угол $PIB$ прямой, $Q$ — точка, симметричная точке $I$ относительно вершины $A.$ Докажите, что точки $C,I,P,Q$ лежат на одной окружности.

Источники: Турнир городов - 2023, 11.4, авторы - И. Кухарчук, А.Юран

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

Подсказка 1

Условие на угол PIB выглядит немного странно...однако он входит в состав угла AIB (I - центр вписанной окружности, так еще нам и намекают число 90) Какой угол тогда хочется сразу посчитать?

Подсказка 2

Угол AIB на 90 больше половины угла ACB, а, значит, углы ACI и AIP равны. На картинке много биссектрис, которые могут помочь нам в поисках подобных треугольников. А еще хочется как-то пользоваться равенством отрезков QA и AI(мы этого еще не делали)

Подсказка 3

Треугольники CIA и IPA подобны по трем углам, а в них как раз присутствует отрезок IA, так что можем записать, что IC/IP = AC/AI = AC/AQ. Смотрим, какие же треугольники содержат отрезки IC, IP, AC, IQ (или хотя бы часть из них, чтобы дальше работать с подобием)?

Подсказка 4

Треугольники ICP и ACQ! Становится ясно: хотим равенства углов CIP и CAQ, чтобы доказать подобие треугольников с такими же названиями, чтобы доказать равенство углов IPC и AQC. Посчитать угол QAC как внешний к половине угла BAC несложно, а угол PIC есть сумма углов AIP и AIC. Осталось лишь воспользоваться знанием про углы с вершиной I из подсказки 2 ;)

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

$PIC$

Пусть $CI$ пересекает $AB$ в точке $N.$ Угол $AIB$ тупой, а угол $NIB$ острый, значит $P$ лежит между $A$ и $N.$ Далее, т.к. $I$ — центр вписанной окружности треугольника, получаем

∠AIP = ∠AIB − 90∘ = 1∠ACB = ∠ACI 2

∠CAI = ∠IAP

Значит, треугольники $CAI$ и $IAP$ подобны. Учитывая это и равенство $QA = AI,$ имеем

-IC-= P-I= P-I AC AI QA

Кроме того,

( ) ∠AIP + ∠AIC = 1∠ACB + 90∘+ 1∠ABC = 180∘− 1∠CAB 2 2 2

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

∘ 1 ∘ ∠PIC = 180 − 2∠CAB =180 − ∠CAI = ∠QAC

Тогда треугольники $QAC$ и $PIC$ подобны по углу и отношению прилежащих сторон, значит $∠IPC =∠AQC =∠IQC,$ и точки $C,I,P,Q$ лежат на одной окружности.

Замечание. После доказательства подобия треугольников $CAI$ и $IAP$ можно действовать по-другому. Выберем точку $R$ на продолжении отрезка $CA$ за точку $A$ так, что $AP =AR;$ тогда треугольники $IAP$ и $QAR$ равны ( $IA= QA,AP = AR,∠QAR = ∠CAI = ∠IAP$ ). Значит, $QRP I$ — равнобокая трапеция, и она вписана. С другой стороны, поскольку $∠CIQ = ∠CIA =∠CRQ,$ точки $C,I,R,Q$ лежат на одной окружности. Значит, все пять точек $C,I,P,Q,R$ лежат на окружности $(QRI).$

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

Задача 11#67557

В таблице $44× 44$ часть клеток синие, а остальные красные. Никакие синие клетки не граничат друг с другом по стороне. Множество красных клеток, наоборот, связно по сторонам (от любой красной клетки можно добраться до любой другой красной, переходя из клетки в клетку через общую сторону и не заходя в синие клетки). Докажите, что синих клеток в таблице меньше трети.

Источники: Турнир городов - 2023, 11.3, автор - Б. Френкин

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

Подсказка 1

В данной задаче нужно получить какие-то оценки на количество синих клеток. Для этого полезно некоторую величину посчитать двумя способами. Какую здесь удобно взять?

Подсказка 2

Будем считать число M общих сторон красных клеток с синими. Оценить M снизу довольно просто, как это можно сделать?

Подсказка 3

Так как синие клетки не граничат с синими, то каждая сторона синей клетки даёт вклад 1 в M, кроме...

Подсказка 4

Сторон синих клеток, примыкающих к краю таблицы. Но их количество легко оценить, и мы получим оценку снизу на M.

Подсказка 5

Теперь хочется получить оценку сверху. Ясно, что каждая красная клетка даёт вклад в M не больше 4, но эта оценка слишком грубая.

Подсказка 6

Опять же надо учесть, что стороны красных клеток, примыкающие к краю таблицы, не дают вклад в M, а их количество также легко оценить.

Подсказка 7

Мы так и не воспользовались одним из условий задачи (каким?). Оно поможет нам сделать оценку сверху ещё точнее.

Подсказка 8

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

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

Положим $N =44,$ и пусть $b$ и $r$ — количества синих и красных клеток. Оценим сверху количество $M$ общих сторон красных клеток с синими.

Всего у красных клеток $4r$ сторон, откуда $M ≤4r.$ Вдоль краёв таблицы стоит не меньше $2N$ сторон красных клеток, поэтому $M ≤ 4r− 2N.$ Теперь рассмотрим граф, вершины которого — красные клетки, а рёбра соединяют клетки, имеющие общую сторону. По условию граф связен, поэтому количество его рёбер не меньше $r− 1.$ Каждому из них отвечает общая сторона двух красных клеток, засчитанная в величине $4r$ два раза, поэтому из $M$ можно вычесть $2(r − 1).$ Получаем

M ≤4r− 2N − 2(r− 1)= 2r− 2N + 2

(1)

Оценим теперь $M$ снизу. Сложив количества сторон всех синих клеток, получим $4b.$ Ясно, что на одной стороне таблицы не больше $N ∕2$ сторон синих клеток. Поэтому

M ≥ 4b− 2N

(2)

Из (1) и (2) следует, что

4b− 2N ≤M ≤ 2r− 2N + 2

Поскольку $b+ r= N2,$ получаем отсюда

2 6b≤ 2N2+ 2⇒ b≤ N--+ 1 3 3

Поскольку $N2 =442 ≡ 1 (mod 3),$ а $b$ целое, получаем нужный результат.

Интенсивы

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

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

Задача 12#67556

Существует ли целое $n > 1$ , удовлетворяющее неравенству

[√---- √----] [√ ----] n − 2+ 2 n+ 2 < 9n+ 6?

(Здесь $[x]$ обозначает целую часть числа $x$ , то есть наибольшее целое число, не превосходящее $x$ .)

Источники: Тургор-2023, 11.2 (см. www.turgor.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Хм, можно оценить, что квадрат правой части (к слову, целой) не больше, чем 9n + 6. Подумаем, а когда в таком неравенстве достигается равенство?

Подсказка 4

Вообще, при равенстве получится, что квадрат целого числа даёт остаток 6 по модулю 9. Стоп, а такое вообще возможно?

Подсказка 5

Нет, квадраты чисел по модулю 9 не дают остаток 6! Более того, остаток 5 они тоже не дают, а вот остаток 4 уже может получиться. А тогда можно оценить правую часть более строго!

Подсказка 6

Действительно, получается, что квадрат правой части на самом деле не больше, чем 9n + 4, давайте преобразуем исходное неравенство, а дальше опять будем возводить в квадрат, остаётся надеяться, что в результате получится более содержательное неравенство

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

Предположим целое $n> 1$ удовлетворяет этому неравенству. Имеем

[√----]2 9n+ 6 ≤ 9n+ 6,

Но квадрат целого числа не может давать ни остаток 6, ни остаток 5 от деления на 9, значит,

[√-----]2 9n+ 6 ≤9n+ 4

[√-----] [√ ----] 9n+ 6 ≤ 9n +4

Тогда исходное неравенство влечёт неравенство

√n-− 2+ 2√n-+2< √9n-+4

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

∘ ----- 4 n2− 4< 4n− 2

1 n2− 4< n2− n+ 4

n <4,25

Однако, прямая проверка показывает, что при $n∈ {2,3,4}$ исходное неравенство не выполняется — противоречие.

Ответ: нет

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

Задача 13#67555

Дана треугольная пирамида $SABC$ , основание которой — равносторонний треугольник $ABC$ , а все плоские углы при вершине $S$ равны $α$ . При каком наименьшем $α$ можно утверждать, что эта пирамида правильная?

Источники: Тургор-2023, 11.1 (см. www.turgor.ru)

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

Подсказка 1

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

Подсказка 2

Верно, докажем, что при плоском угле 60 градусов наша пирамида окажется правильной. Нужно только понять, что если в треугольнике есть угол 60 градусов, то сторона напротив него средняя по величине между другими. Тогда предположив, что какое-то боковое ребро не равно ребру из основания, сможем получить противоречие и получить доказательство. Что же будет, если плоские углы будут меньше 60? Попробуйте построить пример неправильной пирамиды с таким углом, учитывая условия задачи и соотношения сторон по их размерам.

Подсказка 3

Давайте, рассмотрим равнобедренный треугольник SAB, в котором SA=SB и ∠S = α(α<60). Тогда сторона AB в нём наименьшая, и мы сможем его отложить на боковых сторонах. Осталось только понять, что отложив на рёбрах трёхгранного угла нужные отрезки(два из которых SA и SB) с плоскими углами меньше 60, мы получим неправильную пирамиду, то есть контрпример.

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

Докажем, что при $α = 60∘$ пирамида правильная. Пусть стороны треугольника $ABC$ равны 1. Заметим, что в любом треугольнике с углом $∘ 60$ против этого угла лежит средняя по длине сторона (причём если она строго меньше одной из сторон, то строго больше другой). Пусть одно из боковых рёбер пирамиды не равно 1: например, $SA > 1$ . Тогда в гранях $SAB$ и $SAC$ рёбра $SB$ и $SC$ будут меньше 1, и значит, в грани $SBC$ ребро $BC$ — не средняя сторона, противоречие.

Покажем теперь, как построить неправильную пирамиду с плоскими углами $∘ α< 60$ при вершине $S$ .

Первый способ. Сначала боковое ребро $SA$ удаляем, а неудалённую боковую грань $SBC$ вращаем вокруг её ребра основания $BC$ , пока эта грань не окажется в плоскости основания так, что будет содержать треугольник основания. В процессе движения будут «текущие» пирамиды, у которых два равных плоских угла сначала равны $α$ , потом больше $α$ (в момент, когда вершина проектируется в вершину основания — поскольку в этот момент синус угла при вершине $S$ в боковых гранях $SAC$ и $SAB$ равен $1:SB$ , а в грани $SBC$ равен отношению боковой высоты этого треугольника к $SB$ , которая меньше 1), а в конце у «вырожденной» пирамиды они равны $α2$ . Значит, в силу непрерывности, будет ещё раз $α$ .

Второй способ. Рассмотрим треугольник $SAB$ c $SA = SB$ и $∠S = α$ . Так как $AB < SB$ , на стороне $SA$ существует такая точка $C$ , что $BC =AB$ . Теперь возьмем трёхгранный угол, у которого все плоские углы равны $α$ , и отложим на его ребрах отрезки $SA$ , $SB$ , $SC$ . Пирамида $SABC$ — искомая.

Третий способ. Пусть $S′ABC$ — правильная пирамида с плоским углом $α$ при вершине $S′$ . Пусть $X$ , $Y$ — точки, такие, что $XY = AB$ , построим на $XY$ треугольники $XY Z$ и $XY T$ так, что $∠ZXY = ∠ZYX = 90∘ − α2$ , $∠TXY = 90∘ + α2$ , $∠TYX = 90∘ − 3α2$ , тогда понятно что $∠XT Y = ∠XZY = α$ . В силу теоремы синусов для этих треугольников имеем

---T∘Y-α--= XY--= ---ZX∘--α-= ----ZY∘--α-, sin(90 +2 ) sinα sin(90 − 2) sin(90 − 2)

что влечёт $TY = ZX =ZY$ , поскольку синусы смежных углов равны. Пусть теперь $S$ — такая точка на продолжении отрезка $S′B$ за точку $B$ , что $SB = TX$ . Тогда $∠SBC =∠SBA =90∘+ α= ∠TXY 2$ , $BC = BA = XY$ , и $SB =T X$ , тогда $△SBC = △SBA = △T XY$ , откуда $SC =SA = TY =ZX =ZY$ , и значит $△SCA = △ZXY$ (по трём сторонам). Из всех указанных равенств треугольников следует, что у пирамиды $SABC$ все плоские углы при вершине $S$ равны $α$ , значит она удовлетворяет условиям задачи. Но она не правильная, поскольку прямая $′ S B$ не перпенидикулярна $ABC$ , и на ней только одна точка проецируется в центр треугольника $ABC$ , это точка $′ S$ , а значит не точка $S$ .

Ответ:

$60∘$

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

Задача 14#82168

Дан отрезок $AB.$ Точки $X, Y, Z$ в пространстве выбираются так, чтобы $ABX$ был правильным треугольником, а $ABY Z$ – квадратом. Докажите, что ортоцентры всех получающихся таким образом треугольников $XY Z$ попадают на некоторую фиксированную окружность.

Источники: Турнир городов - 2022, осенний тур, базовый вариант, 11.4

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

$PIC$

Пусть $M$ — середина $AB, N$ — середина $YZ.$ Рассмотрим плоскость $AXB.$ Заметим, что прямая $AB$ перпендикулярна прямым $XM$ и $MN,$ а значит она перпендикулярна плоскости $XMN.$ Следовательно, $XMN ⊥ ABY.$ Нетрудно видеть, что при симметрии относительно плоскости $XMN$ отрезок $XZ$ перейдёт в отрезок $XY,$ то есть $XY = XZ.$ Таким образом, ортоцентр $H$ треугольника $XY Z$ лежит на отрезке $XN$ — серединном перпендикуляре $Y Z.$

Покажем, что $H$ лежит на окружности $ω$ с центром $M,$ радиусом $XM,$ лежащей в плоскости $XMN.$ Для этого определим на отрезке $MN$ точку $T$ такую, что $MT =XM,$ и точку $S$ — вторичное пересечение прямой $MN$ с $ω.$ Осталось посчитать, что четырёхугольник $SMHX$ — вписанный, то есть доказать равенство $NT ⋅NS = NH ⋅NX.$

Пусть длина стороны квадрата и правильного треугольника равна $2a.$ Из подобия треугольников $HNZ$ и $NXZ$ нетрудно получить, что $NH ⋅NX =a2.$ Также понятно, что $NT =MN − XM = (2 − √3)a,NS =MN +XM = (2 +√3)a,$ откуда $NT ⋅NS = a2.$ Получили нужное равенство.

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

Задача 15#76741

Дан отрезок $[0;1]$ . За ход разрешается разбить любой из имеющихся отрезков точкой на два новых отрезка и записать на доску произведение длин этих двух новых отрезков. Докажите, что ни в какой момент сумма чисел на доске не превысит $1 2$ .

Источники: Турнир городов - 2022, осенний тур, базовый вариант, 11.5

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

Подсказка 1

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

Подсказка 2

Верно, в итоге, у нас получится сумма всевозможных попарных произведений отрезков. База понятна, а дальше нужно по аналогии в сумме заменить длину вновь разбитого отрезка через сумму двух новых. Отлично, с этим справились! Заметим, что нам известна сумма всех отрезков. Как можно выразить теперь сумму попарных произведений для удобной оценки?

Подсказка 3

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

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

Пусть через $n$ шагов мы поделили отрезок на отрезки $x ,x,...,x 1 2 n$ . Индукцией по $n$ покажем, что сумма чисел, записанных на доске, равна сумме всевозможных попарных произведений чисел $x1,x2,...,xn$ .

База очевидна.

Переход: Пусть на $n−$ шаге сумма равна $x1x2+ ...+ xn−1xn$ . На $n+ 1$ -м шаге мы делим $i$ -й отрезок на отрезки $a$ и $b$ , тогда сумма примет вид:

x1x2+ ...+ xn−1xn+ (a+ b)(x1+ x2+...+xn)+ ab

В данном случае $xx + ...+ x x 1 2 n−1n$ — попарные произведения чисел $x,x ,...,x 1 2 n$ без $x i$ , а $x + x + ...+x 1 2 n$ — сумма этих же чисел без $xi$ . Таким образом, на $n+ 1$ -м шаге также получили всевозможные попарные произведения.

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

(x1+ x2+...+xn)2− (x2+ x2+...+x2) x1x2+ ...+xn−1xn =----------------2--1---2------n- =

2 2 2 = 1−-(x1+-x2+-...+xn)-< 1. 2 2

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

Задача 16#76585

На доске написана буква А. Разрешается в любом порядке и количестве: а) приписывать А слева; б) приписывать Б справа; в) одновременно приписывать Б слева и А справа. Например, БААБ так получить можно ( А $→$ БАA $→$ БААБ), а АББА — нельзя. Докажите, что при любом натуральном $n$ половину слов длины $n$ получить можно, а другую половину — нельзя.

Источники: Турнир городов - 2022, 11.6 (см. www.turgor.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Посчитайте, сколько есть слов вида AWБ. Заметим, что именно такое количество слов посчитано дважды :)

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

Назовем слова, которые можно получить, достижимыми. Всего существует $2n$ различных слов длины $n,$ поэтому достаточно доказать, что количество достижимых слов длины $n$ равно $n−1 2 .$ Докажем это утверждение по индукции.

База индукции. Для $n =1$ и $n =2$ это легко проверяется: А $→$ АА, А $→$ АБ.

Шаг индукции. Пусть для всех длин, не превосходящих $n,$ утверждение верно. Посмотрим, как можно получить слово длины $n +1:$

1.: из слова длины $n,$ применив операцию а): W $→$ АW
2.: из слова длины $n,$ применив операцию б): W $→$ WБ
3.: из слова длины $n − 1,$ применив операцию в): W $→$ БWА

Слов 1-го и 2-го типа по $2n−1,$ а слов 3-го типа $− 2n−2.$ При этом слова 3-го типа не могут совпадать со словами 1-го и 2-го типа. А вот множества слов 1-го и 2-го типа пересекаются. Их общие слова имеют вид А $w$ Б. Докажем, что слова $w$ (которые находятся между буквами А и Б) — это все достижимые слова длины $n − 1.$ Понятно, что если $w$ — достижимое слово, то за две операции из него можно получить А $w$ Б. С другой стороны, если слово $w$ Б достижимое, то посмотрим, как оно было получено. Если проделать все те же операции, но пропустить приписывание последней буквы Б, то будет получено слово $w,$ значит, оно достижимое.

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

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

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

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

Задача 17#76584

На доске написана функция $sinx +cosx.$ Разрешается написать на доске производную любой написанной ранее функции, а также сумму и произведение любых двух написанных ранее функций, так можно делать много раз. В какой-то момент на доске оказалась функция, равная для всех действительных $x$ некоторой константе $c.$ Чему может равняться $c?$

Источники: Турнир городов - 2022, 11.4 (см. www.turgor.ru)

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

Подсказка 1

Для начала давайте попробуем взять несколько производных, перемножить что-нибудь — в общем, сделать несколько итераций. Видно, что все, что окажется на доске - многочлены от sin(x) и cos(x). Это можно и нужно доказать, но давайте сначала идейно. Если мы уже пощупали как себя ведут выражения, то может нам теперь попытаться что-то явно получить? Какую-то константу, к примеру.

Подсказка 2

Заметим, что эту константу только синусом или только косинусом не получить. Давайте возьмем f(x) = cos(x) + sin(x) и посмотрим на производные. Заметим, что f(x) * f(x) + f’(x) * f’(x) = 2. То есть все целые, четные значения, больше 0, мы можем получить. А что с целыми, четными и меньшими 0?

Подсказка 3

Верно, их тоже можно получить, к примеру, как сумму f(x) * f’’(x) + f’(x) * f’’’(x) = -2. Но ведь это всего лишь целые, и то не все. Попробовав так по складывать, да по умножать, можно понять эмпирически, что нечетные целые не получить, а уж что делать с не целыми и ума не приложить. В таких моментах не стоит ничего говорить, а только попытаться доказать, что это невозможно. Как? А мы использовали где-то наши рассуждения про многочлен? Может быть самое время?

Подсказка 4

Мы же можем посмотреть на значение в нуле. Ведь, тогда и sin(x), и cos(x) - целые числа. Значит, и многочлен от них - целое число в этой точке, а значит, если он тождественно константа, то эта константа - целая. Тогда, остается доказать про нечетные целые числа, что их нельзя получить. Давайте сделаем такой трюк. Если у нас все выражается через sin и cos, то это значит, что все выражается через sin(x) + cos(x) и sin(x) - cos(x). Но эти числа равны sqrt(2) * cos(x - pi/4) и sqrt(2) * sin(x - pi/4). Появилась иррациональность. А у нас только целые числа могут быть. Что из этого можно выгадать?

Подсказка 5

А в общем-то, все, что нам и нужно. Ведь если подставить pi/4, то получим, что при нечетных степенях, у cos будет либо иррациональный коэффициент, либо нулевой. А это значит, что сумма коэффициентов перед нечетными степенями равна 0), но ровно это и означает, что значение четно. Победа.

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

Любая функция, полученная описанным способом, — многочлен от $sinx$ и $cosx$ с целыми коэффициентами. Доказательство индукцией по числу шагов: исходная функция имеет такой вид; производная многочлена с целыми коэффициентами — многочлен с целыми коэффициентами; аналогичное верно для суммы и произведения. При $x= 0$ синус и косинус принимают целые значения, поэтому значение многочлена от них с целыми коэффициентами — целое, то есть $c$ целое.

Положим

f(x)= sinx+ cosx

Запишем на доску

′ f (x)= cosx− sinx

′′ f (x)= − sinx − cosx

f′′′(x)= − cosx+ sinx

Тогда

f2(x)+f′2(x)= (sin x+cosx)2 +(cosx − sinx)2 = 2

Аналогично

f(x)f′′(x)+ f′(x)f′′′(x)= −2

Суммируя такие функции, получаем все чётные константы.

Покажем, что нечётную константу получить нельзя. Заметим, что

(π ) π ( π) √- ( π) sinx+ cosx =sin x+ sin 2 − x = 2sin 4 cos x− 4 = 2 cos x− 4

Поэтому все функции, которые можно получить, — это многочлены от $√- ( ) 2cosx− π4$ и $√- ( ) 2 sin x− π4$ с целыми коэффициентами и нулевым свободным членом. При $x= π4$ остаются лишь члены с косинусом (равным 1). Коэффициенты при чётных степенях косинуса чётны, а при нечётных либо иррациональны, либо равны нулю. Целочисленное значение получится, если сумма коэффициентов при нечётных степенях равна 0, но тогда значение чётно, что и требовалось доказать.

Ответ:

Любому чётному числу.

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

Задача 18#76583

Дан клетчатый квадрат $n× n,$ где $n> 1.$ Кроссвордом будем называть любое непустое множество его клеток, а словом — любую горизонтальную и любую вертикальную полоску (клетчатый прямоугольник шириной в одну клетку), целиком состоящую из клеток кроссворда и не содержащуюся ни в какой большей полоске из клеток кроссворда (ни горизонтальной, ни вертикальной). Пусть $x$ количество слов в кроссворде, $y$ — наименьшее количество слов, которыми можно покрыть кроссворд. Найдите максимум отношения $x y$ при данном $n.$

Источники: Турнир городов - 2022, 11.3 (см. www.turgor.ru)

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

Подсказка 0

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

Подсказка 1

Для начала получим оценку. Рассмотрим, ско́льким словам может принадлежать одна клетка. Сколько среди них может быть вертикальных и горизонтальных? Сколько могут не принадлежать минимальному разложению?

Подсказка 2

Верно, каждая клетка содержится максимум в одном горизонтальном и одном вертикальном слове. Назовём слова из минимального покрытия кроссворда правильными, все остальные - неправильными. Каждая клетка должна принадлежать хотя бы одному правильному слову. Что тогда можно сказать об общем количестве клеток в неправильных словах?

Подсказка 3

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

Подсказка 4

Так как слова, состоящие из одной клетки точно правильные, то в одном неправильном слове хотя бы 2 клетки. Аналогично найдём количество правильных слов: сначала выясним, сколько суммарно букв в правильных словах (воспользуемся тем, что правильные слова покрывают все клетки) и поделим на минимальное количество букв в одном правильном слове.

Подсказка 5

Остаётся только найти искомое отношение и составить подходящий пример. Такой случай легко находится, если вспомнить, что максимальное количество неправильных слов достигается, когда в одном неправильном слове 2 клетки.

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

Пример. Для прямоугольника $n ×2$ получаем $x =n +2,y = 2.$

Оценка. Пусть в кроссворде $z$ клеток. Выберем некоторое его покрытие наименьшим количеством слов. Слова из этого покрытия назовём правильными, а остальные неправильными.

Каждая клетка содержится не более чем в одном горизонтальном и одном вертикальном слове. Хотя бы одно из этих слов правильное, так как правильные слова покрывают весь кроссворд. Значит, каждая клетка принадлежит не более чем одному неправильному слову. Поэтому сумма количеств клеток в неправильных словах не больше $z.$

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

Так как правильные слова покрывают весь кроссворд, сумма количеств клеток в них не меньше $z.$ Каждое слово содержит не больше $n$ клеток, поэтому количество правильных слов не меньше $z n$ Отсюда

z xy ≤ 1+ 2z-=1 + n2 n

Ответ:

$1+ n 2$

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

Задача 19#76582

Назовём расположенный в пространстве треугольник $ABC$ удобным, если для любой точки $P$ вне его плоскости из отрезков $PA,PB$ и $P C$ можно сложить треугольник. Какие углы может иметь удобный треугольник?

Источники: Турнир городов - 2022, 11.2 (см. www.turgor.ru)

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

Подсказка 1

Если поразмыслить над этой задачей, порисовать какие-то треугольники и точки Р, можно понять, что если брать точку Р очень близко к одной из вершин (допустим, к А), выполнение неравенства треугольника для РА, РВ, РС сводится к тому, что АВ и АС не могут быть сильно отличны по длине.

Подсказка 2

Конечно, мысли из первой подсказки нужно формализовать. Тогда мы придем к тому, что если условие задачи выполнено, то треугольник АВС равносторонний. Теперь для равностороннего треугольника нужно доказать, что для любой точки P условие задачи выполнено.

Подсказка 3

Доказывать это можно по-разному. Один из способов (красивый) — явно построить треугольник со сторонами, равными PA, PB и РС, используя подобия.

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

Докажем сначала, что неравносторонний треугольник под условие подходить не может. Предположим противное, пусть такой треугольник $ABC$ есть и в нём $AB ⁄= AC,$ причём длины этих сторон различаются хотя бы на $d.$

Рассмотрим точку $P,$ расположенную на перпендикуляре к плоскости $ABC,$ проходящем через точку $A,$ на расстоянии $𝜀$ от $A.$ Тогда

∘ ------- ∘ ------- PB = AB2+ 𝜀2, PC = AC2 +𝜀2

Можно выбрать $P$ настолько близко к вершине $A,$ уменьшая $𝜀,$ чтобы $PB$ и $P C$ отличались соответственно от $AB$ и $AC$ меньше, чем на $d∕3,$ и чтобы $𝜀$ было меньше $d∕3.$ Тогда стороны $PB$ и $P C$ будут различаться более чем на $d∕3,$ а длина стороны $P A$ меньше $d∕3$ — противоречие с неравенством треугольника.

Покажем теперь, что равносторонний треугольник удобен. Пусть $AB = BC =CA.$ Отметим на лучах $PA,PB,P C$ точки $A1,B1,C1$ так, чтобы выполнялись равенства:

AB ⋅P A1 = PB ⋅PC

BC ⋅PB1 = PC ⋅PA

CA ⋅PC1 = PB ⋅PA

Треугольники $APB$ и $B1P A1$ подобны по углу и отношению двух сторон, откуда

AB-⋅P-A1 A1B1 = PB = PC

Аналогично вычисляем длины остальных сторон. Получаем, что треугольник $A1B1C1$ — искомый.

Ответ:

$60∘,60∘,60∘$

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

Задача 20#76581

Многочлен третьей степени имеет три различных корня строго между 0 и 1. Учитель сообщил ученикам два из этих корней. Ещё он сообщил все четыре коэффициента многочлена, но не указал, в каком порядке эти коэффициенты идут. Обязательно ли можно восстановить третий корень?

Источники: Турнир городов - 2022, 11.1 (см. www.turgor.ru)

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

Подсказка 1

Нам известны 2 корня и все коэффициенты в каком-то порядке! Все корни меньше единицы, но больше 0. Что тогда можно сказать про коэффициенты и их сравнения относительно друг друга?

Подсказка 2

Да, свободный член наименьший по модулю и при этом, знаки у коэффициентов чередуются! В таком случае, что можно сказать исходя из теоремы Виета?

Подсказка 3

Верно, по теореме Виета для b и d, которые мы знаем, можно найти a! А дальше уже можно найти и оставшийся корень.

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

Пусть $a,b,c,d$ — коэффициенты многочлена от старшего к младшему, $α,β$ — известные корни, $γ$ — неизвестный корень. Прежде всего заметим, что так как все корни между 0 и 1, то в силу теоремы Виета коэффициент $d$ — наименьший из коэффициентов по абсолютной величине.

Поскольку все корни многочлена положительны, знаки коэффициентов чередуются. Поэтому, зная $d,$ определяем $b.$ Если найти $a,$ то определяется и $c.$ Заметим, что по Виета