Первое решение. Заметим, что разность корней приведённого квадратного трёхчлена \(x^{2} + b x + c\) равна корню из его дискриминанта, то есть \(\sqrt{b^{2}-4 c}\).

Пусть два данных трёхчлена-это \(f(x) = x^{2} + b_{1} x + c_{1}\) и \(g(x) = x^{2} + b_{2} x + c_{2}\). Согласно условию, у них общий дискриминант \(D = b_{1}^{2}-4 c_{1} = b_{2}^{2}-4 c_{2}\). Вместо суммы трёхчленов удобно рассмотреть их полусумму-она тоже является приведённым квадратным трёхчленом. Квадрат разности его корней (т.е. дискриминант) равен

\(\left(\frac{b_{1} + b_{2}}{2}\right)^{2}-2\left(c_{1} + c_{2}\right) = \frac{b_{1}^{2} + b_{2}^{2}}{2}-2\left(c_{1} + c_{2}\right)-\left(\frac{b_{1}-b_{2}}{2}\right)^{2} .\)

Значит, он не больше, чем \(\frac{b_{1}^{2} + b_{2}^{2}}{2}-2\left(c_{1} + c_{2}\right) = \frac{D}{2} + \frac{D}{2} = D\). Отсюда и следует, что разность корней полусуммы не больше, чем \(\sqrt{D}\), то есть разность корней каждого из данных трёхчленов.

Замечание. В оценке выше можно было воспользоваться неравенством о средних \(\sqrt{\frac{b_{1}^{2} + b_{2}^{2}}{2}} \geqslant \frac{b_{1} + b_{2}}{2}\).

Второе решение. Заметим, что любой приведённый квадратный трёхчлен с двумя корнями имеет вид \((x - p)^{2}-q^{2}\) при \(q \geqslant 0\). При этом разность его корней равна \(2 q\), а его наименьшее значение равно \(-q^{2}\).

Теперь условие означает, что два данных трёхчлена имеют равные наименьшие значения \(-q^{2}\). Наименьшее значение их полусуммы, очевидно, не меньше \(-q^{2}\) (оно является полусуммой каких-то значений исходных трёхчленов), то есть оно равно \(-r^{2}\)

при \(0 \leqslant r \leqslant q\). Поэтому и разность корней полусуммы, то есть \(2 r\), не превосходит \(2 q\).

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

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

Действительно, пусть для некоторой операции выбран кусок, в котором по \(y\) букв А и Б, причём \(t\) из этих букв А стоят на нечётных местах. Тогда на чётных местах в куске стоят \(y - t\) букв А и, следовательно, \(y-(y - t) = t\) букв Б. После операции именно из этих \(t\) букв Б возникнут буквы А, стоящие

на нечётных местах куска-значит, количество таких букв А не поменяется.

Итак, в любой полученной строке будет ровно \(x\) букв А на нечётных местах. Однако, если строка развернётся задом наперёд, то на нечётных местах должны оказаться ровно те буквы, которые раньше были на чётных местах, а там было ровно \(125-x\) букв А. Поскольку \(125-x \neq x\), требуемое невозможно.

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

Второе решение. Предъявим ещё один инвариант. В строке всего \(125^{2}\) пар, состоящих из буквы А и буквы Б. Назовём такую пару левой, если в ней А стоит левее Б, и правой иначе. Покажем, что при операции количество левых пар не изменяется. Из этого будет следовать невозможность требуемого, ибо при развороте строки все пары меняют тип, а значит, количество левых пар меняет чётность.

Рассмотрим одну операцию с куском длины \(2 y\). При этой операции пары из букв, не лежащих в куске, сохраняют свой тип. Далее, для каждой буквы вне куска было ровно \(y\) пар, содержащих её и букву из куска; столько же таких пар осталось, и все эти пары были и стали одного и того же типа.

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

Пусть \(A B C\) - данный треугольник, \(O\) - центр его описанной окружности, \(D, E, F\) - середины его сторон \(B C\), \(C A, A B\) соответственно, так что \(D E F\) подобен \(A B C\) с коэффициентом \(1 / 2\) и \(O D \perp B C, O E \perp C A, O F \perp A B\).

Пусть при повороте вокруг \(O\) по часовой стрелке на угол \(120^{\circ}\) точка \(D\) переходит в \(D^{\prime}\). При таком повороте прямая \(B C\) переходит в перпендикуляр к \(O D^{\prime}\), проходящий через \(D^{\prime}\), пусть этот перпендикуляр пересекает \(B C\) в точке \(K\) (см. рис. 3). Видим, что прямоугольные треугольники \(O D K\) и \(O D^{\prime} K\) равны (симметричны относительно \(O K\) ), и поэтому \(\angle K O D = = \angle D O D^{\prime} / 2 = 60^{\circ}\), значит, в прямоугольном треугольнике \(K O D\) верно \(O K = 2 O D\). Иными словами, \(K\) получается из \(D\) в результате поворотной гомотетии : поворота с центром \(O\) по часовой стрелке на угол \(60^{\circ}\) и последующей гомотетии с центром \(O\) и коэффициентом 2. Аналогичный результат получим

Рис. 3

для других точек \(L, M\) пересечения одноцветных прямых. Таким образом, треугольник \(K L M\) получается из \(D E F\) поворотной гомотетией с центром \(O\) и коэффициентом 2. Тогда \(K L M\) подобен \(D E F\) с коэффициентом 2 , следовательно, равен \(A B C\).

На 1-м шаге у каждого из 100 человек было выписано одно из чисел множества \(A_{1} = \{0,1,2, \ldots, 100\}\).

На 2-м шаге-одно из чисел множества \(A_{2} = = \left\{\frac{1}{2}, \frac{2}{2}, \frac{3}{2}, \ldots, \frac{199}{2}\right\}\).

На 100-м шаге выписано одно из чисел множества \(A_{100} = = \left\{\frac{S}{100}, \frac{S - 1}{100}, \frac{S - 2}{100}, \ldots, \frac{S - 100}{100}\right\}\), где \(S = \frac{100 \cdot 101}{2}\) - сумма всех чисел (а вычитается-число на оставшейся в конце карточке).

Видим, что \(A_{1} \cup A_{2} = \left\{0, \frac{1}{2}, \frac{2}{2}, \frac{3}{2}, \ldots, \frac{199}{2}, \frac{200}{2}\right\}\), так что \(\left|A_{1} \cup A_{2}\right| = 201\). Далее, \(\left|A_{100}\right| = 101\), но числа \(50-\frac{1}{2}, 50,50 + \frac{1}{2}\) принадлежат \(A_{2} \cap A_{100}\), значит, \(\left|A_{1} \cup A_{2} \cup A_{100}\right| \leqslant 201 + 101- -3 = 299\).

Итак, мы показали, что 300 чисел, выписанных на \(1-м, 2-м\) и 100-м шагах, могут принимать не более 299 различных значений. Следовательно, какие-то два из них равны.

При \(n = 20\) ! имеем \(\frac{n(n + 1)(n + 2) \ldots(n + 20)}{n^{2}} = = \frac{(n + 1)(n + 2) \ldots(n + 20)}{20!} = C_{n + 20}^{20}\) - целое число.

Пусть теперь \(n > 20!\) и пусть \(P = n(n + 1)(n + 2) \ldots(n + 20)\) делится на \(k^{2}\), где \(k = n + i, i \in\{0,1,2, \ldots, 20\}\). Имеем \(P / k = = (k - i)(k - i + 1) \ldots(k - 1)(k + 1)(k + 2) \ldots(k + j)\), где \(j = 20-i\). Заметим, что число \(P / k \equiv(-1)^{i} i!j!(\bmod k)\) должно делиться на \(k\). Но \(0 < i!j!\leqslant i!\cdot(i + 1)(i + 2) \ldots(i + j) = 20! < n \leqslant k\), значит, \(i!j!\) не делится на \(k\). Противоречие.

Положим \(a = \sin x + \operatorname{tg} x\) и \(b = \cos x + \operatorname{ctg} x\). Введём обозначения : \(u = \sin x + \cos x\) и \(v = \sin x \cdot \cos x\). По условию рациональными являются числа \(c = a + b = u + \frac{1}{v}\) и \(d = a \cdot b = v + u + 1\). Отсюда \(k = d - c = v + 1-\frac{1}{v}\). Значит, \(t = \sin 2 x = 2 v\) - корень квадратного уравнения \(t^{2} + 2 t-(4 + + 2 k t) = 0\) с рациональными коэффициентами, откуда следует требуемое.

Из условия задачи мы сразу получаем, что \(\angle X Y Z = 90^{\circ} = \angle X T Z\). Обозначим через \(Q\) точку пересечения прямых \(X Y\) и \(Z T\), через \(R\) - точку пересечения прямых \(Z Y\) и \(X T\) (см. рис. 7). Без ограничения общности можно считать, что точка \(Z\) лежит на отрезках \(R Y\) и \(Q T\). Поскольку точка \(R\) лежит и в плоскости \(A B D\), и в плоскости \(B C D\), то она лежит на прямой \(B D\). Аналогично, точка \(Q\) лежит на прямой \(A C\).

Рис. 7

Рис. 8

Заметим, что \(R Y\) и \(Q T\) - высоты треугольника \(X Q R\). Tогда \(Z\) - точка пересечения высот этого треугольника, и поэтому \(X Z \perp Q R\). Пусть \(M\) - середина отрезка \(Q R\). Поскольку \(\angle Q Y R = 90^{\circ}\), то \(Y M = M R = R Q\) по свойству медианы прямоугольного треугольника. Значит, \(\angle M Y R = \angle Y R Q = = 90^{\circ}-\angle X Q R = \angle Z X Q\). Следовательно, прямая \(Y M\) касается окружности \(\omega\). Аналогично, прямая \(T M\) тоже касается окружности \(\omega\), поэтому точки \(M\) и \(P\) совпадают.

Рассмотрим две параллельные плоскости \(\beta\) и \(\gamma\), одна из которых содержит отрезок \(A C\), а другая-отрезок \(B D\). Заметим, что середины всех отрезков, соединяющих точку из плоскости \(\beta\) и точку из плоскости \(\gamma\), лежат в одной плоскости, параллельной \(\beta\) и \(\gamma\). Действительно, если ввести декартовы координаты так, что одна из плоскостей задаётся уравнением \(z = 0\), а другая уравнением \(z = h\) (где \(h\) есть расстояние между плоскостями \(\beta\) и \(\gamma\) ), то середины всех рассматриваемых отрезков лежат в плоскости \(z = h / 2\). Применяя это наблюдение для отрезков \(A B\), \(B C, C D, D A, Q R\), мы получаем, что их середины лежат в одной плоскости, что и требовалось.

Первое решение. Предположим, что это возможно.

Лемма. Пусть число \(n\) синее; тогда \(n^{2}\) - красное.

Доказательство. Поскольку \(n\) синее, числа \(n - 1\) и \(n + 1\) красные, иначе два синих числа отличаются на 1 . Поэтому число \(n^{2}-1 = (n - 1)(n + 1)\) синее. Значит, \(n^{2}\) красное.

Очевидно, что существует синее число \(k > 1001\); по лемме число \(k^{2}\) красное. Рассмотрим два случая.

Пусть число \(k^{3}\) синее. Тогда по лемме число \(k^{6} = \left(k^{3}\right)^{2}\) красное. Поскольку \(k^{2} \cdot k^{4} = k^{6}\), и числа \(k^{2}\) и \(k^{6}\) красные, то число \(k^{4}\) обязано быть синим. По лемме число \(k^{8} = \left(k^{4}\right)^{2}\) красное, но оно является произведением красных чисел \(k^{2}\) и \(k^{6}\). Этого не может быть.

Пусть теперь число \(k^{3}\) красное. Тогда число \(k^{5} = k^{2} \cdot k^{3}\) синее, и по лемме число \(k^{10} = \left(k^{5}\right)^{2}\) красное. Поскольку \(k^{10} = = k^{2} \cdot k^{8} = k^{3} \cdot k^{7}\) и числа \(k^{2}\) и \(k^{3}\) красные, числа \(k^{7}\) и \(k^{8}\) должны быть синими, а тогда, по лемме, числа \(k^{14} = \left(k^{7}\right)^{2}\) и \(k^{16} = \left(k^{8}\right)^{2}\) красные. Но тогда красное число \(k^{16}\) равно произведению красных чисел \(k^{2}\) и \(k^{14}\). Противоречие.

Второе решение. Опять же предположим противное. Начнём со следующего замечания. Пусть \(a\) и \(b\) - два различных красных числа; тогда число \(a b + 1\) тоже красное. Действительно, по условию число \(a b\) синее, а тогда \(a b + 1\) красное.

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

числа, отличающихся на 1-пусть это \(a\) и \(a + 1\). Из условия их общий цвет-красный.

Из замечания выше получаем сначала, что число \(b = a^{2} + + a + 1 = a(a + 1) + 1\) красное, а затем-что число \(c = a^{3} + + a^{2} + a + 1 = a b + 1\) тоже красное. Значит, по условию, число \(d = a^{4} + 2 a^{3} + 2 a^{2} + 2 a + 1 = (a + 1) c\) синее.

С другой стороны, из того же замечания число \(p = (a + + 1) b + 1 = a^{3} + 2 a^{2} + 2 a + 2\) красное. Значит, по условию, число \(a p = a^{4} + 2 a^{3} + 2 a^{2} + 2 a = d - 1\) тоже синее. Итак, мы нашли два соседних синих числа \(d\) и \(d - 1\), что невозможно.

Обозначим через \(\Gamma\) окружность с диаметром \(I_{B} I_{C}\). Поскольку \(C I_{C} \perp C I_{B}\) и \(B I_{C} \perp B I_{B}\), точки \(B\) и \(C\) лежат на \(\Gamma\) (см. рис. 1).

Обозначим через \(I\) центр вписанной окружности \(A B C\). Если точка \(X\) лежит внутри угла \(B I C\), то углы \(X B I_{C}\) и \(X C I_{B}\) тупые, поэтому \(X I_{B} > X C\) и \(X I_{C} > X B\). Перемножив эти неравенства, получим требуемое.

В противном случае точки \(X\) и \(A\) лежат в одной полуРис. 1

плоскости относительно прямой \(B C\). Продлим лучи \(C X\) и \(I_{B} X\) до пересечения с \(\Gamma\) в точках \(C_{1}\) и \(Y\) соответственно. Поскольку четырёхугольник \(A I_{C} B I\) вписан в окружность с диаметром \(I I_{C}\), то \(\angle X C_{1} B = \angle I I_{C} B = \angle I A B = \frac{1}{2} \angle C A B < \frac{1}{2} \angle C X B = = \frac{1}{2}\left(\angle X C_{1} B + \angle X B C_{1}\right)\), откуда \(\angle X C_{1} B < \angle X B C_{1}\), поэтому \(X C_{1} > X B\). Кроме того, поскольку длина хорды окружности не превосходит длины диаметра, \(I_{B} X + X I_{C} \geqslant I_{B} I_{C} \geqslant \geqslant I_{B} Y = I_{B} X + X Y\), откуда \(X I_{C} > X Y\). Следовательно, \(X I_{B} \cdot X I_{C} \geqslant X I_{B} \cdot X Y = X C \cdot X C_{1} > X C \cdot X B\).

Легко видеть, что если \(b = 1\), то всякий многочлен с коэффициентами от 0 до \(b - 1\) является нулевым.

Пусть \(b > 1\). Представим \(a - b\) в \(b\)-ичной записи : \(a - b = = c_{n} b^{n} + \ldots + c_{1} b + c_{0}\), где \(c_{i} \in\{0,1,2, \ldots, b - 1\}\). Поскольку \(a - b \geqslant b\), в этой записи \(n \geqslant 1\).

Покажем, что \(P(x) = c_{n} x^{n} + \ldots + c_{1} x + c_{0}\) удовлетворяет условию. Действительно, для любого многочлена \(f\) с целыми коэффициентами \(f(a)-f(b)\) делится на \(a - b\). Значит, \(P(a)-P(b)\) делится на \(a - b = P(b)\). Но тогда и \(P(a) = (P(a)-P(b)) + P(b)\) делится на \(P(b)\).

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

Раскрасим клетки таблицы в \( n \) цветов по диагоналям, идущим вправо-вниз: первую диагональ — в первый цвет, вторую — во второй, …, \( n \)-ю диагональ — в \( n \)-й цвет, а следующие диагонали — снова в цвета с первого по \( (n-1) \)-й. Заметим, что после каждой партии номер цвета клетки, в которой находится фишка, увеличивается на 1 по модулю \( n \). Так как всего в турнире было проведено \( n^{2} \) партий, что кратно \( n \), то в конце фишка находится в клетке \( n \)-го цвета, то есть на главной диагонали (далее, говоря «диагональ», мы будем иметь в виду именно эту диагональ). Пусть финальная клетка в маршруте фишки расположена в столбце с номером \( m \), тогда требуется доказать, что число \( m \) нечётно.

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

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

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

Пусть число \( m \) при делении на \( k \) даёт остаток \( d \). Тогда первый переход с левых клеток на правые был с числа 0 на число \( k-d \), и в этот момент все клетки с нулём в левой части были посещены. На диагонали остались только числа от 1 до \( k-1 \). Дальше цепочка переходов между правыми и левыми клетками выглядит так: \( k-d \rightarrow \cdots \rightarrow d \). В этой цепочке каждое число от 1 до \( k-1 \) встречается два раза, начинается она на правых клетках, а заканчивается на левых. Переходы с правых клеток на левые будем называть переходами первого типа, а с левых на правые — второго. Тогда в цепочке \( k-1 \) переход первого типа и \( k-2 \) перехода второго, и они чередуются.

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

Предположим, что число \( m \) чётно, и рассмотрим два случая.

1) Число \( k \) нечётно. Тогда центральный переход в цепочке имеет второй тип. У правой нижней клетки диагонали нечётный номер, поскольку число \( n-m \) нечётно, а \( k-1 \) чётно. Левая верхняя клетка диагонали тоже имеет нечётный номер, поэтому при переходе первого типа чётность числа меняется. Пусть с числа 1 переход первого типа происходит на число \( 2s \). Тогда по модулю \( k-1 \) переходы первого типа выглядят так: \( 1 \rightarrow 2s, 2 \rightarrow 2s+1, \ldots, k-1 \rightarrow 2s+k-2 \). Суммы чисел в этих парах являются последовательными нечётными числами, поэтому при делении на \( k-1 \) они дают все нечётные остатки по два раза. В частности, есть переход, в котором сумма чисел равна 1 по модулю \( k-1 \). Как показано выше, эта сумма равна \( k \). Но тогда для этого перехода симметричный ему тоже имеет первый тип и содержит те же самые числа, то есть один из переходов повторился, чего быть не должно.

2) Число \( k \) чётно. Тогда у центрального перехода в цепочке первый тип. Последняя левая клетка имеет нечётный номер, так как число \( m-1 \) нечётно, а \( k \) чётно. У первой правой клетки тоже нечётный номер, значит, при переходе второго типа чётность числа не меняется. Аналогично первому случаю можно показать, что среди них найдётся переход, пара чисел в котором даёт сумму \( k \), и получаем такое же противоречие.

Замечание. После описания того, в каком порядке фишка обходит клетки диагонали (с левых сдвигается вправо на \( k \) клеток, а с правых — на \( k-1 \)) решение можно завершить по-другому.

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

Этот цикл определяет перестановку \( \sigma \) чисел \( 1,2,\ldots,n \), где \( \sigma(i) \) — это номер клетки, в которую ведёт стрелка из клетки \( i \). Эта перестановка — цикл на \( n \) элементах. Напомним, что перестановка, являющаяся циклом на \( b \) элементах, имеет чётность, отличную от чётности числа \( b \). Поэтому перестановка \( \sigma \) чётна.

С другой стороны, \( \sigma \) получается как композиция (последовательное применение) двух перестановок: \( \tau \), которая отправляет \( x \mapsto x+(k-1) \bmod n \), и \( \theta \), действующей как \( k \mapsto(k+1) \mapsto \mapsto(k+2) \mapsto \ldots \mapsto(m+k-1) \mapsto k \). Перестановка \( \tau \) состоит из нескольких циклов одинаковой длины; поэтому эти циклы нечётной длины, и потому \( \tau \) чётна. Значит, и \( \theta \) чётна, что как раз и означает, что \( m \) нечётно.

Пример. Верхнюю и нижнюю горизонтали разобьём на горизонтальные доминошки-они окажутся в квадратах \(2 \times 2\). Остальной прямоугольник \(98 \times 100\) разобьём на вертикальные доминошки-они не окажутся в квадратах \(2 \times 2\).

Оценка. Рассмотрим квадраты \(A_{1}, A_{3}, \ldots, A_{99}\) размеров \(1 \times 1,3 \times 3, \ldots, 99 \times 99\), у которых левый нижний угол совпадает с левым нижним углом исходного квадрата \(100 \times 100\). Для каждого из квадратов \(A_{i}(i = 1,3,5, \ldots, 99)\) найдётся доминошка \(X_{i}\), пересекающая его сторону (поскольку квадраты нечётной площади не разбиваются на доминошки). Легко видеть, что \(X_{i}\) лежит внутри квадратика \(2 \times 2\) из разбиения.

Аналогично, рассматривая квадраты \(B_{1}, B_{3}, \ldots, B_{99}\) размеров \(1 \times 1,3 \times 3, \ldots 99 \times 99\), у которых правый верхний угол совпадает с правым верхним углом исходного квадрата \(100 \times 100\), находим ещё 50 нужных нам доминошек \(Y_{j}(j = 1,3,5, \ldots, 99)\).

Это завершает решение (очевидно, что все доминошки \(X_{1}\), \(X_{3}, \ldots, X_{99}, Y_{1}, Y_{3}, \ldots, Y_{99}\) различны).

Замечание. Приведём схему несколько другого доказательства оценки.

Пусть внутри квадратов \(2 \times 2\) оказалось не более 99 доминошек.

Проведём 50 вертикальных линий сетки \(v_{1}, v_{3}, v_{5}, \ldots, v_{99}\) так, что \(v_{i}\) отделяет \(i\) столбцов слева. Легко видеть, что любая доминошка, пересекаемая одной из линий \(v_{1}, v_{3}, v_{5}, \ldots, v_{99}\), нам подходит. Каждая вертикальная линия пересекает чётное количество доминошек, так как слева от этой линии чётное количество клеток. Значит, среди линий \(v_{1}, v_{3}, v_{5}, \ldots, v_{99}\) есть линия \(v_{i}\), не пересекающая доминошек, иначе мы уже нашли хотя бы \(2 \cdot 50 = 100\) нужных нам доминошек. Проведём аналогичное рассуждение для 50 горизонтальных линий сетки \(h_{1}, h_{3}, h_{5}, \ldots, h_{99}\) и найдём среди них линию \(h_{j}\), не пересекающую доминошек. Но \(v_{i}\) и \(h_{j}\) делят доску на области с нечётным количеством клеток, поэтому хотя бы одна из этих двух линий обязана пересекать доминошку. Противоречие.

Сопоставим строке \(x_{1}, x_{2}, \ldots, x_{100}\) чисел от 1 до 100 последовательность из 99 знаков \(<\) и \(>\) в соответствии с тем, как упорядочены соседние числа. То есть если \(x_{k} < x_{k + 1}\), то \(k\)-й знак в этой последовательности равен \(<\), в противном случае он равен \(>\). Заметим, что разрешённые операции над строкой не меняют соответствующую ей последовательность знаков. Действительно, из пары чисел \(x_{k}\) и \(x_{k + 1}\) меняется не более одного и не более чем на 1. Поэтому знак неравенства между ними не может измениться на противоположный. Сопоставим каждой перестановке знаков расстановку чисел по следующему правилу (далее такие расстановки будем называть выделенными). При \(k = 1,2, \ldots, 99\) если \(x_{k} > x_{k + 1}\) (т.е. \(k\)-й знак \(<\) ) поставим на место \(x_{k}\) наибольшее из не выбранных ранее чисел, если же \(x_{k} < x_{k + 1}\) - наименьшее из не выбранных ранее чисел. Заметим, что при такой последовательности операций числа, не выбранные за первые \(k\) шагов, будут образовывать отрезок натурального ряда (а выбранными окажутся несколько наибольших и несколько наименьших чисел от 1 до 100 ). В частности, \(x_{1} = 1\) или \(x_{1} = 100\). Число \(x_{100}\) заменим на единственное оставшееся число.

Нетрудно видеть, что полученная расстановка чисел соответствует выбранной последовательности знаков. Всего выделенных расстановок будет столько же, сколько и различных последовательностей знаков, то есть \(2^{99}\). В силу сказанного выше, разрешёнными операциями никакие две из выделенных строк разрешёнными операциями нельзя сделать одинаковыми. Таким образом, заполнив таблицу \(100 \times 2^{99}\) выделенными строками, мы получаем пример для \(n = 2^{99}\).

Теперь докажем, что из любой строки \(A\) длины 100 можно получить выделенную строку \(B\) с той же расстановкой знаков. Из этого последует, что \(n \leqslant 2^{99}\). Предположим, что первые \(t - 1\) знаков данной строки \(A = \left(x_{1}, \ldots, x_{100}\right)\) и выделенной строки \(B = \left(y_{1}, \ldots, y_{100}\right)\) совпадают. Если \(t = 100\), то и сами строки совпадают. Пусть \(t < 100\). Без ограничения общности будем

считать, что \(x_{t} < x_{t + 1}\). В силу сказанного выше наборы чисел \(y_{t}, \ldots, y_{100}\) и \(x_{t}, \ldots, x_{100}\) совпадают и образуют отрезок натурального ряда с наименьшим числом \(x_{t}\). Поскольку \(y_{t} < y_{t + 1}\), можно менять в строке \(A\) на месте \(t\) с числом на единицу меньшим, пока на месте \(t\) не окажется число \(x_{t}\). Таким образом, мы добились совпадения первых \(t\) символов у нашей строки с выделенной строкой \(B\). Значит, такими операциями можно из любой строки получить выделенную строку, что завершает доказательство оценки.

Обозначим точки пересечения прямой \(M H\) с прямыми \(A B, A C, B I\) и \(C I\) через \(P, Q, X\) и \(Y\) соответственно (см. рис. 6). Пусть прямые \(A I, B I\) и \(C I\) повторно пересекают \(\omega\) в точках \(A_{1}, B_{1}\) и \(C_{1}\) соответственно. Обозначим \(\angle B A I = = \angle C A I = \alpha, \angle A B I = \angle C B I = \beta, \angle A C I = \angle B C I = \gamma\), тогда \(\alpha + \beta + \gamma = 90^{\circ}\) из суммы углов треугольника \(A B C\). Поскольку \(M H \perp A I\), имеем \(\angle A Q M = 90^{\circ}-\alpha\). Так как четырёхугольник

\(A B A_{1} C\) - вписанный, \(\angle M A_{1} C = 90^{\circ}-\angle B C A_{1} = 90^{\circ}-\alpha\). Таким образом, \(\angle M A_{1} C + \angle M Q C = 180^{\circ}\), поэтому четырёхугольник \(A_{1} C Q M\) - вписанный. Следовательно, \(\angle A Q A_{1} = 90^{\circ}\). Аналогично \(\angle A P A_{1} = 90^{\circ}\), откуда следует, что точки \(A, A_{1}, P, Q\) лежат на окружности \(\gamma\), построенной на отрезке \(A A_{1}\) как на диаметре.

Теперь заметим, что \(\angle Q C^{\prime} C = \angle Q Y C = 90^{\circ}-\angle C I A_{1} = = 90^{\circ}-\alpha-\gamma = \beta\). Однако из вписанности четырехугольника \(B C^{\prime} C B_{1}\) мы получаем, что \(\angle C C^{\prime} B_{1} = \angle B_{1} B C = \beta = \angle C C^{\prime} Q\). Следовательно, точки \(C^{\prime}, Q\) и \(B_{1}\) лежат на одной прямой. Аналогично, точки \(P, B^{\prime}\) и \(C_{1}\) лежат на одной прямой.

Рис. 6

В силу сказанного выше и вписанности четырёхугольника \(C_{1} B_{1} C B\) имеем, что \(\angle C C_{1} B_{1} = \beta = \angle C Y Q\), поэтому \(C_{1} B_{1} \| P Q\). Поскольку четырёхугольник \(B^{\prime} C_{1} B_{1} C^{\prime}\) вписанный, \(\angle P B^{\prime} C^{\prime} = \angle C_{1} B_{1} C^{\prime} = \angle P Q C^{\prime}\). Значит, четырехугольник \(B^{\prime} Q C^{\prime} P\) - вписанный. Тогда радикальные оси его описанной окружности, окружности \(\gamma\) и окружности \(\omega\) пересекаются в одной точке, а это прямые \(B^{\prime} C^{\prime}, P Q\) и \(A A_{1}\). Следовательно, точка \(H\) лежит на прямой \(B^{\prime} C^{\prime}\), что и требовалось доказать.

Замечание. Приведём другой способ закончить решение после того, как установлено, что точки \(C^{\prime}, Q\) и \(B_{1}\) лежат на одной прямой, и точки \(P, B^{\prime}\) и \(C_{1}\) лежат на одной прямой. Обозначим через \(N\) середину дуги \(B A C\). Пусть прямая \(A X\) повторно пересекает окружность \(\omega\) в точке \(T\). Заметим, что \(\angle C C^{\prime} Y = \angle A Q Y = 90^{\circ}-\alpha = \frac{1}{2} \angle C C^{\prime} B\). Следовательно, \(C^{\prime} Y-\) биссектриса угла \(C C^{\prime} B\), поэтому на прямой \(C^{\prime} Y\) лежит точка \(N\). Аналогично, она лежит на прямой \(X B^{\prime}\). Применяя теорему Паскаля для точек \(A T C^{\prime} B_{1} B C\) мы получаем, что точка \(X\), точка \(Q\) и точка пересечения \(C^{\prime} T\) и \(B C\) лежат на одной прямой. Следовательно, прямые \(B C, X Q\) и \(C^{\prime} T\) пересекаются в одной точке, то есть точка \(M\) лежит на \(C^{\prime} T\). Теперь применяем теорему Паскаля для точек \(A T C^{\prime} B^{\prime} N A_{1}\) и получаем, что точки \(X\) и \(M\) вместе с точкой пересечения \(A A_{1}\) и \(B^{\prime} C^{\prime}\) лежат на одной прямой. Значит, точка \(H\) лежит на \(B^{\prime} C^{\prime}\), что и требовалось.

Многочлен \(P(x)\) называется целозначным, если \(P(k)\) - целое число при любом целом \(k\). Нам надо доказать, что,

если многочлены \(P(x)\) и \(P^{\prime}(x)\) целозначны, причём степень \(P(x)\) равна \(d\), то старший коэффициент многочлена \(N_{d} \cdot P(x)\) - целый.

Лемма. Пусть \(P(x)\) - целозначный многочлен степени \(d\). Тогда все коэффициенты многочлена \(d!\cdot P(x)\) цельие.

Доказательство. Рассмотрим многочлен

\(Q(x) = \sum_{i = 0}^{n} P(i) \cdot \frac{(x - 0)(x - 1) \ldots(x-(i - 1))(x-(i + 1)) \ldots(x - d)}{(i - 0)(i - 1) \ldots(i-(i - 1))(i-(i + 1)) \ldots(i - d)}\)

Его степень не больше \(d\), и его значения совпадают с соответствующими значениями \(P(x)\) в точках \(x = 0,1,2, \ldots, d\). Это означает, что многочлен \(P(x)-Q(x)\) имеет степень не выше \(d\), а также обнуляется в \(d + 1\) точке. Поэтому он нулевой, то есть \(P(x) = Q(x)\). (Формула выше-это частный случай интерполяционной формуль Лагранжа.)

Осталось заметить, что в формуле выше в \(i\)-м слагаемом знаменатель равен \((-1)^{d - i} i!(d - i)!;\) это число делит \(d!\), поскольку \(\frac{d!}{i!(d - i)!} = C_{d}^{i}\). Значит, при умножении каждого слагаемого на \(d!\) получается многочлен с целыми коэффициентами.

Перейдём к решению задачи. Индукция по \(d\). База при \(d = 0\) тривиальна. Для перехода индукции рассмотрим бицелозначный многочлен \(P(x)\) степени \(d\); пусть его старший коэффициент равен \(a\).

Если \(d\) не является простым числом, то \(N_{d} = d N_{d - 1}\). Заметим, что многочлен \(\Delta P(x) = P(x + 1)-P(x)\) также бицелозначный, имеет степень \(d - 1\) и старший коэффициент \(a d\). По предположению индукции, число \(N_{d - 1} \cdot a d = N_{d} a\) является целым, что и требовалось доказать.

Пусть теперь \(d\) - простое число; тогда \(N_{d} = N_{d - 1}\), и то же рассуждение даёт, что число \(d N_{d} a\) является целым. Предположим, что \(N_{d} a\) - нецелое число; тогда знаменатель числа \(a\) (в несократимой записи) делится на простое число \(d\).

Заметим, что сумма всех коэффициентов многочлена \(P(x)\) - это целое число \(P(1)\). Поскольку знаменатель числа \(a\) делится на \(d\), среди коэффициентов многочлена \(P(x)\) найдётся ещё один, у которого знаменатель делится на \(d\); пусть это коэффициент \(b\) при \(x^{i}, i < d\). Заметим, что \(i > 0\), так как число \(P(0)\) целое.

Но тогда у целозначного многочлена \(P^{\prime}(x)\) коэффициент при \(x^{i - 1}\) равен \(i b\) и также имеет знаменатель, кратный \(d\). Поскольку \(d\) - простое число, отсюда вытекает, что коэффициент при \(x^{i - 1}\) у многочлена \((d - 1)!P^{\prime}(x)\) нецелый, что противоречит лемме.

Замечание 1. Случай простого \(d\) можно разобрать и другими способами. Приведём один из них.

Предположим, что число \(d N_{d} a\) целое, а \(N_{d} a\) - нет, так что \(N_{d} a = t / d\) для некоторого целого \(t\), не кратного \(d\). Рассмотрим многочлен

\(Q(x) = N_{d} P(x)-N_{d} a \cdot(x - 1)(x - 2) \ldots(x - d) .\)

Он целозначен, поскольку при любом целом \(k\) число \((k - 1)(k- -2) \ldots(k - d)\) делится на \(d!\). Кроме того, его степень меньше \(d\). Из леммы вытекает, что знаменатели коэффициентов многочлена \(Q(x)\) не делятся на \(d\).

Рассмотрим теперь целое число \(c = N_{d} P^{\prime}(d)\). Из формулы ( * ) нетрудно получить, что

\(c = Q^{\prime}(d) + \frac{t}{d} \cdot(d - 1)(d - 2) \ldots(d-(d - 1)) .\)

При этом первое слагаемое-это несократимая дробь со знаменателем, не делящимся на \(d\), а второе-с делящимся. Это невозможно для целого \(c\).

Замечание 2. Как доказали D. Brizolis и E. G. Straus, наименьшее \(N\), для которого старший коэффициент многочлена \(N P(x)\) обязательно целый, равно \(d!\prod_{p} p^{-k(p, d)}\), где произведение берётся по всем простым \(p\), а \(k(p, d)\) - это наибольшее целое неотрицательное число \(k\), для которого верно неравенство \(k p^{k}-(k - 1) p^{k - 1} \leqslant d\).

Если удалить полностью 51 кучку, то, очевидно, не останется много камней. Значит, искомое значение \(n\) меньше 5100. (Альтернативно, можно удалить из всех кучек по 51 камню.)

Осталось показать, что при удалении любых \(n = 5099\) камней останется много камней. Пусть в кучках осталось \(a_{1}, a_{2}, \ldots\), \(a_{100}\) камней соответственно; можно считать, что \(0 \leqslant a_{1} \leqslant a_{2} \leqslant \leqslant \ldots \leqslant a_{100} \leqslant 100\). Покажем, что \(a_{i + 50} \geqslant i\) при \(i = 1,2, \ldots, 50\), то есть кучки с номерами от 51 до 100 удовлетворяют требованиям.

Пусть это не так, то есть \(a_{i + 50} \leqslant i - 1\). при некотором \(i \leqslant 50\). Это значит, что каждая из первых \(i + 50\) кучек содержит не более \(i - 1\) камня, то есть из неё удалено хотя бы \(101-i\) камней. Поэтому общее количество удалённых камней не меньше, чем \((i + 50)(101-i) = 5100-(i - 1)(i - 50) \geqslant 5100\). Противоречие.

Каждому остатку \(a\) от деления на 19 сопоставим остаток \(b(a)\) такой, что \(b(a) \equiv 3 a(\bmod 19)\). Заметим, что остаткам \(0,1,2,3,7,8,9\) сопоставлены остатки \(0,3,6,9,2,5,8\) соответственно. Более того, по остатку \(b\) восстанавливается остаток \(a = a(b) \equiv - 6 b(\bmod 19)\) такой, что \(a(b(a)) \equiv - 18 a \equiv a (\bmod 19)\) и \(b(a(b)) = b\) (из аналогичных соображений).

Обозначим теперь через \(\mathcal{A}\) множество чисел из условия, не содержащих цифр \(4,5,6\), а через \(\mathcal{B}\) - множество таких чисел, не содержащих \(1,4,7\). Каждому числу \(A = \overline{a_{99} a_{98} \ldots a_{0}} \in \mathcal{A}\) сопоставим число \(B = \overline{b\left(a_{99}\right) b\left(a_{98}\right) \ldots b\left(a_{0}\right)}\). Заметим, что \(b\left(a_{i}\right)-\) цифра (причём \(b\left(a_{99}\right) \neq 0\) ), так что получилось 100-значное число. Кроме того,

\(\begin{aligned} B = b_{0} + 10 b_{1} + & \ldots + 10^{99} b_{99} \equiv \\ & \equiv 3\left(a_{0} + 10 a_{1} + \ldots + 10^{99} a_{99}\right) = 3 A \quad(\bmod 19) \end{aligned}\)

так что \(B\) делится на 19 и \(B \in \mathcal{B}\). Поскольку разным числам из \(\mathcal{A}\) соответствуют разные числа из \(\mathcal{B}\), количество чисел в \(\mathcal{B}\) не меньше, чем в \(\mathcal{A}\).

Наконец, каждому числу \(B = \overline{b_{99} b_{98} \ldots b_{0}} \in \mathcal{B}\) соответствует число \(A = \overline{a\left(b_{99}\right) a\left(b_{98}\right) \ldots a\left(b_{0}\right)}\), которое по аналогичным причинам лежит в \(\mathcal{A}\). Отсюда следует, что количества чисел в \(\mathcal{A}\) и \(\mathcal{B}\) равны.

Покажем, что Петя сможет определить вес одной гири, даже если у него 8000 гирь. Положим \(n = 4000\).

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

Доказательство. Пусть Петя положит в прибор по очереди все возможные наборы из 10 гирь из наших \(n\). Заметим, что каждое показание прибора-это вес какой-то из \(C_{n}^{2}\) пар гирь (будем говорить, что это показание использует эту пару). В то же время, Петя получит \(C_{n}^{10}\) показаний. Значит, одна из пар будет использована хотя бы

\(D = \frac{C_{n}^{10}}{C_{n}^{2}} = \frac{(n - 2)(n - 3) \ldots(n - 9)}{3 \cdot 4 \cdot \ldots \cdot 10}\)

раз.

Иначе говоря, найдутся \(D\) измерений таких, что (1) в них прибор показывает один и тот же вес \(S\), и (2) во всех десятках, использованных в этих испытаниях, есть две общих гири \(a\) и \(b\). Мы покажем, что при выполнении условий (1) и (2) суммарный вес \(a\) и \(b\) обязательно равен \(S\), то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовём десятки гирь, участвовавшие в этих \(D\) измерениях, нужными.

Предположим противное : сумма весов \(a\) и \(b\) не равна \(S\). Рассмотрим все пары из \(n\) гирь, суммарные веса в которых равны \(S\) (назовём эти пары хорошими). Поскольку веса всех гирь различны, хорошие пары не пересекаются; в частности, их не больше, чем \(n / 2\). При этом в каждой нужной десятке есть не только гири \(a\) и \(b\), но и хотя бы одна хорошая пара. Оценим теперь общее количество нужных десяток.

Пусть в нужной десятке хорошая пара не содержит ни \(a\), ни \(b\). Любую такую десятку можно получить, добавив к гирям \(a\) и \(b\) хорошую пару (не более чем \((n - 2) / 2\) способами), а затем

дополнив шестью из оставшихся \(n - 4\) гирь. Итого, количество таких десяток не больше, чем \(\frac{n - 2}{2} C_{n - 4}^{6}\).

Во всех остальных нужных десятках хорошая пара содержит либо \(a\), либо \(b\). Если есть хорошая пара, содержащая \(a\), то такая пара единственна. Для получения нужной десятки, содержащей эту пару, её надо дополнить гирей \(b\) и ещё семью гирями из оставшихся \(n - 3\); итого, таких нужных десяток не больше \(C_{n - 3}^{7}\). Аналогично, нужных десяток, содержащих хорошую пару с гирей \(b\), тоже не больше \(C_{n - 3}^{7}\).

Итого, получаем

\(\begin{aligned} D \leqslant \frac{n - 2}{2} & C_{n - 4}^{6} + 2 C_{n - 3}^{7} = \\ & \quad = D \cdot\left(\frac{7 \cdot 8 \cdot 9 \cdot 10}{4(n - 3)} + \frac{8 \cdot 9 \cdot 10}{n - 2}\right) < D \cdot\left(\frac{1}{2} + \frac{1}{2}\right) = D \end{aligned}\)

Противоречие.

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

Значит, в полученном графе есть цикл \(w_{1}, w_{2}, \ldots, w_{2 k + 1}\), и Петя знает суммарные веса всех пар соседних гирь в этом цикле. Взяв полусумму всех этих весов, Петя узнаёт суммарный вес всех гирь цикла. Вычтя из него \(\left(w_{2} + w_{3}\right) + \left(w_{4} + w_{5}\right) + \ldots + + \left(w_{2 k} + w_{2 k + 1}\right)\), он узнает вес гири \(w_{1}\).

Замечание. Оценивая чуть точнее, можно доказать лемму даже при \(n = 2000\).

Пусть прямая \(E C\) повторно пересекает окружность \((A B C)\) в точке \(X\), а прямая \(E A\) повторно пересекает

окружность ( \(A C D\) ) в точке \(Y\) (мы разберём расположение точек, указанное на рис. 5; другие случаи рассматриваются аналогично).

Рассмотрим гомотетию с центром \(E\), переводящую ( \(A B C\) ) в \((A C D)\). При такой гомотетии точка \(X\) переходит в \(C\), а точка \(A\)-в \(Y\). Отсюда \(A X \| Y C\) и \(\angle A E C = \angle A Y C-\angle E C Y = = \angle A Y C-\angle A X C\).

Рис. 5

Но \(\angle A X C = 180^{\circ}-\angle A B C\) и \(\angle A Y C = 180^{\circ}-\angle A D C\). Значит, \(\angle A E C = \angle A B C-\angle A D C = \angle A B C-\angle B C G = \angle B G C\). Из полученного равенства следует, что точки \(A, C, E, G\) лежат на одной окружности.

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

Аналогично показывается, что \(F\) также лежит на внешней биссектрисе угла \(B G C\).

Замечание. У задачи есть следующее обобщение. Пусть \(A B C D\) - четырёхугольник, \(G = A B \cap C D\), а \(M\) - вторая точка пересечения окружностей ( \(A D G\) ) и ( \(B C G\) ) (иначе говоря, точка

Микеля этого четырёхугольника). Пусть \(E\) - центр гомотетии с положительным коэффициентом, переводящей ( \(A B C\) ) в ( \(A D C\) ). Тогда точки \(A, C, M, E\) лежат на одной окружности, причём \(E\) - середина дуги \(A C\) (т. е. \(M E\) - биссектриса угла между \(A M\) и \(C M\) ).

Доказать это можно аналогично решению решении задачи : имеем (в направленных углах) \(\angle A E C = \angle A B C + \angle A D C = = \angle G B C + \angle A M G = \angle G M C + \angle A M G = \angle A M C\).

Заметим, что равенство достигается при \(x_{0} = a\) и \(x_{1} = \ldots = x_{n} = 1\).

Запишем \(\sum x_{k}^{2} = \sum\left(1-x_{k}\right)^{2} + 2 \sum x_{k}-(n + 1) = \sum\left(1-x_{k}\right)^{2} +\)

\(+ n - 1 + 2 a\). Достаточно доказать, что \(\sum\left(1-x_{k}\right)^{2} \geqslant(1-a)^{2}\). Пусть \(x_{0}\) - наименьшее из чисел.

При \(x_{0} \leqslant a\) имеем \(\sum\left(1-x_{k}\right)^{2} \geqslant\left(1-x_{0}\right)^{2} \geqslant(1-a)^{2}\).

Если же \(x_{0} \geqslant a\), то \(\sum\left(1-x_{k}\right)^{2} = \sum x_{k}\left(\frac{1}{x_{k}}-2 + x_{k}\right)\), что, поскольку выражения в скобках неотрицательны, не меньше, чем \(a \sum\left(\frac{1}{x_{k}}-2 + x_{k}\right) = a\left(n + \frac{1}{a}-2(n + 1) + n + a\right) = = a\left(\frac{1}{a}-2 + a\right) = (a - 1)^{2}\).

Заметим, что \(2023 = 7 \cdot 17^{2}\). Гриша разобьёт числа на доске на две группы по 5 и будет возводить в квадрат числа из первой группы и из второй группы по очереди. Легко видеть, что квадраты целых чисел, не кратных 7 , при делении на 7 могут давать лишь остатки 1,2 и 4 . Следовательно, после увеличения максимум на 2 числа на доске будут давать при делении на 7 только остатки \(1,2,3,4,5\) и 6 . Значит, ни одно из чисел не будет делиться 7 , а поэтому не будет делиться и на 2023.

Замечание. Существуют и другие решения.

Рассматриваемые сети из \(N - k\) дорог называем далее \(k\)-сетями. Рассмотрим неориентированный граф, образованный дорогами \(k\)-сети. В нём не более чем \(k\) компонент связности, поскольку в каждой есть выделенный город. С другой стороны, компонент не менее \(k\), поскольку рёбер всего не более чем \(N - k\). Поэтому компонент ровно \(k\), каждая из них есть дерево, содержит единственный выделенный город и-вспоминая про ориентацию-рёбра каждого дерева направлены по направлению к выделенному городу. В частности, из каждого не выделенного города должна выходить ровно одна дорога, а из выделенного 0 дорог.

Рассмотрим \((k + 1)\)-оптимальную сеть \(A\) с выделенными городами \(y_{0}, y_{1}, \ldots, y_{k}\) и \(k\)-оптимальную сеть \(B\) с выделенными городами \(x_{1}, \ldots, x_{k}\). Не умаляя общности, ни из одного \(x_{i}\) нельзя добраться в сети \(A\) до города \(y_{0}\). Пусть \(U\) - множество городов, из которых в \(A\) можно добраться до \(y_{0}\), а \(\alpha, \beta\) - множества дорог, выходящих из \(U\) в сетях \(A, B\) соответственно. Имеем \(|\alpha| = |U|-1,|\beta| = |U|\).

Рассмотрим сеть \(D : = (A \backslash \alpha) \cup \beta\). Утверждается, что это \(k\)-сеть для выделенных городов \(y_{1}, \ldots, y_{k}\). В самом деле, число дорог в ней равно \(|D| = N - k - 1-(|U|-1) + |U| = N - k\). Из каждого города, кроме \(y_{1}, \ldots, y_{k}\) выходит ровно одна дорога. Выезжая из любого города вне \(U\) и используя дороги сети, мы по-прежнему можем попасть в один из городов \(y_{1}, \ldots, y_{k}\). Выезжая из города в \(U\), мы либо попадаем вне \(U\) - и далее в один из городов \(y_{1}, \ldots, y_{k}\), - либо зацикливаемся в \(U\). Но тогда \(\beta\) содержит цикл, что невозможно.

Рассмотрим сеть \(C : = (B \backslash \beta) \cup \alpha\). Утверждается, что это \((k + 1)\)-сеть для выделенных городов \(x_{1}, \ldots, x_{k}, y_{0}\). В самом деле, \(|C| = n - k - 1\), и выезжая из любого города по дорогам сети \(C\), мы либо попадаем в \(U\) - и тогда по \(\alpha\) доезжаем до \(y_{0}\), - либо ни разу не попадаем в \(U\) и тогда доезжаем до одного из городов \(x_{1}, \ldots, x_{k}\).

Итак, \(C, D - k\)-сеть и \((k + 1)\)-сеть. Сумма их стоимостей такая же, как у \(A\) и \(B\). Значит, они обе оптимальны. Таким образом, для сети \(A\) удалось выкинуть выделенный город и найти оптимальную \(k\)-сеть с оставшимися выделенными городами. Теперь можно построить требуемую нумерацию в обратном порядке (начиная с пустой \(N\)-сети).