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

Второе решение. Нарисуем графики движения мальчиков по дорожке : на горизонтальной оси отмечаем время \(t\), на вертикальной-положение \(y\) мальчика, считая от начала дорожки.

Пусть \(P_{0}, P_{1}, P_{2}\) - точки, соответствующие старту Пети, моменту, когда он перешёл с асфальтового участка на песчаный, и его финишу; пусть \(V_{0}, V_{1}, V_{2}\) - аналогичные точки для Васи. Тогда графики движения мальчиков-это ломаные \(P_{0} P_{1} P_{2}\) и \(V_{0} V_{1} V_{2}\), при этом

Рис. 1 отрезки \(P_{0} V_{0}, P_{1} V_{1}\) и \(P_{2} V_{2}\) горизонтальны (см. рис. 1). По условию, середины отрезков \(P_{0} P_{1}\) и \(V_{0} V_{1}\) совпадают, откуда \(P_{0} V_{0} P_{1} V_{1}\) - параллелограмм. Аналогично, \(P_{1} V_{1} P_{2} V_{2}\) - параллелограмм. Значит, отрезки \(P_{0} V_{0}, V_{1} P_{1}\) и \(P_{2} V_{2}\) параллельны и равны. Поэтому между моментами финиша Пети и Васи прошло столько же времени, сколько и между моментами их старта; отсюда и следует ответ.

Многоугольник, у которого площадь (измеренная в см²) численно равна периметру (измеренному в см), назовём хорошим.

Заметим, что исходный треугольник-хороший : он прямоугольный с катетами 5 см и 12 cm , поэтому его площадь равна \(30 \mathrm{~cm}^{2}\) и численно совпадает с его периметром, равным \(5 + 12 + 13 = 30\) см.

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

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

Один из многих возможных примеров показан на рисунке.

Предположим, такие три числа найдутся. Поскольку \(a\) кратно \(b + c\), сумма \(a + (b + c) = 2023\) также кратна \(b + c\), из чего следует, что \(b + c\) нечётно. Значит, \(b - c + 1-\) чётное число, и нечётное число \(b + c\) не может на него делиться.

Первое решение. Так как многочлен \( \left(x - a_{1}\right)\left(x - a_{2}\right)\left(x- a_{3}\right) - b \) имеет старший коэффициент 1 и корни \(c_{1}, c_{2}, c_{3}\), то \(\left(x - a_{1}\right)\left(x - a_{2}\right)\left(x - a_{3}\right)-b = \left(x - c_{1}\right)\left(x - c_{2}\right)\left(x - c_{3}\right)\). Подставим \(-x\) в последнее равенство вместо \(x\), получим \(\left(-x - a_{1}\right)\left(-x - a_{2}\right)(- \left.-x - a_{3}\right)-b = \left(-x - c_{1}\right)\left(-x - c_{2}\right)\left(-x - c_{3}\right)\), что равносильно \(\left(x + a_{1}\right)\left(x + a_{2}\right)\left(x + a_{3}\right) + b = \left(x + c_{1}\right)\left(x + c_{2}\right)\left(x + c_{3}\right)\). Из полученного равенства получаем, что тремя корнями уравнения \(b = (x + \left. + c_{1}\right)\left(x + c_{2}\right)\left(x + c_{3}\right)\) являются числа \(-a_{1},-a_{2},-a_{3}\).

Второе решение. По теореме Виета выполняются следующие соотношения : \(\begin{array}{c} c_{1} + c_{2} + c_{3} = a_{1} + a_{2} + a_{3} \\ c_{1} c_{2} + c_{2} c_{3} + c_{3} c_{1} = a_{1} a_{2} + a_{2} a_{3} + a_{3} a_{1} \\ c_{1} c_{2} c_{3} = a_{1} a_{2} a_{3}-b \end{array}\)

Эти же равенства можно переписать следующим образом : \(\begin{aligned} \left(-a_{1}\right) + \left(-a_{2}\right) + \left(-a_{3}\right) & = \left(-c_{1}\right) + \left(-c_{2}\right) + \left(-c_{3}\right) \\ a_{1} a_{2} + a_{2} a_{3} + a_{3} a_{1} & = c_{1} c_{2} + c_{2} c_{3} + c_{3} c_{1} \\ -a_{1} a_{2} a_{3} & = -c_{1} c_{2} c_{3}-b \end{aligned}\)

из чего следует, что числа \(-a_{1},-a_{2}\) и \(-a_{3}\) являются корнями уравнения \(\left(x + c_{1}\right)\left(x + c_{2}\right)\left(x + c_{3}\right)-b = 0\).

поэтому \(A_{3} = \left\{z_{1}, z_{2}, y_{2}, y_{3}, \ldots, y_{29}\right\}\). Рассмотрим любое подмножество \(A_{i}\) из подмножеств \(A_{4}, \ldots, A_{50}\). Предположим, что \(A_{i}\) содержит элемент, лежащий вне 31-элементного множества \(K = \left\{z_{1}, z_{2}, y_{1}, y_{2}, \ldots, y_{29}\right\} = A_{1} \cup A_{2} \cup A_{3}\). Тогда \(A_{i}\) должно пересекаться с каждым из подмножеств \(A_{1}, A_{2}, A_{3}\) по одному и тому же 29-элементному подмножеству множества \(K\). Но \(\left|A_{1} \cap A_{2} \cap A_{3}\right| = 28\), значит, такого 29-элементного подмножества не существует-противоречие. Отсюда делаем вывод, что все множества \(A_{1}, A_{2}, \ldots, A_{50}\) являются подмножествами множества \(K\). Но в множестве \(K\) количество 30-элементных подмножеств равно \(31 < 50\). Получаем противоречие, завершающее решение задачи.

Заметим, что в каждой вертикали и каждой горизонтали стоит ровно по одной ладье.

Покажем сначала, что все \(2 n\) ладей не могли попасть в одну часть. Пусть \(A, B, C, D\) - угловые клетки доски (в порядке обхода против часовой стрелки, см. рис. 2). Из симметрии, \(A\) и \(C\) должны принадлежать разным частям, как и \(B\) и \(D\). Это значит, что либо \(A\) и \(B\), либо \(A\) и \(D\) лежат в одной части, а остальные две клетки-в другой.

Пусть для определённости \(A\) и \(B\) лежат в части I. Тогда все граничные клетки между ними также должны лежать в части I; действительно, если какая-то такая клетка \(X\) лежит в части II, то в ней же лежит какой-то путь из \(X\) в \(C\), а в части I лежит какой-то путь из \(A\) в \(B\); но эти пути должны иметь общую клетку, что невозможно.

Значит, вся горизонталь между клетками \(A\) и \(B\) лежит в части I , то есть в ней должна быть хотя бы одна ладья. Аналогично, в части II тоже есть целая горизонталь (между \(C\) и \(D\) ), а значит, есть ладья. Отсюда и следует требуемое.

Осталось привести пример, когда в одной из частей расположено \(2 n - 1\) ладей. Один из возможных

Рис. 2

примеров устроен так. Рассмотрим диагональ квадрата; в одну часть попадут клетки ниже неё, а также нижняя половина самой диагонали; остальные клетки попадут во вторую часть. Расставим \(2 n - 1\) ладью в клетки непосредственно под диагональю; тогда они окажутся в одной части. Оставшуюся ладью поставим в пересечение оставшихся строки и столбца. На рис. 2 указан такой пример при \(n = 5\).

Замечание. Ключевым соображением в оценке является следующее : Если на границе выбраны четыре клетки \(P, Q, R\), \(S\), обозначенные в порядке обхода, то любой путь между \(P\) и \(R\) имеет общую клетку с любым путём между \(Q\) и \(S\).

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

Первое решение. Предположим противное : пусть \(b \geqslant c + 1\). Из делимости \(a b c + 1\) на \(a b - b + 1\) следует, что число \(b(a c - a + + 1) = (a b c + 1)-(a b - b + 1)\) кратно \(a b - b + 1\). Поскольку числа \(b\) и \(a b - b + 1 = b(a - 1) + 1\) взаимно просты, получаем, что \(a c - a + 1\) делится на \(a b - b + 1\). Ясно, что \(a c - a + 1 > 0\), поэтому либо \(a c - a + 1 = a b - b + 1\), либо \(a c - a + 1 \geqslant 2(a b - b + 1)\).

В первом случае получаем \(b = a(b - c + 1)\) и, значит, \(b\) делится на \(a\), что невозможно по условию. Во втором случае имеем

\(a c - a \geqslant 2 b(a - 1) + 1 > 2 b(a - 1) > 2 c(a - 1)\)

то есть \(a c < 2 c - a < 2 c\). Это значит, что \(a < 2\), то есть \(a = 1\); но это также невозможно по условию, ибо тогда снова \(b\) делится на \(a\).

Второе решение. Опять же предположим противное. Поскольку \(a b c + 1\) делится на \(a b - b + 1\), то и \(b c - c + 1 = (a b c + 1)- -c(a b - b + 1)\) тоже кратно \(a b - b + 1\), то есть \(b c - c + 1 = k(a b - b + 1)\) при некотором натуральном \(k\). Иначе говоря,

\(0 = (b c - c + 1)-k(a b - b + 1) = b(c - k a + k)-(k + c - 1) .( * )\)

Значит, \(k + c - 1\) делится на \(b\).

По нашему предположению, \(c < b\). С другой стороны, поскольку \(a > 1\) (иначе \(b\) делится на \(a\) ), имеем

\(b c - c + 1 = c(b - 1) + 1 < b^{2} < b(b + 1) \leqslant b(b(a - 1) + 1)\)

откуда \(k < b\). Значит, \(0 < k + c - 1 < 2 b\), и потому \(k + c - 1 = b\).

Теперь ( * ) переписывается в виде \(0 = b(c - k a + k)-b\), то есть \(c - k a + k - 1 = 0\). Но тогда \(k a = k + c - 1 = b\), то есть \(b\) делится на \(a\). Это невозможно.

Обозначим окружности с диаметрами \(A B\) и \(C D\) через \(\omega_{1}\) и \(\omega_{2}\) соответственно. Заметим, что точка \(S\) лежит на отрезке \(M N\).

Пусть прямые \(C S\) и \(D S\) пересекают \(\ell\) в точках \(P\) и \(Q\) соответственно (см. рис. 3). Поскольку \(C D\) - диаметр \(\omega_{2}\), имеем \(\angle P S Q = \angle C S D = 90^{\circ}\). В прямоугольном треугольнике \(P S Q\) отрезок \(S M\) - высота, поэтому \(\angle M S P = 90^{\circ}-\angle S P M = \angle S Q P\). С другой стороны, поскольку \(N S = N C\), имеем \(\angle S C D = \angle C S N = = \angle M S P\). Итак, \(\angle S C D = \angle M S P = \angle S Q P\), то есть точки \(P, Q\), \(C\) и \(D\) лежат на одной окружности \(\gamma^{\prime}\).

Пусть теперь прямая \(M C\) пересекает окружности \(\gamma\) и \(\gamma^{\prime}\) в точках \(X\) и \(X^{\prime}\) соответственно (точка \(M\) лежит на отрезках \(C X\) и \(C X^{\prime}\) ). Тогда \(M C \cdot M X = M A \cdot M B = M S^{2}\), поскольку \(M\) - центр окружности \(\omega_{1}\). С другой стороны, \(M C \cdot M X^{\prime} = = M P \cdot M Q = M S^{2}\); последнее равенство опять же вытекает из того, что \(S M\) - высота в прямоугольном треугольнике \(P S Q\). Значит, \(M C \cdot M X = M S^{2} = M C \cdot M X^{\prime}\), то есть \(X = X^{\prime}\). Но точка \(X\) отлична от \(C\) и \(D\), так как \(M\) не лежит на \(C D\); значит,

окружности \(\gamma\) и \(\gamma^{\prime}\) имеют три общих точки \(C, D, X\), то есть они совпадают. Поэтому \(P\) лежит на \(\gamma\), что и требовалось доказать.

Рис. 3

Рис. 4

Замечание 1. Решение можно было бы завершить многими разными способами. Например, равенства \(M P \cdot M Q = = M S^{2} = M A \cdot M B\) означают, что точки \(P, Q, A\) и \(B\) лежат на одной окружности \(\delta\). Тогда либо окружности \(\gamma, \gamma^{\prime}\) и \(\delta\) совпадают, либо это три разных окружности. Во втором случае радикальные оси этих трёх окружностей должны пересекаться в одной точке или быть параллельными; но эти радикальные оси это прямые \(P Q, A B\) и \(C D\), и для них эти утверждения неверны.

Рассуждение выше имеет недостаток : оно не проходит в случае, когда точки \(P, Q, A\) и \(B\) лежат на одной прямой. Этот случай легко разобрать отдельно (тогда \(M N\) проходит через центр окружности \(\gamma, A B \| C D\) и \(A C \perp B D\) ).

Замечание 2. Существуют и другие решения, идейно схожие с приведённым выше. Например, можно рассуждать так.

Пусть лучи \(C S\) и \(D S\) пересекают \(\gamma\) повторно в точках \(P^{\prime}\) и \(Q^{\prime}\) (см. рис. 4). Пусть \(M^{\prime} = P^{\prime} Q^{\prime} \cap M N\). Тогда \(\angle D Q^{\prime} P^{\prime} = = \angle D C S = \angle C S N = \angle M^{\prime} S P^{\prime}\), откуда \(M N \perp P^{\prime} Q^{\prime}\). Тогда \(S M^{\prime}\) - высота в прямоугольном треугольнике, и \(M^{\prime} P^{\prime} \cdot M^{\prime} Q^{\prime} = M^{\prime} S^{2}\). С другой стороны, если прямая \(M N\) пересекает \(\gamma\) в точках \(K\) и \(L\), то \(M^{\prime} K \cdot M^{\prime} L = M^{\prime} P^{\prime} \cdot M^{\prime} Q^{\prime} = M^{\prime} S^{2}\). Однако, как нетрудно проверить, на отрезке \(K L\) есть только две точки \(X\) такие, что \(X K \cdot X L = X S^{2}\), и это точки \(X = M\) и \(X = N\). Значит, \(M^{\prime} = M\), что и требовалось доказать.

Предположим противное. Пусть \(S_{m + 1}\) делится на \(2^{s}\), но не делится на \(2^{s + 1}\); тогда \(s \geqslant 2\). Это значит, что среди чисел \(1,2, \ldots, m + 1\) есть число \(a\), делящееся на \(2^{s}\). Но тогда число \(a / 2\) уже не превосходит \(m\) и делится на \(2^{s - 1}\); значит, и \(S_{m}\) делится на \(2^{s - 1}\). Поэтому \(S_{m + 1} / S_{m}\) не может делиться на степень двойки, бо́льшую первой.

Замечание. Можно показать, что \(S_{m + 1} > S_{m}\) только тогда, когда число \(m + 1\) является степенью некоторого простого числа \(p\); в этом случае отношение \(S_{m + 1} / S_{m}\) будет равно \(p\).

Докажем, что \(d \geqslant 7\). Все числа с доски разбиваются на цепочки чисел вида \(a, a + 1, a + 2, \ldots, a + t\) так, что числа из разных цепочек не отличаются ровно на 1 . Такое разбиение нетрудно построить, соединив любые два числа, отличающиеся на 1 , отрезком и рассмотрев полученные ломаные.

Пусть получилось \(k\) цепочек, в которых \(n_{1}, n_{2}, \ldots, n_{k}\) чисел соответственно (некоторые цепочки могут состоять из одного числа). В цепочке из \(n_{i}\) чисел есть ровно \(n_{i}-1\) пара чисел, отличающихся на 1 . Поэтому общее количество единиц в тетрадке

равно

\(\left(n_{1}-1\right) + \left(n_{2}-1\right) + \ldots + \left(n_{k}-1\right) = \left(n_{1} + n_{2} + \ldots + n_{k}\right)-k = 99-k\), откуда \(k = 99 - 85 = 14\). Значит, в одной из цепочек не меньше, чем \(99 / 14\) чисел, то есть не меньше 8 чисел. Разность наибольшего и наименьшего чисел в такой цепочке не меньше \(8 - 1 = 7\).

Осталось привести пример, в котором \(d = 7\). Такой пример дают, например, числа

\(0 = \frac{0}{14}, \frac{1}{14}, \frac{2}{14}, \ldots, \frac{98}{14} = 7 .\)

Действительно, в этом примере \(d = 7\), и ровно для первых 85 из этих чисел в наборе есть число, на единицу большее.

Замечание. Приведённый пример-не единственный. Все возможные оптимальные примеры устроены так : есть ровно одна цепочка из 8 чисел (от \(a\) до \(a + 7\) ), а также 13 цепочек, каждая-из 7 чисел; все числа этих остальных цепочек должны располагаться между \(a\) и \(a + 7\).

Первое решение. Совершим гомотетию с центром \(A\) и коэффициентом 2. При этой гомотетии точки \(M\) и \(N\) переходят в \(B\) и \(C\) соответственно; пусть точки \(K\) и \(P\) переходят соответственно в \(K^{\prime}\) и \(P^{\prime}\) (см. рис. 1). Тогда достаточно доказать, что четырёхугольник \(A B P^{\prime} K^{\prime}\) описан. Мы докажем, что он описан около вписанной окружности \(\omega\) треугольника \(A B C\). Три стороны четырёхугольника уже касаются \(\omega\), поэтому достаточно доказать, что её касается \(P^{\prime} K^{\prime}\).

Пусть \(I\) - центр \(\omega\). Тогда \(K K^{\prime} = A K\), поэтому \(A\) и \(K^{\prime}\) симметричны относительно \(K I\). Далее заметим, что \(\angle P^{\prime} K^{\prime} A = = \angle P K A = \angle M H A\). Но \(M H\) - медиана в прямоугольном треугольнике \(A H B\), поэтому \(\angle M H A = \angle M A C\). Значит, \(\angle P^{\prime} K^{\prime} A = = \angle B A C\). Значит, и прямые \(A B\) и \(K^{\prime} P^{\prime}\) также симметричны относительно \(K I\); поскольку одна из них касается \(\omega\), то и другая тоже. Это и требовалось доказать.

Замечание. У решения выше есть несколько вариаций. Например, похожими рассуждениями можно показать, что в четырёхугольнике \(A M P K\) биссектрисы трёх углов \(A, M\) и \(K\) проходят через одну точку-середину отрезка \(A I\). Отсюда следует, что эта середина-центр искомой вписанной окружности.

Рис. 1

Рис. 2

Второе решение. Пусть прямая \(P K\) пересекает прямую \(A B\) в точке \(L\) (см. рис. 2). Как и в решении выше, получаем, что \(\angle A K L = \angle A H M = \angle L A K\), откуда \(L A = L K\).

Мы докажем, что окружности, вписанные в треугольники \(A K L\) и \(A M N\), совпадают (тогда это и будет вписанная окружность четырёхугольника \(A M P K\) ). Поскольку обе окружности вписаны в угол \(B A C\), для этого достаточно показать, что они касаются прямой \(A B\) в одной и той же точке. Как известно, расстояния от \(A\) до точек касания этих окружностей с \(A B\)

равны соответственно \(\frac{A L + A K - K L}{2}\) и \(\frac{A M + A N - M N}{2}\). Значит, нам надо доказать, что \(A L + A K - K L = A M + A N - M N\), или что \(M L - K L = K N - M N\).

Обозначим полупериметр треугольника \(A B C\) через \(p\), и пусть \(a = B C, b = C A, c = A B\). Имеем \(M L - K L = (A L- -A M)-K L = -A M = -\frac{c}{2}\). С другой стороны, \(K N - M N = = (A N - A K)-M N = \left(\frac{b}{2}-(p - a)\right)-\frac{a}{2} = \frac{a + b}{2}-p = -\frac{c}{2}\), откуда и следует искомое равенство.

Замечание. Во втором абзаце решения по сути доказан следующий известный признак : четырёхугольнике \(A M P K\) описан тогда и только тогда, когда \(M L - K L = K N - M N\) (где \(N\) и \(L\) - точки пересечения продолжений боковых сторон, расположенные как на рисунке).

Первое решение. Докажем сначала, что \(m = 1\) удовлетворяет требованиям задачи. Заметим, что \(a b + c = a b + c(a + b + + c) = (c + a)(c + b)\). Следовательно,

\(\begin{array}{c} \sqrt{\frac{a b}{c + a b}} + \sqrt{\frac{b c}{a + b c}} + \sqrt{\frac{c a}{b + c a}} = \\ = \sqrt{\frac{a b}{(c + a)(c + b)}} + \sqrt{\frac{b c}{(a + b)(a + c)}} + \sqrt{\frac{c a}{(b + c)(b + a)}} = \\ = \frac{\sqrt{a b} \sqrt{a + b} + \sqrt{b c} \sqrt{b + c} + \sqrt{c a} \sqrt{c + a}}{\sqrt{(a + b)(b + c)(c + a)}} \end{array}\)

Значит, осталось доказать неравенство

\(\sqrt{a b} \sqrt{a + b} + \sqrt{b c} \sqrt{b + c} + \sqrt{c a} \sqrt{c + a} \geqslant \sqrt{(a + b)(b + c)(c + a)}\)

Возведем это неравенство в квадрат; оно примет вид

\(\begin{array}{r} a b(a + b) + b c(b + c) + c a(c + a) + 2 \sqrt{a b^{2} c(a + b)(b + c)} + \\ + 2 \sqrt{b c^{2} a(b + c)(c + a)} + 2 \sqrt{c a^{2} b(c + a)(a + b)} \geqslant \\ \geqslant a^{2} b + a b^{2} + a^{2} c + a c^{2} + b^{2} c + b c^{2} + 2 a b c \end{array}\)

После сокращения слева останется сумма корней, а справа \(2 a b c\). Но любой из корней не меньше, чем \(a b c\); действительно, например, \(\sqrt{a b^{2} c(a + b)(b + c)} \geqslant \sqrt{a b^{2} c \cdot a c} = a b c\). Отсюда и следует требуемое.

Осталось доказать, что при любом \(m > 1\) неравенство выполнено не всегда; достаточно это сделать при \(1 < m < 3\). Пусть \(m = 1 + 2 t\) при \(0 < t < 1\). Положим \(a = b = \frac{1-t^{2}}{2}\) и \(c = t^{2}\). Тогда \(a + b + c = 1\), однако

\(\sqrt{\frac{a b}{c + a b}} + \sqrt{\frac{b c}{a + b c}} + \sqrt{\frac{c a}{b + c a}} < \sqrt{\frac{a b}{a b}} + \sqrt{\frac{b c}{a}} + \sqrt{\frac{c a}{b}} = 1 + 2 t = m .\)

Второе решение. Приведём другое доказательство того, что \(m = 1\) подходит. Для этого докажем, что если \(a\) - наибольшее из чисел \(a, b, c\), то верно даже неравенство

\(\sqrt{\frac{a b}{c + a b}} + \sqrt{\frac{c a}{b + c a}} \geqslant 1\)

Обозначим \(t = 1 / a, \mu = b / c\); заметим, что \(1 > a \geqslant \frac{1}{3}\), поэтому \(1 < t \leqslant 3\). Левая часть неравенства выше переписывается как

\(\begin{aligned} \sqrt{\frac{a b}{c + a b}} + \sqrt{\frac{c a}{b + c a}} & = \sqrt{\frac{1}{1 + c / (a b)}} + \sqrt{\frac{1}{1 + b / (a c)}} = \\ & = \frac{1}{\sqrt{1 + t / \mu}} + \frac{1}{\sqrt{1 + t \mu}} \end{aligned}\)

Значит, нам достаточно доказать, что

\(\sqrt{1 + t / \mu} + \sqrt{1 + t \mu} \geqslant \sqrt{(1 + t / \mu)(1 + t \mu)}\)

Возводя это неравенство в квадрат, получаем

\(1 + t / \mu + 1 + t \mu + 2 \sqrt{(1 + t / \mu)(1 + t \mu)} \geqslant 1 + t / \mu + t \mu + t^{2}\)

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

\(2 \sqrt{(1 + t / \mu)(1 + t \mu)} \geqslant t^{2}-1 = (t - 1)(t + 1)\)

Наконец, это неравенство вытекает из неравенств \(2 \geqslant t - 1\) (поскольку \(t \leqslant 3\) ) и

\((1 + t / \mu)(1 + t \mu) = 1 + t^{2} + t(\mu + 1 / \mu) \geqslant 1 + t^{2} + 2 t = (t + 1)^{2}\)

где мы применили неравенство о средних.

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

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

После действий Пети найдётся слой, в котором включено \(d \leqslant k / 100\) лампочек-назовём один такой слой главным. Пусть \(\mathcal{V}\) - набор из \(d\) переключателей на красной грани, связанных

со включёнными лампочками в главном слое. Мы докажем, что Вася сможет погасить все лампочки, использовав с красной грани ровно эти переключатели.

Запустим несколько другой процесс, начиная с того же исходного положения. Пусть \(\mathcal{P}\) - набор переключателей с красной грани, использованных Петей, а \(\mathcal{Q}\) - набор использованных им переключателей с некрасных граней, связанных с главным слоем. Пусть Петя применит \(\mathcal{P}\) и \(\mathcal{Q}\), а затем Вася применит \(\mathcal{V}\). После действий Пети в главном слое будут гореть те же \(d\) лампочек, что и раньше, а значит, после действий Вася все лампочки в главном слое будут погашены. Если теперь Вася применит в каждом из остальных слоёв наборы переключателей с некрасных граней, аналогичные \(\mathcal{Q}\), то все лампочки будут погашены.

Пусть теперь Петя применит все остальные переключатели (с некрасных граней!), которые он применял исходно, а Вася применит их ещё по разу. Все лампочки по-прежнему будут погашены. При этом в новом процессе Петя применил ровно те же переключатели, что и в исходном, а Вася использовал лишь переключатели набора \(\mathcal{V}\) с красной грани (и какие-то-с остальных граней). Значит, если в исходном процессе Вася совершит те же действия, которые он сделал в новом, он добьётся требуемого.

Предположим противное, и пусть в множестве всех школьников есть различные 30-элементные подмножества \(A_{1}, A_{2}, \ldots, A_{50}\) (множества участников каждой олимпиады) такие, что пересечение любых 30 из них непусто, а пересечение всех-пусто.

Пусть среди множеств \(A_{1}, A_{2}, \ldots, A_{50}\) нашлись два множества \(B\) и \(C\), имеющие \(k \leqslant 28\) общих элементов \(x_{1}, x_{2}, \ldots, x_{k}\). Для каждого элемента \(x_{i}\) среди множеств \(A_{1}, A_{2}, \ldots, A_{50}\) найдём подмножество \(D_{i}\), не содержащее \(x_{i}\) (такое подмножество \(D_{i}\) найдётся, иначе \(x_{i}\) - общий элемент множеств \(A_{1}, A_{2}, \ldots, A_{50}\) ). (Заметим, что среди подмножеств \(D_{i}\) могут быть совпадающие.) Тогда пересечение не более 30 подмножеств \(B, C, D_{1}, \ldots, D_{k}\) пусто. Это противоречит нашему предположению (к данным подмножествам можно добавить еще несколько, чтобы стало 30 подмножеств, при таком добавлении пересечение остается пустым).

Значит, указанных двух множеств \(B\) и \(C\) не найдётся. Тогда пересечение любых двух из множеств \(A_{1}, A_{2}, \ldots, A_{50}\) содержит в точности 29 элементов. Пусть \(A_{1} \cap A_{2} = \left\{y_{1}, y_{2}, \ldots, y_{29}\right\}\), так что \(A_{1} = \left\{z_{1}, y_{1}, y_{2}, \ldots, y_{29}\right\}, A_{2} = \left\{z_{2}, y_{1}, y_{2}, \ldots, y_{29}\right\}\). Найдём подмножество (пусть, для определенности, это подмножество - \(A_{3}\) ), не содержащее \(y_{1}\). Так как \(\left|A_{1} \cap A_{3}\right| = = \left|A_{2} \cap A_{3}\right| = 29\), то \(A_{3}\) обязано содержать все элементы \(z_{1}, z_{2}, y_{2}, y_{3}, \ldots, y_{29}\). Этих элементов 30 (все они различны), поэтому \(A_{3} = \left\{z_{1}, z_{2}, y_{2}, y_{3}, \ldots, y_{29}\right\}\). Рассмотрим любое подмножество \(A_{i}\) из подмножеств \(A_{4}, \ldots, A_{50}\). Предположим, что \(A_{i}\) содержит элемент, лежащий вне 31-элементного множества \(K = \left\{z_{1}, z_{2}, y_{1}, y_{2}, \ldots, y_{29}\right\} = A_{1} \cup A_{2} \cup A_{3}\). Тогда \(A_{i}\) должно пересекаться с каждым из подмножеств \(A_{1}, A_{2}, A_{3}\) по одному и тому же 29-элементному подмножеству множества \(K\). Но \(\left|A_{1} \cap A_{2} \cap A_{3}\right| = 28\), значит, такого 29-элементного подмножества не существует-противоречие. Отсюда делаем вывод, что все множества \(A_{1}, A_{2}, \ldots, A_{50}\) являются подмножествами множества \(K\). Но в множестве \(K\) количество 30-элементных подмножеств равно \(31 < 50\). Получаем противоречие, завершающее решение задачи.

Из условия следует, что \((a b c + 1)-(a b - b + 1) = = a b c - a b + b = b(a c - a + 1)\) делится на \(a b - b + 1\). Заметим, что \(b\) и \(a b - b + 1 = (a - 1) b + 1\) взаимно просты, отсюда получаем, что \(a c - a + 1\) делится на \(a b - b + 1\).

Далее замечаем, что \(0 < a c - a + 1 < 2(a b - b + 1)\). Действительно, \(2(a b - b + 1) = (2 a - 2) b + 2 > (2 a - 2) c + 2 = a c + (a - 2) c + + 2 \geqslant a c + 2 > a c - a + 1\). Значит, делимость \(a c - a + 1\) на \(a b - b + 1\) возможна только в случае равенства \(a c - a + 1 = a b - b + 1\).

Имеем \(a(c - 1) = a c - a = a b - b = (a - 1) b\). Видим, что \((a - 1) b\) делится на \(a\), но так как \(a - 1\) и \(a\) взаимно просты, отсюда следует, что \(b\) делится на \(a\), что и требовалось доказать.

Заметим, что \(P Q \| C D\), так что \(P Q\) - средняя линия прямоугольного треугольника \(A H D\). Значит, \(P Q\) пересекает гипотенузу \(A H\) в её середине \(M\), так что \(M A = M D = M H\) (см. рис. 6).

Рис. 6

Имеем \(\angle M D H = \angle M H D\), а поскольку \(M H \perp B C\) и \(H D \perp \perp C D\), имеем также \(\angle M H D = \angle B C D\). Получаем равенство

\(\angle M D H = \angle B C D\), из которого следует касание прямой \(M D\) и окружности ( \(B C D\) ) в точке \(D\). Отсюда \(M D^{2} = M P \cdot M Q\) (по теореме о произведении отрезков секущей).

Далее, \(M A^{2} = M P \cdot M Q\). Значит, треугольники \(A M P\) и \(Q M A\) подобны (угол \(A M Q\) общий и \(M A / M P = M Q / M A\) ). Отсюда \(\angle M Q A = \angle M A P\), поэтому \(\angle M P A + \angle M Q A = \angle M P A + + \angle M A P = \angle H M Q = 90^{\circ}-\angle M H D = \angle C B D\). Итак, \(\angle A P B + \angle A Q B = \angle C B D\), и, поскольку \(\angle A P B + \angle A Q B = = (\angle M P A + \angle M Q A) + (\angle M P B + \angle M Q B)\), для завершения решения остаётся убедиться, что \(\angle M P B + \angle M Q B = 180^{\circ}-\angle C B D\).

Для определённости далее считаем, что \(P\) лежит между \(M\) и \(Q\). Имеем \(\angle M P B + \angle M Q B = 180^{\circ}-(\angle B P Q-\angle P Q B)\). Так как \(P Q \| C D\), то дуги \(P D\) и \(C Q\) равны, а значит, опирающиеся на них вписанные углы равны. Тогда \(\angle B P Q-\angle P Q B = \angle B D Q- -\angle P C B = (\angle B D C-\angle Q D C)-(\angle D C B-\angle D C P) = \angle B D C- -\angle D C B = 90^{\circ}-\angle D C B = \angle C B D\), что завершает доказательство.

Пусть \(\overline{x_{i} y_{i} z_{i}}\) - десятичная запись трехзначного числа \(a_{i}\). Подстановка в левую часть уравнения \(x = = 1000\) даёт \(a_{9} \cdot 1000^{9} + a_{8} \cdot 1000^{8} + \ldots + a_{1} \cdot 1000 + a_{0} = = \overline{x_{9} y_{9} z_{9} \underbrace{0000 \ldots 0}_{27 \text { нулей }}} + \overline{x_{8} y_{8} z_{8} \underbrace{0 \ldots 0}_{24 \text { нуля }}} + \ldots + \overline{x_{1} y_{1} z_{1} 000} + \overline{x_{0} y_{0} z_{0}} = = \overline{x_{9} y_{9} z_{9} x_{8} y_{8} z_{8} \ldots x_{0} y_{0} z_{0}}\). Таким образом, после подстановки вместо звёздочки 30-значного числа \(\overline{x_{9} y_{9} z_{9} x_{8} y_{8} z_{8} \ldots x_{0} y_{0} z_{0}}\) получится уравнение, имеющее корень 1000.

Первое решение. Поскольку \(A M\) - биссектриса угла \(L A N\), отрезки \(L M\) и \(M N\) равны как хорды, стягивающие равные дуги (см. рис. 3). Теперь достаточно доказать, что \(C M = = L M\) (тогда \(C M = L M = M N\), значит, \(C N L\) - прямоугольный треугольник, и \(N M\) - его медиана, проведенная из прямого угла).

Так как \(\angle B K A = \angle N A K = \angle B A K\), треугольник \(A B K\) равнобедренный (симметричный относительно серединного перпендикуляра к \(A K\) ). Отметим на стороне \(B K\) точку \(X\) так, что \(L X \| A K\). Из симметрии треугольника \(A B K\) имеем \(K X = A L\). Тогда имеем \(K X = C K\) и \(M K \| L X\), значит, \(M K\) - средняя линия треугольника \(C L X\), значит, \(C M = L M\), что завершает решение.

Рис. 3

Рис. 4

Второе решение. Пусть \(\angle B A D = 2 \alpha\).

Заметим, что \(D M\) - биссектриса угла \(A D C\). Действительно, продлим \(A K\) до пересечения с \(C D\) в точке \(Y\) (см. рис. 4). Тогда, используя подобия \(A M L \sim Y M C\) и \(A Y D \sim K Y C\), имеем \(A M / M Y = A L / Y C = C K / Y C = A D / D Y\). Из полученного равенства \(A M / M Y = A D / D Y\) вытекает, что \(D M\) - биссектриса треугольника \(A D Y\). Отсюда \(\angle M D C = \angle A D C / 2 = \left(180^{\circ}-\right. -2 \alpha) / 2 = 90^{\circ}-\alpha\).

Из вписанности \(A L M N\) имеем \(\angle C M N = \angle L A D\), а из параллельности \(A B \| C D\) следует \(\angle L A D = \angle C D N\). Поэтому

\(\angle C M N = \angle C D N\), значит, четырёхугольник \(C M D N\) - вписанный. Отсюда \(\angle M N C = \angle M D C = 90^{\circ}-\alpha\).

Из вписанности \(\angle L N M = \angle L A M = \alpha\). Тогда \(\angle L N C = = \angle M N C + \angle L N M = 90^{\circ}\), что и требовалось доказать.

Замечание. Отметим, что в решении 2 при доказательстве того, что \(D M\) - биссектриса угла \(A D C\), не использовалось то, что \(A M\) - биссектриса угла \(A\). А при доказательстве вписанности \(C M D N\) не использовалось также равенство \(A L = C K\).

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

Оценка. Пусть \(n\) столбов покрашены так, что условие задачи выполнено. Пусть \(n_{i}\) - количество столбов \(i\)-го цвета (далее считаем, что \(n_{i} \geqslant 1\), т.е. все цвета присутствуют, иначе можно увеличить \(n\), добавить столб нового цвета в конец). Пусть \(a_{i}\) и \(b_{i}\) - номера первого и последнего столбов \(i\)-го цвета.

Всего у нас есть \(t = \left(n_{1}-1\right) + \left(n_{2}-1\right) + \ldots + \left(n_{k}-1\right) = = \left(n_{1} + n_{2} + \ldots + n_{k}\right)-k = n - k\) хороших пар столбов. Поскольку все расстояния между столбами в хороших парах различны, наименьшее из этих расстояний не меньше 1 , следующее-не меньше 2 , и т.д. Так, для суммы \(S\) расстояний во всех хороших парах получаем оценку \(S \geqslant 1 + 2 + \ldots + t = t(t + 1) / 2\).

С другой стороны, сумма всех расстояний для \(i\)-го цвета равна \(b_{i}-a_{i}\). Поэтому \(S = \left(b_{1} + \ldots + b_{k}\right)-\left(a_{1} + \ldots + a_{k}\right)\). Сумма \(b_{1} + \ldots + b_{k}\) не превышает суммы \(k\) самых больших среди номеров \(1,2, \ldots, n\), а сумма \(a_{1} + \ldots + a_{k}\) не меньше, чем сумма \(k\) наименьших среди номеров \(1,2, \ldots, n\), поэтому \(S \leqslant(n + (n- -1) + \ldots + (n - k + 1))-(1 + 2 + \ldots + k) = k(n - k) = k t\).

Итак, \(t(t + 1) / 2 \leqslant S \leqslant k t\), откуда \(t \leqslant 2 k - 1\) и \(n = k + t \leqslant 3 k - 1\).

Пример. Годится, например, покраска

\(1,2, \ldots, k - 1, k, k, k - 1, \ldots, 2,1,2,3, \ldots, k - 1, k .\)

Здесь для цвета 1 единственная хорошая пара, и расстояние между столбами в ней равно \(2 k - 1\). Для всех остальных цветов есть две хорошие пары, при этом для цвета 2 имеем расстояния \(2 k - 3\) и 2 , для цвета \(3-\) расстояния \(2 k - 5\) и 4, и т.д., для цвета \(k\) - расстояния 1 и \(2 k - 2\).

Замечание. Существуют и другие, более сложные примеры. Например, можно первые \(k\) столбов покрасить в цвета \(1,2, \ldots, k\), а дальше столб с номером \(k + s\), где \(s = 2^{p}(2 q - 1)\), окрасить в цвет \(q\) (скажем, для \(k = 8\) покраска будет выглядеть так : \(1,2,3,4,5,6,7,8,1,1,2,1,3,2,4,1,5,3,6,2,7,4,8\) ). Возможно индуктивное описание подходящих примеров.

Докажем, что \((x - y) \sqrt{3 x^{2} + y^{2}} \geqslant(x - y)(x + + y) = x^{2}-y^{2}\). Если \(x \geqslant y\), то \(x - y \geqslant 0\) и \(\sqrt{3 x^{2} + y^{2}} \geqslant \geqslant \sqrt{x^{2} + 2 x y + y^{2}} = x + y\). Если же \(x \leqslant y\), то \(x - y \leqslant 0\) и \(\sqrt{3 x^{2} + y^{2}} \leqslant \sqrt{x^{2} + 2 x y + y^{2}} = x + y\).

Складывая доказанное неравенство \((x - y) \sqrt{3 x^{2} + y^{2}} \geqslant x^{2}- -y^{2}\) с аналогичными неравенствами \((y - z) \sqrt{3 y^{2} + z^{2}} \geqslant y^{2}-z^{2}\) и \((z - x) \sqrt{3 z^{2} + x^{2}} \geqslant z^{2}-x^{2}\), получаем требуемое.

Первое решение. Докажем, что для любой пары \((x, y)\), записанной на доске, число \(2 x - y\) делится на 7 .

Действительно, для пары \((1,2)\) число \(2 \cdot 1 - 1 = 0\) делится на 7 .

Пусть для пары ( \(a, b\) ) число \(2 a - b\) делится на 7. Тогда для пары \((-a,-b)\) число \(2 \cdot(-a)-(-b) = -(2 a - b)\) делится на 7 , и для пары \((-b, a + b)\) число \(2 \cdot(-b)-(a + b) = -a - 3 b = 3(2 a - b)-7 a\) делится на 7 .

Пусть для пар \((a, b),(c, d)\) числа \(2 a - b, 2 c - d\) делятся на 7. Тогда для пары \((a + c, b + d)\) число \(2(a + c)-(b + d) = (2 a - b) + + (2 c - d)\) делится на 7 .

Так как для пары \((2022,2023)\) число \(2 \cdot 2022 - 2023 = 2021\) не делится на 7 , эта пара на доске появиться не может.

Второе решение. Будем к каждой паре \((a, b)\) на доске дописывать третье число \(c = -a - b\). Тогда сумма чисел в каждой тройке будет равна нулю, а правила дописывания новых пар будут такими : если на доске записана тройка ( \(a, b, c\) ), то можно дописать тройки \((-a,-b,-c)\) и \((-b,-c,-a)\), а если записаны тройки \((a, b, c)\) и ( \(d, e, f\) ), то можно дописать тройку ( \(a + d, b + e, c + f\) ) - назовём эту тройку суммой троек ( \(a, b, c\) ) и ( \(d, e, f\) ). Также для тройки ( \(a, b, c\) ) и целого числа \(k\) обозначим через \(k \cdot(a, b, c)\) тройку ( \(k a, k b, k c\) ).

Докажем, что все тройки, появляющиеся на доске, имеют вид

\((a, b, c) = k \cdot(1,2,-3) + \ell \cdot(2,-3,1) + m \cdot(-3,1,2)\)

с целыми \(k, \ell\) и \(m\). В начальный момент времени это верно : \((1,2,-3) = 1 \cdot(1,2,-3) + 0 \cdot(2,-3,1) + 0 \cdot(-3,1,2)\). Теперь достаточно показать, что из троек, имеющих вид ( \(*\) ), также получаются лишь такие тройки. Для операции взятия суммы троек это очевидно. Для остальных операций это тоже несложно проверить : если \((a, b, c)\) имеет вид ( * ), то

\(\begin{array}{l} (-a,-b,-c) = (-k) \cdot(1,2,-3) + (-\ell) \cdot(2,-3,1) + (-m) \cdot(-3,1,2), \\ (-b,-c,-a) = (-m) \cdot(1,2,-3) + (-k) \cdot(2,-3,1) + (-\ell) \cdot(-3,1,2) . \end{array}\)

Утверждение доказано.

Предположим теперь, что на доске появилась тройка \((2022,2023,-4045)\), то есть она имеет вид \(( * )\). Тогда имеем

\(2022 = k + 2 \ell - 3 m \quad \text { и } \quad 2023 = 2 k - 3 \ell + m .\)

Выражая из первого равенства \(k = 2022 - 2 \ell + 3 m\) и подставляя во второе, получаем \(2023 = 2 \cdot 2022 - 7 \ell + 7 m\), то есть \(7(m-\ell) = = 2023 - 2 \cdot 2022 = -2021\). Однако это невозможно, поскольку 2021 не делится на 7 .

Замечание. Можно показать, что указанными операциями получаются все тройки, имеющие вид ( * ). Также можно заметить, что \((-3,1,2) = -(1,2,-3)-(2,-3,1)\), так что в формуле ( * ) можно обойтись без третьего слагаемого.

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

на доске в исходном процессе, имеют вид

\((a, b) = k \cdot(1,2) + \ell \cdot(2,-3)\)

с целыми \(k\) и \(\ell\). Заметим здесь, что если пара ( \(a, b\) ) имеет вид ( * * ), то

\((-b, a + b) = \ell \cdot(1,2) + (\ell - k) \cdot(2,-3) .\)

Пусть \(P\) - такая точка на луче \(H E\), что \(P B \perp \perp B C\) (см. рис. 7). Докажем, что точки \(C, O\) и \(P\) лежат на одной прямой.

В самом деле, по теореме Менелая для треугольника \(A D E\) и прямой \(C M B\) имеем \(\frac{E C}{C D} \cdot \frac{D M}{M A} \cdot \frac{A B}{B E} = 1\). Поскольку прямые \(P B, A H\) и \(O M\) параллельны между собой (так как они все перпендикулярны прямой \(B C\) ), имеем \(A B / B E = H P / P E\), а также \(D M / M A = D O / O H\). Значит, \(\frac{E C}{C D} \cdot \frac{D O}{O H} \cdot \frac{H P}{P E} = 1\), из чего следует, что точки \(C, O\) и \(P\) лежат на одной прямой по теореме Менелая для треугольника \(E D H\). Значит, точка \(P\) диаметрально противоположна точке \(C\) в окружности \(\omega\). Аналогично, если \(Q\) - точка пересечения перпендикуляра к прямой \(B C\), проходящего через точку \(C\), и прямой \(H F\), то точка \(Q\) диаметрально противоРис. 7

\(T_{b} = T_{c}\)

Рис. 8

положна точке \(B\). Из этого следует, что \(\angle E X C = \angle P X C = 90^{\circ}\), и, аналогично, \(\angle F Y B = \angle Q Y B = 90^{\circ}\).

Обозначим через \(H^{\prime}, T_{b}\) и \(T_{c}\) точки пересечения прямой \(A H\) соответственно с прямыми \(P Q, B Y\) и \(C X\) (см. рис. 8). Заметим, что треугольники \(H X T_{c}\) и \(H H^{\prime} P\) подобны как прямоугольные с вертикальными острыми углами. Значит, \(H T_{c} / H X = H P / H H^{\prime}\), или \(H T_{c} = H X \cdot H P / H H^{\prime} = H B \cdot H C / H H^{\prime}\). Аналогично, \(H T_{b} = = H B \cdot H C / H H^{\prime}\). Значит, прямые \(B Y\) и \(C X\) пересекают прямую \(A H\) в одной и той же точке, что и требовалось доказать.

Возьмём прямоугольник размера \(5 \times 15\), половина площади которого равняется 37,5 . Для того, чтобы условие выполнялось, из данного прямоугольника необходимо вырезать прямоугольник площади 37 или 38. Таких прямоугольников всего три : \(1 \times 37,1 \times 38\) и \(2 \times 19\). Заметим, что длинная сторона каждого из таких прямоугольников не меньше 19. С другой стороны, диагональ исходного прямоугольника равняется \(\sqrt{250}\), но \(\sqrt{250} < \sqrt{256} = 16 < 19\), поэтому ни один из таких прямоугольников вырезать из прямоугольника \(5 \times 15\) нельзя.

Обозначим вторую точку пересечения биссектрисы угла \(A B C\) с окружностью, описанной около треугольника \(A B C\), через \(F\) (см. рис. 5). Тогда точка \(F\) - середина дуги \(A C\), поэтому \(O F\) - серединный перпендикуляр к хорде \(A C\). Поскольку вписанный угол вдвое меньше центрального, опирающегося на ту же дугу, то \(\angle F O C = 2 \angle F B C\). С другой стороны, так как \(B D = D C\), то \(\angle D C B = \angle C B D\), а тогда \(\angle C D F = \angle D C B + + \angle D B C = 2 \angle D B C = 2 \angle F B C\) как внешний к треугольнику \(B C D\). Таким образом, \(\angle F O C = \angle F D C\), поэтому точка \(F\) лежит на окружности, описанной около треугольника \(C O D\). Рассуждая аналогично, мы получаем, что \(\angle A O F = 2 \angle A B F = \angle A E F\), и точка \(F\) лежит и на окружности, описанной около треугольника \(A O E\). Значит, точки \(P\) и \(Q\) - центры описанных окружностей треугольников \(A O F\) и \(C O F\), а эти треугольники симметричны относительно \(O F\). Получается, что точки \(P\) и \(Q\) также симметричны относительно \(O F\). Следовательно, либо точки \(P\) и \(Q\) лежат на прямой \(A C\), либо \(P, Q, A, C\) - вершины равнобокой трапеции, а потому лежат на одной окружности.

Рис. 5

Положим \(d = \frac{1}{a}-\frac{1}{b}-\frac{1}{c}\). Теперь заметим, что

\(\left|\frac{b}{a}-\frac{b}{c}\right| + \left|\frac{c}{a}-\frac{c}{b}\right| + |b c + 1| = |b d + 1| + |c d + 1| + |b c + 1| .\)

Если \(d = 0\), то два из этих слагаемых равны 1 , и тем самым сумма не меньше, чем 2 . В противном случае числа \(a, b, d\) отличны от нуля. Значит, какие-то два из них одного знака, а тогда их произведение положительно, и соответствующее слагаемое больше 1. Поскольку два других слагаемых неотрицательные, то общая сумма больше 1.

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

Предположим, в графе с \(2 n\) вершинами найдётся пара вершин, соединённых ребром, при удалении которых граф не теряет связность; обозначим эти вершины через \(u\) и \(v\). Покрасим оставшиеся вершины таким образом, чтобы число разноцветных рёбер было хотя бы на \(n - 1\) больше числа одноцветных рёбер так можно сделать по предположению индукции. Заметим, что вершины \(u\) и \(v\) теперь можно покрасить таким образом, что разность между количествами разноцветных и одноцветных рёбер увеличится. В самом деле, без ограничения общности будем считать, что если вершины \(u\) и \(v\) не имеют обе чётные степени, то вершина \(u\) имеет нечётную степень. Тогда покрасим вершину \(u\) в цвет, который имеет меньшинство её соседей (в случае равенства покрасим в любой цвет), а затем покрасим таким же образом вершину \(v\). Очевидно, при каждой покраске требуемая разность не уменьшилась, и хотя бы при одной покраске у соответствующей вершины было нечётное число покрашенных соседей, то есть разность при этой покраске увеличилась. Поскольку до покраски вершин \(u\) и \(v\) разность между числом разноцветных рёбер и числом одноцветных рёбер была не меньше \(n - 1\), после этой покраски она стала не меньше \(n\).

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

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

В самом деле, рассмотрим произвольное остовное дерево этого графа и подвесим его за любую не висячую вершину. Пусть \(v\) - наиболее удалённая от корня висячая вершина этого дерева, а \(u\) - предок этой вершины. Обозначим потомков этого предка через \(v_{1}, \ldots, v_{k}\). Заметим, что вершины \(v_{1}, \ldots, v_{k}\) являются висячими в рассматриваемом остовном дереве. Рассмотрим несколько случаев.

Случай 1. Среди вершин \(v_{1}, \ldots, v_{k}\) есть пара вершин, соединённых ребром в исходном графе. Тогда при удалении этих двух вершин остовное дерево (а значит, и сам исходный граф) сохраняет связность.

Случай 2. Среди вершин \(v_{1}, \ldots, v_{k}\) есть пара вершин, являющихся висячими в исходном графе. Значит, в исходном графе есть хотя бы две висячие вершины.

Случай 3. Среди вершин \(v_{1}, \ldots, v_{k}\) есть не больше одной вершины, являющейся висячей в исходном графе. Без ограничения общности, будем считать, что если такая вершина есть, то это вершина \(v_{1}\). Тогда переподвесим каждую из вершин \(v_{2}, \ldots\), \(v_{k}\) к любому из её соседей, отличных от \(u\) : поскольку эти вершины не являются висячими в исходном графе, такой сосед всегда найдётся. После всех переподвешиваний вершины \(u\) и \(v_{1}\) можно будет удалить из графа, и остовное дерево останется связным а значит, и сам граф.

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

Замечание. Неравенство из задачи является точным : в частности, в полном графе на \(2 n\) вершинах соответствующая разность не может быть строго больше \(n\).