Пусть \(n > k\) - главные делители числа \(a\); тогда \(a / n\) и \(a / k\) - два наименьших делителя числа \(a\), бо́льших единицы. Пусть \(p\) - наименьший простой делитель числа \(a\), а \(q\) - наименьший простой делитель \(a\), кроме \(p\) (если такой существует). Тогда \(a / n = p\). Далее, \(a / k\) - либо простое число (тогда это \(q\) ), либо составное. Во втором случае единственным простым делителем числа \(a / k\) является \(p\), и потому \(a / k = p^{2}\); этот случай реализуется ровно тогда, когда \(a\) делится на \(p^{2}\), причём \(p^{2} < q\) или \(q\) не существует.

Итак, главные делители числа \(a\) - это либо \(a / p\) и \(a / q\), либо \(a / p\) и \(a / p^{2}\). Покажем теперь, что по двум главным делителям \(n > k\) составное число \(a\) восстанавливается однозначно (откуда и следует требуемое). Если \(n\) кратно \(k\), то выполнен второй случай, и тогда \(a = n^{2} / k\). Иначе выполнен первый случай, и тогда \(a = \operatorname{HOK}(n, k)\).

Первое решение. Проведём в окружности \(\omega_{b}\) диаметр \(I X\), а в окружности \(\omega_{c}\) - диаметр \(I Y\). Заметим, что \(\angle I B J = 90^{\circ} = = \angle I C J\), поскольку внутренняя и внешняя биссектриса угла перпендикулярны. Следовательно, точка \(X\) лежит на \(B J\), а точка \(Y\) - на \(C J\) (см. рис. 1). Кроме того, \(I X \perp I C\), поскольку \(\omega_{b}\) касается \(I C\) в точке \(I\), поэтому \(I X \| C J\). Аналогично, \(I Y \| B J\). Итого, четырёхугольник \(I X J Y\) - параллелограмм, пусть его диагонали пересекаются в точке \(M\). Тогда \(I M = M J\), а отрезок \(O_{b} O_{j}\) - средняя линия треугольника \(I X Y\), поэтому точка \(K\) середина отрезка \(I M\). Таким образом, \(I K = I M / 2 = I J / 4\), откуда следует, что \(I K / K J = 1 / 3\).

Рис. 1

Рис. 2

Второе решение. Обозначим через \(N\) середину дуги \(B A C\) описанной окружности \(\Omega\) треугольника \(A B C\), а через \(S\) - середину другой её дуги \(B C\). Пусть луч \(N I\) вторично пересекает \(\Omega\) в точке \(P\) (см. рис. 2). Поскольку \(S N\) - диаметр окружности \((A B C)\), то \(\angle N P S = 90^{\circ}\).

По известной лемме о трезубце имеем \(S I = S C = S J\), в частности, \(S\) - середина отрезка \(I J\). Поскольку \(\angle B A C = \angle B N C\) и \(B N = N C\), то \(\angle N B C = \angle N C B = \frac{1}{2} \angle A B C + \frac{1}{2} \angle A C B\).

Продлим луч \(C I\) до пересечения с \(A B\) в точке \(L\). Так

как \(\angle L I B\) внешний для треугольника \(B I C\), а также четырёхугольник \(B N C P\) - вписанный, мы получаем, что \(\angle L I B = = \angle I B C + \angle I C B = \frac{1}{2} \angle A B C + \frac{1}{2} \angle A C B = \angle N C B = \angle I P B\), поэтому окружность ( \(I B P\) ) касается прямой \(C I\) в точке \(I\). Также эта окружность проходит через \(B\), следовательно, это и есть окружность \(\omega_{b}\). Аналогично, окружность \(\omega_{c}\) описана около треугольника \(I P C\).

Значит, \(I P\) - общая хорда окружностей \(\omega_{b}\) и \(\omega_{c}\), а тогда \(O_{b} O_{c}\) - серединный перпендикуляр к отрезку \(I P\). Поскольку к тому же \(\angle I P S = 90^{\circ}\), мы получаем, что \(O_{1} O_{2}\) проходит через середину отрезка \(I S\), то есть \(K I = K S\), а тогда \(I K / K J = 1 / 3\).

Замечание. Точка \(S\) во втором решении совпадает с точкой \(M\) из первого решения.

Первое решение. Без ограничения общности будем считать, что точка \(D\) лежит на отрезке \(B E\) и \(A D \leqslant A E\). Пусть \(O\) - центр окружности ( \(A D E\) ). Пусть точка \(A^{\prime}\) симметрична \(A\) относительно серединного перпендикуляра к отрезку \(D E\) (см. рис. 5). Из симметрии \(A^{\prime} B = A C = B Q\). Окружность с центром \(B\) и радиусом \(B A^{\prime}\) пересекает окружность ( \(A D E\) ) в точках, симметричных относительно прямой \(B O\), то есть точки \(A^{\prime}\) и \(Q\) симметричны относительно \(B O\). Аналогично, точки \(A^{\prime}\) и \(P\) симметричны относительно прямой \(C O\).

Прямые \(O B\) и \(O C\) симметричны относительно серединного

Рис. 5

Рис. 6

перпендикуляра к отрезку \(D E\), поэтому они образуют равные углы с прямой \(D E\). Поскольку \(A^{\prime} P \perp C O, A^{\prime} Q \perp B O\) и \(A A^{\prime} \| \| D E\), то прямые \(A^{\prime} Q\) и \(A^{\prime} P\) образуют равные углы с прямой \(A A^{\prime}\). Значит, меньшие дуги окружности ( \(A D E\) ), стягиваемые хордами \(A P\) и \(A Q\) равны, а тогда \(A P = A Q\), что и требовалось.

Второе решение. Без ограничения общности будем считать, что точка \(D\) лежит на отрезке \(B E\). Пусть \(O\) - центр окружности ( \(A D E\) ). Заметим, что \(O B = O C\). Поскольку \(\angle D A E < \angle B A C < 90^{\circ}\), то точки \(A\) и \(O\) лежат по одну сторону от прямой \(B C\) (см. рис. 6). Треугольники \(O A B\) и \(O P C\) равны по трем сторонам, треугольники \(O A C\) и \(O Q B\) - тоже.

Тогда \(\angle A B Q = \angle A B O + \angle O B Q = \angle P C O + \angle O C A = \angle P C A\). (Если луч \(B O\) не лежит внутри угла \(A B Q\), то луч \(B A\) лежит внутри угла \(Q B O\), а значит и внутри угла \(O B C\). В этом случае либо \(\angle B O A > \angle B O E = \angle C O D > \angle C O P\), либо \(\angle B O A < < \angle B O D = \angle C O E < \angle C O P\); в обоих случаях получаем противоречие с равенством треугольников \(O A B\) и \(O P C\). Аналогично, луч \(C O\) лежит внутри угла \(P C A\).)

Поэтому треугольники \(A B Q\) и \(P C A\) равны по двум сторонам и углу между ними, откуда \(A P = A Q\).

Будем искать касательную, проходящую через начало координат. Касательная к графику синуса в точке ( \(x_{0}, \sin x_{0}\) ) имеет уравнение \(y = \left(x - x_{0}\right) \cdot \cos x_{0} + \sin x_{0}\). Эта прямая проходит через начало координат тогда и только тогда, когда \(0 = -x_{0} \cdot \cos x_{0} + \sin x_{0}\), что равносильно \(\operatorname{tg} x_{0} = x_{0}\).

Осталось построить точку ( \(x_{0}, \sin x_{0}\) ). Для этого (с помощью циркуля и линейки) построим биссектрису координатного угла, т.е. прямую \(y = x\). Выберем её точку пересечения с графиком тангенса : \(\left(x_{0}, \operatorname{tg} x_{0}\right), x_{0} \neq 0\). Далее, опуская из этой точки перпендикуляр на ось абсцисс и пересекая этот перпендикуляр с

графиком синуса, получаем точку ( \(x_{0}, \sin x_{0}\) ). Прямая, проходящая через начало координат и точку \(\left(x_{0}, \sin x_{0}\right)\) будет касаться графика синуса в точке \(\left(x_{0}, \sin x_{0}\right)\) по выбору точки \(x_{0}\), а также в точке \(\left(-x_{0},-\sin x_{0}\right)\) из симметрии относительно начала координат. Эти точки лежат по разные стороны от оси абсцисс, что и требовалось.

Пусть строка состоит из чисел \(a_{1}, a_{2}, \ldots, a_{200}\) в этом порядке. Если число \(a_{i} = 2 k\) чётно, то следующим за ним может быть число \(k\) или число \(18 k\); эти числа дают одинаковые остатки при делении на 17 . Если же \(a_{i}\) нечётно, то \(a_{i + 1} = 9 a_{i}\). В любом случае получаем, что \(a_{i} \equiv 2 a_{i + 1}(\bmod 17)\).

Таким образом, полагая \(a = a_{200}\), получаем, что с точки зрения остатков при делении на 17 строка устроена так же, как и строка \(2^{199} a, 2^{198} a, \ldots, 2 a, a\). Сумма всех членов этой новой строки равна \(\left(2^{200}-1\right) a\). В частности, она делится на \(2^{8}-1 = 15 \cdot 17\), то есть делится на 17 . Поэтому и сумма чисел в исходной строке делится на 17 , и она не может равняться \(24^{2022}\).

Замечание. Доказать, что сумма всех чисел в строке делится на 17 , можно и по-другому. Можно, например, разбить строку на восьмёрки подряд идущих чисел и заметить, что сумма чисел восьмёрки, заканчивающейся числом \(a\), сравнима с \(\left(2^{8}-1\right) a = 17 \cdot 15 a\).

Также можно рассуждать следующим образом. Каждое следующее число в строке получается из предыдущего одной из следующих операций : делением на 2 или умножением на 9 . Отметим, что перестановка местами этих операций не меняет остатка от деления суммы всех чисел на 17 (действительно, после такой замены фрагмент строки \(2 k, 18 k, 9 k\) заменяется на фрагмент \(2 k, k, 9 k)\). Тогда можно переставить операции так, чтобы сначала шли деления на 2 , а потом умножения на 9 .

Если при этом происходит \(n - 1\) деление на 2 , а затем \(200-n\) умножений на 9 , то строка состоит из чисел \(2^{n - 1} a, 2^{n - 2} a, \ldots\), \(2 a, a, 9 a, 81 a, \ldots, 9^{200-n} a\). Сумма всех этих чисел равна

\(a\left(2^{n}-1\right) + 9 a \cdot \frac{9^{200-n}-1}{8} = \frac{a}{8} \cdot\left(2^{n + 3} + 9^{201-n}-17\right) .\)

После этого достаточно проверить, что число \(2^{i} + 9^{j}\) делится на 17 , если \(i + j\) даёт остаток 4 при делении на 8. Это можно сделать, например, перебором остатков от деления на 8 с учётом того, что \(2^{8}-1 = 15 \cdot 17 \equiv 0(\bmod 17)\) и \(9^{8}-1 \equiv(-4)^{4}-1 = 2^{8}-1 \equiv 0 (\bmod 17)\).

Мы всегда считаем, что площадь торта равна 1.

Покажем, что при некоторых запросах детей родители не смогут вырезать более 12 требуемых кусков. Выберем число \(1 / 15 > x > 1 / 16\). Предположим, что 15 главных детей заказали по куску торта площади \(x\) (а остальные трое сделали произвольные заказы так, чтобы суммарная площадь заказанных кусков была равна 1). Мысленно разобьём торт на 16 равных

квадратов и отметим на торте все 9 вершин этих квадратов, не лежащих на границе торта (см. рис. 3). Тогда строго внутри любого квадратного куска площади \(x\) будет лежать одна из отмеченных точек, то есть можно вырезать не больше девяти таких кусков. Значит, хотя бы шестерым детям желаемых кусков не достанется.

Осталось доказать, что 12 детей всегда смогут получить желаемое. Пусть \(a_{1} \geqslant a_{2} \geqslant \ldots \geqslant a_{18}\) - длины сторон кусков, которые хотят получить дети, то есть

\(a_{1}^{2} + a_{2}^{2} + \ldots + a_{18}^{2} = 1 .\)

Покажем, что из квадрата можно вырезать куски со сторонами \(a_{7}, a_{8}, \ldots, a_{18}\).

Для этого нам потребуются неравенства

\(a_{7} + a_{10} + a_{13} + a_{16} \leqslant 1 \quad \text { и } \quad a_{7} + a_{8} + a_{9} \leqslant 1 .\)

Для доказательства первого неравенства заметим, что

\(\begin{array}{l} 1 \geqslant a_{1}^{2} + a_{2}^{2} + \ldots + a_{16}^{2} \geqslant 4 a_{4}^{2} + 4 a_{8}^{2} + 4 a_{12}^{2} + 4 a_{16}^{2} \geqslant \\ \quad \geqslant 4\left(a_{7}^{2} + a_{10}^{2} + a_{13}^{2} + a_{16}^{2}\right) \geqslant\left(a_{7} + a_{10} + a_{13} + a_{16}\right)^{2} \end{array}\)

в последнем переходе мы воспользовались неравенством между средним квадратичным и средним арифметическим. Второе неравенство доказывается аналогично : \(\begin{aligned} 1 \geqslant a_{1}^{2} + a_{2}^{2} & + \ldots + a_{9}^{2} \geqslant 3 a_{3}^{2} + 3 a_{6}^{2} + 3 a_{9}^{2} \geqslant \\ & \geqslant 3\left(a_{7}^{2} + a_{8}^{2} + a_{9}^{2}\right) \geqslant\left(a_{7} + a_{8} + a_{9}\right)^{2} . \end{aligned}\)

Рис. 3

Рис. 4

Из неравенств ( * ) следует, что можно разрезать торт на горизонтальные полосы высот, не меньших \(a_{7}, a_{10}, a_{13}\) и \(a_{16}\) соответственно, и в \(i\)-ю полосу уложить квадраты со сторонами \(a_{3 i + 4}, a_{3 i + 5}\) и \(a_{3 i + 6}\), как показано на рис. 4.

Первое решение. Назовём дискриминантом пары чисел \((a, b)\) величину \(D(a, b) = b^{2}-4 a\). Докажем, что дискриминант всех пар чисел, записанных на доске, всегда отрицателен. Действительно, дискриминант пары чисел, записанной изначально, равен \(D(1,1) = -3 < 0\). Далее, верны следующие соотношения : \(\frac{D(x, y - 1)}{D(x + y, y + 1)} = \frac{y^{2}-4 x - 2 y + 1}{y^{2}-4 x - 2 y + 1} = 1\)

и

\(\frac{D(x, x y)}{D(1 / x, y)} = \frac{x^{2} y^{2}-4 x}{y^{2}-4 / x} = x^{2}\)

поэтому на доске ни в какой момент не может появиться число с положительным дискриминантом. Теперь рассмотрим любую выписанную на доску пару ( \(a, b\) ). В ней первое число \(a\) равно \(\frac{b^{2}-D}{4}\) и, следовательно, больше 0 , что и требовалось доказать.

Второе решение. Если на доске написана пара \((x, y)\), то с помощью первой операции можно добавить или пару \((x + y + + 1, y + 2\) ), или пару ( \(x - y + 1, y - 2\) ). Обе этим пары можно записать как \(\left(x + k y + k^{2}, y + 2 k\right)\), где в первом случае \(k = 1\), а во втором \(-k = -1\). С помощью второй операции можно добавить только пару \(\left(\frac{1}{x}, \frac{y}{x}\right)\).

Докажем более общий факт : на каждом шаге для любых целых \(s, t\), таких, что \(s^{2} + t^{2} > 0\), для любой пары чисел ( \(x, y\) ), написанной на доске, выполняется неравенство

\(s^{2} x + s t y + t^{2} > 0\)

В частности, при \(s = 1, t = 0\) получается в точности утверждение исходной задачи.

Для пары \((1,1)\) утверждение задачи верно. Далее, рассмотрим два типа операций : - \((x, y) \rightarrow\left(x + k y + k^{2}, y + 2 k\right)\). Тогда для новой пары верно \(s^{2}\left(x + k y + k^{2}\right) + s t(y + 2 k) + t^{2} = s^{2} x + s(s k + t) y + (s k + t)^{2} > 0\).

- \((x, y) \rightarrow(1 / x, y / x)\). Здесь также получаем нужное неравенство : \(s^{2} \frac{1}{x} + s t \frac{y}{x} + t^{2} = \frac{t^{2} x + t s y + s^{2}}{x} = \frac{t^{2} x + t s y + s^{2}}{1^{2} \cdot x + 1 \cdot 0 \cdot y + 0^{2}} > 0 .\)

Оценка. Рассмотрим шаг, на котором Василий помечает некоторый отрезок \(A B\). Перед этим шагом из каждой из точек \(A\) и \(B\) выходит максимум по \(n - 2\) отрезка, и они содержат максимум \(2 n - 4\) различных пометки. Значит, Василий точно сможет пометить этот отрезок числом, не превосходящим \(2 n - 3\). Итак, \(k \leqslant 2 n - 3\).

Если \(n\) чётно, эту оценку можно уточнить следующим образом. Назовём маленъким отрезок, помеченный единицей. Докажем, что в конце процесса из каждой точки будет выходить маленький отрезок; предположим противное. Точки, из которых выходят маленькие отрезки, разбиваются на пары точек, соединённых таким отрезком. Значит, есть хотя бы две точки \(X\) и \(Y\), из которых не выходит маленьктх отрезков. Выходит, что когда Василий проводил отрезок \(X Y\), он должен был пометить его единицей-противоречие.

Значит, если отрезок \(A B\) не будет маленьким. то в конце процесса среди отрезков, выходящих из \(A\) и \(B\), кроме \(A B\), будут два маленьких отрезка. Значит, на этих отрезках будет максимум \(2(n - 2)-1 = 2 n - 5\) различных пометок. Следовательно, когдв Василий будет проводить отрезок \(A B\), он сможет пометить его числом, не превосходящим \(2 n - 4\), и \(k \leqslant 2 n - 4\).

Пример. Осталось доказать, что Василий может достичь указанных значений \(k\).

Лемма. Если количество точек чётно и равно \(m\), то Василий может пометить все отрезки между этими точками, использовав лишь числа от 1 до \(m - 1\). При этом из каждой

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

Доказательство. Утверждение леммы не зависит от конкретного расположения точек, так что можно считать, что \(m - 1\) точек \(A_{1}, \ldots, A_{m - 1}\) расположены в вершинах правильного ( \(m - 1\) )-угольника, а оставшаяся точка-в его центре \(O\).

Тогда все отрезки между этими точками можно разбить на \(m - 1\) множеств \(S_{1}, S_{2}, \ldots, S_{m - 1}\) так, чтобы отрезки одного множества не имели общих концов. Например, в множество \(S_{i}\) можно включить отрезок \(O A_{i}\) и все отрезки, соединяющие пары вершин ( \(m - 1\) )-угольника и перпендикулярные \(O A_{i}\). Из каждой точки выходит по отрезку каждого из множеств.

Теперь Василий может сначала пометить все отрезки множества \(S_{1}\) числом 1 , затем все отрезки второго множества числом 2 , и т. д.

Вернёмся к решению. Пусть \(n\) нечётно, и пусть \(A\) - отмеченная точка. Пусть Василий сначала пометит все отрезки между точками, отличными от \(A\), числами от 1 до \(n - 2\) согласно лемме. Затем он проведёт все \(n - 1\) отрезок из \(A\); каждый отрезок \(A B\) ему придётся помечать числом, бо́льшим \(n - 2\), ибо из \(B\) уже выходят отрезки, помеченные всеми меньшими числами. Кроме того, все эти \(n - 1\) отрезок будут помечены разными числами, ибо у них есть общий конец. Следовательно, они будут помечены числами \(n - 1, n, \ldots, 2 n - 3\), то есть Василий получит пометку \(k = 2 n - 3\).

Пусть теперь \(n\) чётно. Выберем две отмеченных точки \(A\) и \(B\); пусть \(C_{1}, C_{2}, \ldots, C_{n - 2}\) - остальные отмеченные точки. Пусть Василий сначала пометит все отрезки между точками \(C_{i}\) числами от 1 до \(n - 3\) согласно лемме, а также пометит отрезок \(A B\) числом 1. Затем он последовательно проводит отрезки \(A C_{1}\), \(A C_{2}, \ldots, A C_{n - 3} ;\) поскольку в вершины \(C_{i}\) уже входят отрезки с пометками от 1 до \(n - 3\), новые отрезки будут помечены числами \(n - 2, n - 1, \ldots, 2 n - 6\) соответственно. Далее Василий проводит отрезки \(B C_{n - 3}, B C_{2}, B C_{3}, \ldots, B C_{n - 4}\); аналогично, он пометит их числами \(n - 2, n - 1, \ldots, 2 n - 6\) соответственно.

Теперь в вершины \(A\) и \(B\) уже входят отрезки со всеми пометками от \(n - 2\) до \(2 n - 6\), а в вершину \(C_{n - 2}\) - со всеми пометками

от 1 до \(n - 3\). Значит, когда Василий проводит отрезки \(A C_{n - 2}\) и \(B C_{n - 2}\), первый будет помечен числом \(2 n - 5\), а второй-числом \(2 n - 4\) (ибо имеет общий конец с предыдущим). Значит, Василий добился появления числа \(k = 2 n - 4\).

Заметим, что \(\angle P A Q = 90^{\circ}\), так как \(P Q\) - диаметр окружности ( \(A B C\) ). Пусть \(M\) и \(N\) - середины отрезков \(A P\) и \(A Q\) соответственно. Так как \(\angle A Z P = 90^{\circ} = \angle A X P\), то четырёхугольник \(A Z X P\) вписан в окружность с центром в точке \(M\), откуда \(\angle P Z X = \angle P A B = 90^{\circ}-\angle B A Q = 90^{\circ}-\angle B P Z\). Следовательно, \(X Z \perp B P\). Тогда, в силу сказанного выше, серединный перпендикуляр к отрезку \(X Z\) проходит через точку \(M\) и параллелен прямой \(B P\), а потому на нём лежит и середина отрезка \(A B\), обозначим её через \(D\). Аналогично, если \(E\) - середина отрезка \(A C\), то \(N E\) - серединный перпендикуляр к отрезку \(Y Z\). Таким образом, прямые \(M D\) и \(N E\) пересекаются в центре окружности ( \(X Y Z\) ), обозначим его через \(O\).

Тогда \(\angle D O E = 180^{\circ}-\angle X Z Y = \angle P Z X + \angle Q Z Y = \angle P A B + + \angle Q A C = 90^{\circ}-\angle B A C\). Следовательно, точка \(O\) лежит на фиксированной окружности, проходящей через точки \(D\) и \(E\), что и требовалось.

Первое решение. Будем называть индекс \(k \geqslant 2\) плохим, если \(a_{k - 1} < a_{k} > a_{k + 1}\) или \(a_{k - 1} > a_{k} < a_{k + 1}\). Заметим, что если среди индексов \(N + 1, N + 2, \ldots\) нет плохих, то последовательность \(a_{N}, a_{N + 1}, a_{N + 2}, \ldots\) монотонна.

Предположим, что утверждение задачи неверно. Тогда найдётся бесконечно много плохих индексов. Выберем некоторый плохой индекс \(k\). Возьмём произвольное \(n > k\) и рассмотрим монотонный отрезок \(I\) длины \(n + 1\), содержащий \(a_{n}\). Он не может содержать членов \(a_{k - 1}, a_{k}\) и \(a_{k + 1}\) одновременно; следовательно, поскольку \(k + 1 \leqslant n\), отрезок \(I\) точно не содержит \(a_{k - 1}\), а следовательно, не содержит и \(a_{1}\).

Итак, монотонный отрезок \(I\) длины \(n + 1\) содержит \(a_{n}\), но не содержит \(a_{1}\); тогда он обязан содержать \(a_{n}, a_{n + 1}\) и \(a_{n + 2}\), так что индекс \(n + 1\) не является плохим. Итак, при любом \(n > k\) индекс \(n + 1\) не плохой, поэтому плохих индексов конечное количество. Противоречие.

Второе решение. Предположим противное. Не умаляя общности, можно считать, что \(a_{1} < a_{2}\) (иначе можно умножить все члены последовательности на -1 ). Поскольку последовательность \(a_{2}, a_{3}, \ldots\) не является возрастающей, существует такое \(k \geqslant 2\), что \(a_{k} > a_{k + 1}\). Поскольку последовательность \(a_{k + 1}, a_{k + 2} \ldots\) не является убывающей, существует такое \(\ell > k\), что \(a_{\ell} < a_{\ell + 1}\). Выберем наименьшее \(\ell\), удовлетворяющее этим

двум неравенствам. Тогда либо \(\ell > k + 1\), и тогда \(a_{\ell - 1} > a_{\ell}\) согласно выбору \(\ell\), либо \(\ell = k + 1\), и тогда \(a_{\ell - 1} = a_{k} > a_{k + 1} = a_{\ell}\). Итак, в любом случае \(a_{\ell - 1} > a_{\ell}\).

Рассмотрим монотонный отрезок длины \(\ell\), содержащий \(a_{\ell - 1}\); он обязан содержать и \(a_{\ell}\). Поскольку \(a_{\ell - 1} > a_{\ell}\), числа этого отрезка монотонно убывают. Значит, он не может содержать числа \(a_{1}\) (иначе бы он содержал и \(a_{2} > a_{1}\) ). Но тогда, раз длина отрезка равна \(\ell\), он обязан содержать и \(a_{\ell + 1} > a_{\ell}\), что невозможно.

Первое решение. Докажем, что \(a \geqslant 1001000\). Заметим, что если \(y\)-корень трёхчлена \(a x^{2} + b x + c\), то \(1 / y\) - корень трёхчлена \(c x^{2} + b x + a\). Поэтому в задаче нужно найти наименьшее натуральное \(a\), для которого корни \(x_{1}\) и \(x_{2}\) некоторого трёхчлена \(c x^{2} + b x + a\) (с целыми \(b\) и \(c\) ) больше 1000. Поскольку \(x_{1}\) и \(x_{2}\) положительны и \(x_{1} x_{2} = a / c\) (по теореме Виета), имеем \(c > 0\).

Если \(c = 1\), то \(\left|x_{1}-x_{2}\right| = \sqrt{b^{2}-4 a} \geqslant 1\). Поскольку меньший корень не меньше 1000 , больший корень не меньше 1001 , а тогда \(a = x_{1} x_{2} \geqslant 1001 \cdot 1000\). Если же \(c \geqslant 2\), то \(a = c x_{1} x_{2} \geqslant 2 x_{1} x_{2} > > 2000000\). В обоих случаях требуемая оценка доказана.

Осталось заметить, что трёхчлен \(x^{2}-(1000 + 1001) x + + 1001 \cdot 1000\) имеет корни 1000 и 1001, поэтому \(a = 1001000\) подходит.

Второе решение. Положим для краткости \(n = 1000\). Пусть \(x_{1}\) и \(x_{2}\) - два различных корня трёхчлена \(f(x) = a x^{2} + b x + c\), причём \(0 < x_{1} < x_{2} \leqslant \frac{1}{n}\). Тогда число \(b = -a\left(x_{1} + x_{2}\right)\) отрицательно, а число \(c = a x_{1} x_{2}\) положительно. Более того, имеем \(\frac{-b}{a} = x_{1} + x_{2} < \frac{2}{n}\), откуда \(a > -\frac{n b}{2}\).

Поскольку корни различны, дискриминант \(D = b^{2}-4 a c\) положителен. Следовательно, \(b^{2} > 4 a c > -2 n b c\) и, значит, \(-b >\)

\(> 2 n c\). Поэтому \(a > (-b) \cdot \frac{n}{2} > 2 n c \cdot \frac{n}{2} = n^{2} c\). Пусть \(a = n^{2} c + d\), где \(d\) - натуральное число.

Предположим, что \(a < n^{2} + n\). Тогда \(c = 1\) и \(d < n\). Стало быть, \(0 \leqslant f\left(\frac{1}{n}\right) = \frac{a}{n^{2}} + \frac{b}{n} + c = \frac{d}{n^{2}} + \frac{b}{n} + 2 < \frac{1}{n} + \frac{b}{n} + 2\) и, значит, \(-b < 2 n + 1\). Следовательно, \(-b \leqslant 2 n\) и \(D = b^{2}-4 a c \leqslant 4 n^{2}- -4\left(n^{2} + d\right) = -4 d < 0\). Это противоречие показывает, что \(d \geqslant n\).

Если же \(a = n^{2} + n\), то при \(b = -2 n - 1\) и \(c = 1\) трёхчлен имеет корни \(x_{1} = \frac{1}{n + 1}\) и \(x_{2} = \frac{1}{n}\).

Назовём набор городов критическим, если есть ровно \(5 k + 10\) рейсов, соединяющих два города этой группы, где \(k\) - количество городов в группе (тогда \(k > 11\), ибо иначе между городами группы есть не более \(k(k - 1) / 2 \leqslant 5 k < 5 k + 10\) рейсов). Если группа из всех 998 городов критическая, то в стране уже \(5 \cdot 998 + 10 = 5000\) рейсов.

В дальнейшем мы всегда предполагаем, что законы в любой момент соблюдены. Обозначим через \(f(X)\) количество рейсов, соединяющих два города группы \(X\).

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

Лемма. Пусть \(A\) и \(B\) - критические группы. Тогда группа \(A \cup B\) также критическая.

Доказательство. Положим \(C = A \cap B, D = A \cup B\). Пусть \(|A| = a,|B| = b,|C| = c\); тогда \(|D| = a + b - c\). По условию, имеем \(f(A) = 5 a + 10, f(B) = 5 b + 10\) и \(f(C) \leqslant 5 c + 10\). Заметим, что все рейсы, посчитанные в \(f(A)\) и \(f(B)\), учитываются также и в \(f(D)\); более того, если какой-то рейс учтён и в \(f(A)\), и в \(f(B)\), то оба его конца лежат в \(C\), то есть количество дважды учтённых рейсов равно \(f(C)\). Поэтому

\(\begin{array}{c} f(D) \geqslant f(A) + f(B)-f(C) \geqslant(5 a + 10) + (5 b + 10)-(5 c + 10) = \\ = 5(a + b - c) + 10 = 5 d + 10 \end{array}\)

Учитывая, что законы соблюдены, получаем \(f(D) = 5 d + 10\), что и требовалось.

Вернёмся к решению. Если в настоящий момент нет ни одной критической группы, можно добавить рейс между любой парой городов, между которыми его ещё нет (такая пара найдётся!). Иначе, применяя лемму, получаем, что объединение всех критических групп-тоже критическая группа \(A\); по предположению, в ней \(a < 998\) городов. Пусть \(x\) - город вне \(A\); тогда \(x\) не входит ни в какую критическую группу.

Пусть из \(x\) идёт \(k\) рейсов в города из \(A\). Поскольку группа \(A^{\prime} = A \cup\{x\}\) не критическая, имеем

\(5(a + 1) + 10 > f\left(A^{\prime}\right) = f(A) + k = 5 a + 10 + k\)

откуда \(k < 5\). С другой стороны, \(a \geqslant 12\), поэтому в \(A\) есть город \(y\), не соединённый рейсом с \(x\), и города \(x\) и \(y\) не входят в одну критическую группу. Значит, министерство может ввести рейс между \(x\) и \(y\).

Пусть точки \(B^{\prime}, C^{\prime}\) и \(K^{\prime}\) симметричны относительно \(A\) точкам \(B, C\) и \(K\) соответственно. Тогда окружность \(\omega^{\prime}\) вписана в треугольник \(A B^{\prime} C^{\prime}\) и касается \(B^{\prime} C^{\prime}\) в точке \(K^{\prime}\). Медиана \(A M\) является средней линией в треугольниках \(B C C^{\prime}\) и \(B^{\prime} B C\), так что \(A M\left\|B C^{\prime}\right\| B^{\prime} C\). Поскольку \(A\) середина \(K K^{\prime}\), утверждение задачи равносильно тому, что прямая \(A M\) содержит среднюю линию треугольника \(K K^{\prime} A_{0}\) (параллельную \(A_{0} K^{\prime}\) ), то есть утверждение равносильно параллельности \(B^{\prime} C \| A_{0} K^{\prime}\).

Рис. 5

Пусть \(\omega\) касается \(A B\) и \(A C\) в точках \(X\) и \(Y\) соответственно, а \(\omega^{\prime}\) касается отрезков \(A B^{\prime}, A C^{\prime}, A_{0} B\) и \(A_{0} C\) в точках \(X^{\prime}\), \(Y^{\prime}, X_{0}\) и \(Y_{0}\) соответственно. Заметим, что \(A B - A C = (A X + + X B)-(A Y + Y C) = X B - Y C = K B - K C\). Аналогично, если вписанная окружность треугольника \(A_{0} B C\) касается \(B C\) в точке \(K_{0}\), то \(A_{0} B - A_{0} C = K_{0} B - K_{0} C\). Однако

\(\begin{array}{c} A_{0} B - A_{0} C = \left(A_{0} X_{0} + X_{0} B\right)-\left(A_{0} Y_{0} + Y_{0} C\right) = X_{0} B - Y_{0} C = \\ = X^{\prime} B - Y^{\prime} C = (X A + A B)-(Y A + A C) = A B - A C \end{array}\)

так что \(K B - K C = K_{0} B - K_{0} C\), и потому \(K = K_{0}\).

Из доказанного следует, что вневписанные окружности треугольников \(A B C\) и \(A_{0} B C\) также касаются отрезка \(B C\) в одной и той же точке \(N\), симметричной \(K\) относительно \(M\) (поскольку \(B N = C K\) ). Гомотетия с центром \(A_{0}\), переводящая прямую \(B C\) в прямую \(B^{\prime} C^{\prime}\), переводит вневписанную окружность треугольника \(A_{0} B C\) в окружность \(\omega^{\prime}\), то есть точку \(N\) - в \(K^{\prime}\). Значит, \(N\) лежит на прямой \(A_{0} K\); но, поскольку \(B N = C K = C^{\prime} K^{\prime}\), имеем \(K^{\prime} N \| B^{\prime} C\), то есть \(A_{0} K^{\prime} \| B^{\prime} C\), что и требовалось.

Замечание 1. После первого абзаца решение также можно завершить применением теоремы Брианшона к описанному (около \(\omega^{\prime}\) ) шестиугольнику \(A_{0} B B^{\prime} K^{\prime} C^{\prime} C\). Теорема утверждает, что три главных диагонали \(A_{0} K^{\prime}, B C^{\prime}, B^{\prime} C\) этого шестиугольника пересекаются в одной точке или попарно параллельны; в нашей задаче реализуется второй случай, то есть \(A_{0} K^{\prime}\left\|B C^{\prime}\right\| B^{\prime} C\).

Замечание 2. Из утверждения задачи следует, что центр \(I^{\prime}\) вписанной окружности треугольника \(A_{0} B C\) лежит на \(A M\). Существуют способы решить задачу, доказав этот факт.

Пусть одно из чисел равно 10 , а каждое из остальных равно -1 . Тогда произведение любых пяти из них больше, чем произведение остальных шести. Действительно, если число 10 входит в произведение пяти чисел, то это произведение равно 10 , а произведение оставшихся шести чисел равно 1, и \(10 > 1\). Если же число 10 не входит в произведение пяти чисел, то это произведение равно -1 , а произведение оставшихся шести чисел равно -10 , и \(-1 > -10\).

Обозначим через \(N\) количество способов вырезать из полоски последовательность \(1 \underbrace{00 \ldots 0}_{\geqslant n - 2} 1\) (т.е. количество последовательностей из хотя бы \(n - 2\) нулей, перед и после которых стоят единицы). Перед каждой из них может стоять или 1 , или 0 ; обозначим количество тех, перед которыми стоят 1 , через \(N_{1 x}\), перед которыми стоят 0-через \(N_{0 x}\). После каждой из \(N\) последовательностей может стоять или 0 , или 1 ; аналогично предыдущему предложению введём количества \(N_{x 0}\) и \(N_{x 1}\). Tогда

\(N_{0 x} + N_{1 x} = N = N_{x 0} + N_{x 1} .\)

Заметим, что \(N_{1 x}\) - это количество способов вырезать последовательность \(11 \underbrace{00 \ldots 0}_{\geqslant n - 2} 1\). Каждый такой способ соответствует способу вырезать последовательность \(11 \underbrace{00 \ldots 0}_{n - 2}\); и наоборот, каждый способ вырезать последовательность \(11 \underbrace{00 \ldots 0}_{n - 2}\) можно единственным образом дополнить до способа вырезать последовательность \(11 \underbrace{00 \ldots 0}_{\geqslant n - 2} 1\). Значит, количества таких способов одинаковые, и \(N_{1 x} = M\). Аналогично \(N_{0 x}, N_{x 0}\) и \(N_{x 1}\) равняются количествам способов вырезать последовательности \(01 \underbrace{00 \ldots 0}_{n - 2}, \underbrace{00 \ldots 0}_{n - 2} 10\) и \(\underbrace{00 \ldots 0}_{n - 2} 11\) соответственно. По условию, последовательность \(\underbrace{00 \ldots 0}_{n - 2} 11\) встречается наименьшее число раз, откуда \(N_{0 x} \geqslant N_{x 1}\). Тогда, с учётом ( \(*\) ), получаем \(N_{x 0} \geqslant N_{1 x} = = M\), что возможно только при \(N_{x 0} = M\). Значит, последовательность \(\underbrace{00 \ldots 0}_{n - 2} 10\) также встречается ровно \(M\) раз.

Замечание. То же самое решение можно изложить на немного другом языке. Обозначим через \(x^{k}\) последовательность из \(k\) букв \(x\). Для слова \(w\) обозначим через \(f(w)\) количество способов вырезать \(w\) из полоски. Тогда для любого слова \(w\) выполнено равенство \(f(w) = f(0 w) + f(1 w) = f(w 0) + f(w 1)\).

Заметим, что \(f\left(10^{n - 1}\right) + f\left(0^{n}\right) = f\left(0^{n - 1}\right) = f\left(0^{n}\right) + f\left(0^{n - 1} 1\right)\), так что \(f\left(10^{n - 1}\right) = f\left(0^{n - 1} 1\right)\).

Теперь

\(\begin{array}{l} f\left(110^{n - 2}\right) + f\left(010^{n - 2}\right) = f\left(10^{n - 2}\right) = f\left(10^{n - 2} 1\right) + f\left(10^{n - 1}\right) = \\ \quad = f\left(10^{n - 2} 1\right) + f\left(0^{n - 1} 1\right) = f\left(0^{n - 2} 1\right) = f\left(0^{n - 2} 11\right) + f\left(0^{n - 2} 10\right) \end{array}\)

Таким образом, разность между наибольшим и наименьшим количествами способов равна

\(f\left(110^{n - 2}\right)-f\left(0^{n - 2} 11\right) = f\left(0^{n - 2} 10\right)-f\left(010^{n - 2}\right) .\)

В частности, должно выполняться \(f\left(0^{n - 2} 10\right) = M\).

Пусть число \(N\) состоит из \(k + 1\) цифры. Считаем далее, что \(k > 100\) : меньшие числа не влияют на искомую ограниченность.

Для \(i = 1, \ldots, k\) обозначим через \(n_{i}\) число, получающееся удалением из \(N i\)-ой с конца цифры. Обозначим через \(f(N)\) количество точных квадратов в множестве \(\left\{n_{1}, \ldots, n_{k}\right\}\). Наша цель-доказать, что \(f(N)\) ограничено сверху.

Пусть \(N = 10^{t} N_{1}\), где \(N_{1}\) не кратно 10. Если \(t\) нечётно, то число \(n_{i}\) может быть точным квадратом только при \(i \leqslant t + 1\), так что в этом случае \(f(N) \leqslant 2\). Если \(t\) чётно, то заключительные \(t\) нулей не влияют на дело, поэтому \(f(N) = f\left(N_{1}\right)\). Поэтому далее считаем, что \(N\) не кратно 10 .

Выделим множество \(A \subset\{1, \ldots, k\}\) из \(f(N)\) номеров \(i\), для которых \(n_{i} = m_{i}^{2}\) - точный квадрат, причём натуральные числа \(m_{i}, i \in A\), попарно различны.

Отметим следующее : 1) \(n_{i} \geqslant 10^{k - 1}\), следовательно \(m_{i} \geqslant 10^{(k - 1) / 2}\) при всех \(i \in A\);

2) \(\left|n_{i}-n_{j}\right| < 10^{\max (i, j)}\);

3) \(N - n_{i}\) кратно \(10^{i - 1}\).

Из свойства 1) следует, что для различных номеров \(i \neq j\) из \(A\) имеет место оценка

\(\left|n_{i}-n_{j}\right| = \left|m_{i}^{2}-m_{j}^{2}\right| \geqslant m_{i} + m_{j} \geqslant 2 \cdot 10^{(k - 1) / 2} .\)

Сопоставляя это со свойством 2), получаем, что \(\max (i, j) > (k- -1) / 2\). Таким образом, все элементы \(A\), кроме, быть может, одного, больше, чем \((k - 1) / 2\). Обозначим \(A_{1} : = A \backslash\{\min (A)\}\) (удалили из \(A\) наименьший элемент), тогда \(\left|A_{1}\right| = f(N)-1\) и \(\min \left(A_{1}\right) \geqslant k / 2\).

Пусть \(j > i\) - два элемента множества \(A_{1}\). Тогда по свойствам 1), 2) имеем

\(10^{j} > \left|n_{i}-n_{j}\right| = \left|m_{i}^{2}-m_{j}^{2}\right| \geqslant 2 \cdot 10^{(k - 1) / 2} \cdot\left|m_{i}-m_{j}\right| .\)

С другой стороны, по свойству 3) число \(n_{i}-n_{j} = \left(m_{i}-m_{j}\right)\left(m_{i} + \right. \left. + m_{j}\right)\) кратно \(10^{i - 1}\).

Положим \(r = \lceil(i - 1) / 2\rceil\) (где \(\lceil\cdot\rceil\) обозначает верхнюю целую часть). Хотя бы одно из чисел \(m_{i}-m_{j}, m_{i} + m_{j}\) кратно \(2^{r}\), и хотя бы одно кратно \(5^{r}\). Кроме того, если \(N\) нечётно, то нечётны числа \(m_{i}, m_{j}\), поэтому одно из чисел \(m_{i}-m_{j}, m_{i} + m_{j}\) не кратно 4-а другое, соответственно, кратно \(2^{i - 2}\). Иначе \(N\) не кратно 5 , и аналогичным образом получаем, что одно из чисел \(m_{i}-m_{j}\), \(m_{i} + m_{j}\) кратно \(5^{i - 1}\).

Рассмотрим пятиэлементное подмножество \(\tilde{A} \subset A_{1}\), наименьший элемент \(\tilde{A}\) обозначим \(u\), а наибольший \(v\). Обозначим \(r = \lceil(u - 1) / 2\rceil\). Если \(N\) нечётно, положим \(\alpha = u - 2, \beta = r\); иначе положим \(\alpha = r, \beta = u - 1\). Из доказанного следует, что элементы множества \(\left\{m_{s} : s \in \tilde{A}\right\}\) дают не более двух различных остатков по модулю \(2^{\alpha}\) и не более двух различных остатков по модулю \(5^{\beta}\). Значит, в \(\tilde{A}\) найдутся два различных элемента \(i < j\) такие, что \(m_{j}-m_{i}\) кратно \(2^{\alpha} 5^{\beta}\). Тогда по (1) получаем

\(\begin{aligned} 10^{v} & \geqslant 10^{j} \geqslant 2 \cdot 10^{(k - 1) / 2} 2^{\alpha} 5^{\beta} \geqslant \\ & \geqslant 10^{(k - 1) / 2 + (u - 1) / 2} 2^{(u - 1) / 2} > 10^{u - 1} 2^{u / 2} \end{aligned}\)

откуда следует что \(v / u > 1,01\). Таким образом, если разбить отрезок \([k / 2, k]\) на группы подряд идущих чисел, в каждой из которых отношение любых двух элементов меньше чем 1,01 (количество таких групп меньше, например, миллиона), то любая из этих групп содержит не более 4 элементов множества \(A_{1}\). Отсюда вытекает ограниченность числа \(\left|A_{1}\right| = f(N)-1\).

Первое решение. Обозначим точку касания окружности ( \(A B E\) ) с отрезком \(C F\) через \(P\). Пусть прямая, проходящая через \(C\) и параллельная \(A P\), пересекает отрезок \(A E\) в точке \(Q\) (см. рис. 2). Тогда \(\angle Q C P = \angle A P F = \angle A E P\) (из упомянутых выше касания и параллельности). Значит, четырёхугольник \(C E Q P\) вписанный. Имеем \(\angle Q P C = 180^{\circ}-\angle Q E C = \angle Q A F\). Следовательно, четырёхугольник \(Q P F A\) вписанный. Тогда \(\angle A Q F = = \angle A P F = \angle Q C P\), откуда \(Q F \| E P\). Значит, прямые \(C Q\), \(E P, P A\) и \(Q F\) ограничивают параллелограмм, откуда \(\angle C Q F = = \angle A P E\). Так как \(\angle A P E = 180^{\circ}-\angle A B C = 180^{\circ}-\angle C D F\), то точка \(Q\) лежит на окружности ( \(C D F\) ). Раз \(\angle A Q F = \angle Q C P\), то окружность ( \(C D F\) ) касается отрезка \(A E\) в точке \(Q\), что и требовалось.

Рис. 2

Рис. 3

Второе решение. Обозначим через \(O_{1}\) центр окружности \((A B E)\), пусть \(R_{1}\) — её радиус и \(d_{1}\) — расстояние от точки \(O_{1}\) до прямой \(C F\). Обозначим через \(O_{2}\) центр окружности \((C D F)\), пусть \(R_{2}\) — её радиус и \(d_{2}\) — расстояние от точки \(O_{2}\) до прямой \(A E\). Мы докажем более общий факт: \(d_{1}/R_{1}=d_{2}/R_{2}\) \((\star)\).

В частности, если \(d_{1}=R_{1}\), то \(d_{2}=R_{2}\), и первое равносильно касанию прямой \(C F\) и окружности \((A B E)\), второе — касанию прямой \(A E\) и окружности \((C D F)\).

Если \(A E \parallel C F\), то точки \(E\) и \(F\), а также \(O_{1}\) и \(O_{2}\) симметричны относительно центра параллелограмма, и в силу этой центральной симметрии \(d_{1}=d_{2}\) и \(R_{1}=R_{2}\), откуда следует \((\star)\).

Иначе без ограничения общности будем считать, что луч \(A E\) пересекает луч \(F C\), обозначим их точку пересечения через \(K\) (см. рис. 3).

Обозначим через \(\alpha\) углы при вершинах \(B\) и \(D\) параллелограмма \(A B C D\). Разберём случай \(\alpha<90^{\circ}\), в других случаях рассуждение аналогично. Тогда \(\angle A O_{1} E=2\alpha=\angle C O_{2} F\), поэтому равнобедренные треугольники \(A O_{1} E\) и \(C O_{2} F\) подобны, откуда \(\angle E A O_{1}=\angle C F O_{2}\) и \(\frac{R_{1}}{R_{2}}=\frac{O_{1}A}{O_{2}F}=\frac{A E}{C F}=\frac{K A}{K F}\) (последнее равенство следует из теоремы Фалеса). Следовательно, треугольники \(K A O_{1}\) и \(K F O_{2}\) подобны по углу и отношению заключающих сторон. Значит, \(\frac{O_{1}K}{O_{2}K}=\frac{O_{1}A}{O_{2}F}=\frac{R_{1}}{R_{2}}\) и \(\angle O_{1} K A=\angle O_{2} K F\). Тогда \(\angle O_{1} K F=\angle O_{2} K A\), следовательно, \(\frac{d_{1}}{d_{2}}=\frac{O_{1}K}{O_{2}K}=\frac{R_{1}}{R_{2}}\), что и требовалось.

Замечание. Соотношение \((\star)\) равносильно тому, что угол между окружностью \((A B E)\) и прямой \(C F\) равен углу между окружностью \((C D F)\) и прямой \(A E\).

Третье решение. Пусть окружность \((A B E)\) касается отрезка \(C F\) в точке \(P\) и вторично пересекает прямую \(A D\) в точке \(X\). Обозначим вторую точку пересечения окружности \((F C D)\) с прямой \(B C\) через \(Y\) (см. рис. 4). Тогда отрезки \(X E\) и \(A B\) симметричны относительно серединного перпендикуляра к \(B E\), а отрезки \(C D\) и \(Y F\) — относительно серединного перпендикуляра к \(D F\), поэтому \(\overrightarrow{X E}=\overrightarrow{F Y}\). Поскольку окружность \((A B E)\) касается отрезка \(C F\), то точка \(X\) лежит на луче \(F A\). Значит, точка \(Y\) лежит на луче \(E C\), причём \(X F=E Y\).

Поскольку окружность \((A B E X)\) касается отрезка \(C F\) в точке \(P\), имеем \(C P^{2}=C E \cdot C B\) и \(F P^{2}=F A \cdot F X\). Значит, \(C F=\sqrt{C E \cdot C B}+\sqrt{F X \cdot F A}\) \((\star)\).

Мы позднее докажем, что отсюда следует равенство \(A E=\sqrt{A F \cdot A D}+\sqrt{E Y \cdot Y C}\) \((\star\star)\), сначала завершим решение задачи с его помощью: отметим на отрезке \(A E\) точку \(T\) так, что \(E T=\sqrt{E Y \cdot E C}\) и \(A T=\sqrt{A F \cdot A D}\). Ecли точка \(T\) отлична от концов отрезка \(A E\), полученные равенства означают, что окружности \((Y C T)\) и \((F D T)\) касаются прямой \(A E\) в точке \(T\). Если эти окружности не совпадают, то они обе не совпадают и с окружностью \((F Y C D)\), но в таком случае \(A E\), \(B C\) и \(A D\) — радикальные оси этих трёх окружностей. Однако прямые \(B C\) и \(A E\) пересекаются в точке \(E\), не лежащей на прямой \(A D\), противоречие. Значит, на самом деле окружности \((Y C T)\) и \((F D T)\) совпадают, а тогда это и есть окружность \((C D F)\), и она касается \(A E\) в точке \(T\). Если точки \(Y\) и \(C\) совпадают, нужно, как обычно, под окружностью \((Y C T)\) понимать окружность, проходящую через \(T\) и касающуюся \(B C\) в точке \(Y\). В случае, когда \(T\) совпадает с одним из концов отрезка \(A E\), возможна лишь ситуация \(T=E\), и тогда \(E Y=0\), то есть \(E=Y\), а также \(A E^{2}=A F \cdot A D\). Итого, окружность \((C F D)\) касается \(A E\) в точке \(E\).

Остаётся доказать соотношение \((\star\star)\). Положим \(E Y=a\), \(E C=x\), \(A F=y\). Из сказанного выше, векторы \(\overrightarrow{B A}, \overrightarrow{X E}, \overrightarrow{F Y}, \overrightarrow{C D}\) равны по длине, обозначим её \(b\), а также равны их проекции на ось, сонаправленную вектору \(\overrightarrow{B C}\), обозначим такую проекцию \(h\). Положим \(d=2h-a\). Тогда \(B E=y+d\) и \(D F=x+d\).

По теореме Птолемея для четырёхугольников \(F Y C D\) и \(A B E X\) мы получаем, что \(C F^{2}=b^{2}+(x+d)(x-a)\) и \(A E^{2}=b^{2}+(y+d)(y-a)\). Отметим, что эти равенства будут выполняться вне зависимости от взаимного расположения точек \(A\) и \(X\), \(C\) и \(Y\). Итого, соотношение \((\star)\) имеет вид

\(\displaystyle \sqrt{b^{2}+(x+d)(x-a)}=\sqrt{x(x+y+d)}+\sqrt{a y}.\)

После возведения в квадрат и сокращения общих слагаемых получается симметричное по \(x\) и \(y\) равенство:

\(\displaystyle b^{2}=a(x+y)+ad+xy+2\sqrt{a x y(x+y+d)}.\)

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

\(\displaystyle \sqrt{b^{2}+(y+d)(y-a)}=\sqrt{y(x+y+d)}+\sqrt{a x},\)

а это в точности соотношение \((\star\star)\), что и требовалось.

Замечание. Точка \(T\) совпадает с точкой \(Q\) из решения 1.

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

Оценка. Рассмотрим некоторую прямую \(\ell\), которая не перпендикулярна ни одному из наших лучей. Рассмотрим проекции наших лучей на \(\ell\), среди них не менее \(\left\lceil\frac{n}{2}\right\rceil = \left[\frac{n + 1}{2}\right]\) направлены в одну сторону (будем говорить, что вправо), забудем про остальные лучи. Пусть точка \(X\) на прямой принадлежит всем выбранным проекциям, выберем произвольную точку \(Y \in \ell\) правее. Пусть \(\alpha_{X}\) и \(\alpha_{Y}\) - плоскости, перпендикулярные прямой \(\ell\), проходящие через \(X\) и \(Y\) соответственно. Каждый из выбранных

нами лучей пересекает обе эти плоскости. Выберем достаточно большое \(R\) такое, чтобы окружность \(\omega \subset \alpha_{Y}\) с центром \(Y\) и радиуса \(R\) содержала внутри все точки пересечения плоскости \(\alpha_{Y}\) с выбранными лучами. Рассмотрим сферу \(\Omega\), которая касается плоскости \(\alpha_{X}\) в точке \(X\) и содержит окружность \(\omega\). Рассмотрим любой из наших лучей. Он проходит через точку внутри сферы \(\Omega\), а его начало лежит в другом полупространстве относительно плоскости \(\alpha_{X}\), нежели \(\Omega\), поэтому он пересекает \(\Omega\) в двух точках. Таким образом, мы получили \(k = 2\left\lceil\frac{n}{2}\right\rceil\) точек пересечения.

Обозначим треугольник, образованный синими лучами, через \(A_{1} B_{1} C_{1}\) (как на рисунке), и пусть его описанная окружность касается окружности ( \(A B C\) ). Пусть окружность ( \(A_{1} B C\) ) вторично пересекает окружность ( \(A B_{1} C\) ) в точке \(P\) (которая, очевидно, лежит внутри треугольника \(A_{1} B_{1} C_{1}\) ). Тогда \(\angle A P C = \angle A B_{1} C\) и \(\angle B P C = \angle B A_{1} C\). Поскольку также \(\angle A P B + \angle B P C + \angle A P C = 360^{\circ} = \angle A B_{1} C + \angle A C_{1} B + + \angle B A_{1} C\) (второе равенство-сумма внешних углов треугольника \(A_{1} B_{1} C_{1}\) ), то \(\angle A P B = \angle A C_{1} B\). Таким образом, точка \(P\) лежит и на окружности \(\left(A C_{1} B\right)\).

Рис. 5

Сделаем инверсию с центром в точке \(P\) (и с произвольным радиусом), образы точек будем обозначать теми же буквами со штрихами. Напомним, что для любых точек \(X\) и \(Y\) треугольники \(X P Y\) и \(Y^{\prime} P X^{\prime}\) подобны (по углу и отношению заключающих сторон), поэтому \(\angle X^{\prime} Y^{\prime} P = \angle P X Y\).

Докажем, что треугольник \(A_{1}^{\prime} B_{1}^{\prime} C_{1}^{\prime}\) подобен треугольнику \(A B C\). Действительно, \(\angle B_{1}^{\prime} A_{1}^{\prime} C_{1}^{\prime} = \angle B_{1}^{\prime} A_{1}^{\prime} P + \angle P A_{1}^{\prime} C_{1}^{\prime} = = \angle P B_{1} A_{1} + \angle A_{1} C_{1} P = \angle P A C + \angle B A P = \angle B A C\), аналогично для остальных углов.

Окружность \(\left(C P A_{1} B\right)\) при инверсии перейдет в прямую \(C^{\prime} B^{\prime}\), проходящую через вершину \(A_{1}^{\prime}\) треугольника \(A_{1}^{\prime} B_{1}^{\prime} C_{1}^{\prime}\). Найдем угол между этой прямой и стороной \(A_{1}^{\prime} B_{1}^{\prime} : \angle B^{\prime} A_{1}^{\prime} B_{1}^{\prime} = = \angle P A_{1}^{\prime} B_{1}^{\prime}-\angle P A_{1}^{\prime} B^{\prime} = \angle A_{1} B_{1} P-\angle A_{1} B P = \angle A_{1} B_{1} P- -\angle A_{1} C P = \angle C P B_{1} = \angle C A B_{1}\). Вместе с двумя аналогичными равенствами отсюда следует, что в подобных треугольниках \(A B C\) и \(A_{1}^{\prime} B_{1}^{\prime} C_{1}^{\prime}\) красные лучи в первом и лучи \(A_{1}^{\prime} B^{\prime}, B_{1}^{\prime} C^{\prime}, C_{1}^{\prime} A^{\prime}\) во втором-соответствующие элементы. Окружности \(\left(A_{1}^{\prime} B_{1}^{\prime} C_{1}^{\prime}\right)\) и ( \(A^{\prime} B^{\prime} C^{\prime}\) ) касаются (поскольку они получены инверсией из касающихся окружностей), а тогда и окружность ( \(A B C\) ) касается описанной окружности треугольника, ограниченного красными лучами, что и требовалось.

Замечание. Из решения следует более общий факт : углы между окружностью \((A B C)\) и окружностями, описанными около красного и синего треугольника, одинаковы.