Если число \(k=abc+ab+ac+bc\)\(\le 10^9-4000\) хорошее для Пети, то число

\(k-2=(a+1)(b+1)(c+1)\)\(- (a+1)-(b+1)-(c+1)\)

является хорошим для Васи, так как \(a+1,\;b+1,\;c+1\gt 100\). Значит, если для Пети есть \(p\) хороших чисел, то мы предъявили \(p\) различных чисел, хороших для Васи, и все они строго меньше, чем \(10^9-4000\).

Кроме того, число \(10^9-4000=(1000-1)\cdot 1000\cdot(1000+1)\)\(- (1000-1)-1000-(1000+1)\) также является хорошим для Васи. Следовательно, для Васи есть как минимум \(p+1\) хорошее число.

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

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

Если \(n\) нечётно, то все его делители нечётны. Всего существует \(50\) нечётных хвостов; из них \(10\) оканчиваются на \(5\) и потому невозможны. Остаётся \(40\) вариантов на \(50\) делителей, значит два хвоста совпадут — противоречие.

Пусть \(n\) делится на \(2\), но не на \(4\). Тогда все делители разбиваются на пары \((d,\,2d)\), где \(d\) — нечётный делитель \(n\). При этом хвост всякого числа вида \(2d\) даёт остаток \(2\) по модулю \(4\), а среди хвостов, не кратных \(5\), таких всего \(20\) вариантов. Таких делителей \(2d\) не меньше \(25\), значит два хвоста совпадут — противоречие.

Наконец, пусть максимальная степень двойки, на которую делится \(n\), равна \(2^r\) при \(r\ge 2\). Тогда для любого нечётного делителя \(d\) числа \(n\) числа \(d,\,2d,\,2^2 d,\,\dots,\,2^r d\) тоже являются делителями \(n\), и этим исчерпываются все делители \(n\). Следовательно, общее число делителей кратно \(r+1\). Так как \(50\) делится на \(r+1\), получаем \(r+1\in\{5,10,25,50\}\)\(\Rightarrow r\ge 4\).

Тогда у \(n\) не более \(\frac{50}{r+1}\le 10\) нечётных делителей и столько же делителей, которые чётны, но не делятся на \(4\). Оставшиеся делители (их не меньше \(30\)) кратны \(4\); их хвосты также кратны \(4\). Но хвостов, кратных \(4\) и не кратных \(5\), всего \(20\), значит снова два совпадут — противоречие.

Во всех случаях получаем противоречие. Следовательно, такого числа \(n\) не существует.

Решение. Пусть в процессе было \(N\) ходов. Посмотрим на процесс «в обратную сторону». Назовём последний сделанный ход первым, предпоследний (сделанный другим мальчиком) — вторым, и т.д. Обозначим через \(a_0\) количество клубней в мешке, из которого их перекладывали на первом ходе, после этого хода (то есть в самом конце процесса). Аналогично, обозначим через \(a_{i-1}\) количество клубней в мешке, из которого перекладывали на \(i\)-м ходе, непосредственно после этого хода. Наконец, обозначим через \(a_N\) количество клубней в мешке, в который перекладывали на \(N\)-м (самом раннем) ходе, перед этим ходом (тогда \(a_N=150\)).

Пусть \(k\le N-3\). Рассмотрим мешок, в котором лежало \(a_k\) клубней после \((k+1)\)-го хода (из него только что переложили картошку). Тогда перед \((k+1)\)-м ходом в нём было \(300-a_{k+1}\) клубней, перед \((k+2)\)-м ходом — \(a_{k+2}\) клубней, а перед \((k+3)\)-м ходом — \(300-a_{k+3}\) клубней. На \((k+1)\)-м ходе из этого мешка переложили \((300-a_{k+1})-a_k\) клубней, и это количество должно быть больше, чем количество клубней в нём перед \((k+3)\)-м ходом. Итак, \(300-a_{k+3}<300-a_k-a_{k+1}\)\(\Rightarrow a_{k+3}>a_k+a_{k+1}\); поскольку все числа целые, имеем \(a_{k+3}\ge a_k+a_{k+1}+1\).

Определим числа \(b_0,b_1,b_2,\dots\) так: \(b_0=b_1=b_2=0,\ \ b_{k+3}=b_{k+1}+b_k+1\). Тогда, поскольку \(a_0,a_1,a_2\ge 0\), из полученного неравенства непосредственной индукцией следует, что \(a_k\ge b_k\) и \(b_{k+1}\ge b_k\) при всех \(k=0,1,\dots\). Значит, \(b_N\le a_N=150\).

\(k:\;\;0\;1\;2\;3\;4\;5\;6\;7\;8\;9\;10\;11\;12\;13\;14\;15\;16\;17\;18\;19\;20\)

\(b_k:\;0\;0\;0\;1\;1\;2\;3\;4\;6\;8\;11\;15\;20\;27\;36\;48\;64\;85\;113\;150\;199\).

Из условия \(b_N\le 150\) получаем \(N\le 19\).

Пример, когда дети могут сделать 19 ходов, следует из построения выше. Изначально у каждого ребёнка по \(b_{19}=150\) клубней. Если дети будут действовать так, чтобы после \(k\)-го (с начала) хода у перекладывавшего оставалось ровно \(b_{19-k}\) клубней, то на \(k\)-м (с начала) ходе ребёнок будет перекладывать \(300-b_{20-k}-b_{19-k}\) клубней, а перед любым предыдущим его ходом у него будет \(300-b_i\) клубней при \(i\ge 17-k\), причём \(300-b_i\le 300-b_{17-k}<300-b_{19-k}-b_{20-k}\). Значит, этот ход удовлетворяет условию, и дети могут сделать 19 таких ходов.

Вычеркнем все нецелые числа из прогрессии (если они есть). Ясно, что после вычёркивания остаётся бесконечная убывающая арифметическая прогрессия, состоящая из целых чисел. Пусть её разность равна \( - d \).

Заметим, что \( q^{23} - p^{23} \) делится на \( d \), значит, \( d \) не делится на \( p \), иначе \( q^{23} \) должно будет делиться на \( p \), что неверно. С другой стороны, \( d \) должно являться делителем числа \( p^{24} - p^{23} = p^{23}(p - \) - 1 ). Поскольку \( p \) и \( d \) взаимно просты, \( p - 1 \) делится на \( d \). Далее, \( p^{23} - p \) делится на \( p - 1 \) (поскольку оно равно \( p(p - 1)\left(p^{21} + p^{20} + \right. + \ldots + 1) \) ). Поэтому \( p^{23} - p \) делится на \( d \), и, поскольку \( p < < p^{23} \), получаем, что \( p \) лежит в нашей прогрессии. Аналогично, \( q \) лежит в этой прогрессии.

Оценка. Разобьём квадрат \( 2 n \times 2 n \) на \( n^{2} \) квадратиков \( 2 \times 2 \).

Среди этих квадратиков не более \( 2(n - 1)^{2} / 2 = (n - 1)^{2} \) квадратиков, в которых покрашено хотя бы 2 клетки. Остальных квадратиков \( 2 \times 2 \) - не менее \( n^{2} - (n - 1)^{2} = 2 n - 1 \) штук. Из каждого из них можно вырезать трёхклеточный уголок.

Пример. Построим пример индукци -

Для перехода выделим в квадрате внешнюю «рамку» шириной в две клетки. В этой рамке закрасим все \( 8(n - 2) \) клетки, примыкающие к внутренней границе рамки (см.рис)

Осталось понять, сколько уголков можно вырезать в этом примере. Любой уголок из непокрашенных клеток целиком лежит либо в рамке, либо во внутреннем квадрате (таких по предположению \( 2(n - 2) - 1 = 2 n - 5) \). Из рамки же нельзя вырезать более 4 уголков - каждый такой уголок должен содержать хотя бы 2 клетки одного из угловых квадратов \( 2 \times 2 \), а двух уголков, пересекающихся с одним квадратом, вырезать нельзя. Значит, общее количество уголков не больше \( (2 n - 5) + 4 = 2 n - 1 \).

Предположим, что такая конструкция существует. Спроецируем тетраэдр на плоскость \(\alpha\), перпендикулярную прямой \(\ell\). Проекцией цилиндра будет некоторая окружность \(\omega\). Обозначим проекции вершин тетраэдра через \(A, B, C, D\), они все будут различны (в противном случае одна из прямых, содержащих стороны тетраэдра, будет параллельна \(\ell\), такая прямая не может иметь с цилиндром ровно одну общую точку). Каждая из прямых, соединяющих точки \(A, B, C, D\) должна иметь с окружностью \(\omega\) одну общую точку, то есть касаться этой окружности. При этом точки \(A, B, C, D\) не могут лежать на одной прямой (поскольку вершины тетраэдра не лежат в одной плоскости). Значит, либо на одной прямой лежат какие-то три из них, не умаляя общности \(B, C, D\), либо никакие три из этих точек на одной прямой не лежат. В любом случае прямые \(A B, A C, A D\) попарно различны, однако они все касаются окружности \(\omega\) и проходят через точку \(A\), противоречие.

Покажем, что тройка ( \(a, b, c\) ) - загадочная в том и только в том случае, когда \(a b c = 1\), из этого немедленно последует требуемое в задаче. Предположим, что \(a b c < 1\). Тогда \(\sqrt{a^{2} + \frac{1}{a^{2} c^{2}} + 2 a b} > \sqrt{a^{2} + b^{2} + 2 a b} = a + b\), аналогично

\(\sqrt{b^{2} + \frac{1}{b^{2} a^{2}} + 2 b c} > b + c\) и \(\sqrt{c^{2} + \frac{1}{c^{2} b^{2}} + 2 c a} > c + a\). Итого, в этом случае левая часть равенства из условия больше правой. Рассуждая аналогично, в случае \(a b c > 1\) имеем, что правая часть больше левой, а в случае \(a b c = 1\) достигается равенство, что и требовалось.

Решение. Применяя теорему Менелая к треугольнику \(ETZ\) и секущим \(AXB\) и \(CYD\), получаем \( \frac{AZ}{AE}\cdot\frac{BE}{BT}\cdot\frac{XT}{XZ}=1 \) и \( \frac{CE}{CZ}\cdot\frac{DT}{DE}\cdot\frac{YZ}{YT}=1 \). Из равенств \(AZ=CE\) и \(BE=DT\) следует, что \(AE=CZ\) и \(BT=DE\). Подставляя, получаем \( \frac{XT}{XZ}=\frac{YZ}{YT} \), что означает: точки \(X\) и \(Y\) симметричны относительно середины \(S\) отрезка \(ZT\).

Из условия следует, что лучи \(AD\) и \(BC\) пересекаются в некоторой точке \(F\) под прямым углом. Тогда в прямоугольном треугольнике \(XFY\) медиана \(FS\) равна половине гипотенузы \(XY\).

Обозначим через \(M\) и \(N\) середины \(AD\) и \(BC\) соответственно, а через \(O\) — центр окружности \((ABCD)\). Тогда \(O\) — точка пересечения серединных перпендикуляров к \(AC\) и \(BD\), которые совпадают с серединными перпендикулярами к \(EZ\) и \(ET\) соответственно. Значит, \(O\) — также центр окружности \((ETZ)\), а \(OE\) — её радиус. Поэтому достаточно доказать, что \(OE=FS\). Докажем, что \(OEFS\) — параллелограмм.

Поскольку \(EN\) — медиана в треугольнике \(EBC\), а \(MS\) — отрезок, соединяющий середины противоположных сторон четырёхугольника \(AZTD\), имеем \( \overrightarrow{EN}=\frac{\overrightarrow{EB}+\overrightarrow{EC}}{2}=\frac{\overrightarrow{DT}+\overrightarrow{AZ}}{2}=\overrightarrow{MS} \).

В прямоугольном треугольнике \(FBC\) проекции вектора медианы \( \overrightarrow{NF} \) на прямые \(BF\) и \(CF\) равны \( \overrightarrow{BF}/2 \) и \( \overrightarrow{CF}/2 \) соответственно. Поскольку \(O\) и \(M\) — центры окружностей \((ABCD)\) и \((ADF)\), при проекции на те же прямые первая попадает в середины отрезков \(AB\) и \(CD\), а вторая — в середины \(AF\) и \(DF\). Поэтому проекции вектора \( \overrightarrow{OM}=\overrightarrow{AM}-\overrightarrow{AO}=\overrightarrow{DM}-\overrightarrow{DO} \) на \(BF\) и \(CF\) равны \( (\overrightarrow{AF}-\overrightarrow{AB})/2=\overrightarrow{BF}/2 \) и \( (\overrightarrow{DF}-\overrightarrow{DC})/2=\overrightarrow{CF}/2 \). Отсюда \( \overrightarrow{NF}=\overrightarrow{OM} \).

Итак, \( \overrightarrow{OS}=\overrightarrow{OM}+\overrightarrow{MS} \)\(=\overrightarrow{NF}+\overrightarrow{EN} \)\(=\overrightarrow{EF} \), откуда \(OEFS\) — параллелограмм. Следовательно, \(OE=FS=\frac{XY}{2}\), и длина \(XY\) равна диаметру окружности, описанной около \(\triangle ETZ\).

Покажем, что при \( k = 2 n \) (а тем более при \( k < < 2 n) \) Лёня не сможет однозначно определить определить пару \( P, Q \). Пусть он назвал \( x_{1} < x_{2} < \ldots < x_{2 n} \). Положим \( A = (x - \left. - x_{1}\right)\left(x - x_{2}\right) \ldots\left(x - x_{n}\right), B = \left(x - x_{n + 1}\right)\left(x - x_{n + 2}\right) \ldots\left(x - x_{2 n}\right) \), так что \( A\left(x_{i}\right) = 0 \) для \( i = 1,2, \ldots, n \) и \( B\left(x_{i}\right) = 0 \) для \( i = n + 1, n + 2 \), \( \ldots, 2 n \). Тогда если Илья загадал \( P_{1} = A + 2 B \) и \( Q_{1} = - A - 2 B \), то в \( i \) - м столбце таблицы будут числа \( \pm 2 B\left(x_{i}\right) \) при \( i = 1,2, \ldots \), \( n \) и числа \( \pm A\left(x_{i}\right) \) при \( i = n + 1, n + 2, \ldots, 2 n \). Но та же таблица годится для пары \( P_{2} = A - 2 B \) и \( Q_{2} = - A + 2 B \), её мог загадать Саша.

С другой стороны, покажем, что при \( k = 2 n + 1 \) таблице

Ильи может удовлетворять не более одной пары многочленов \( P, Q \). Предположим противное, и есть две такие пары : \( P_{1}, Q_{1} \) и \( P_{2}, Q_{2} \). Тогда \( P_{2} \) совпадает с \( P_{1} \) или \( Q_{1} \) хотя бы при \( n + 1 \) различных значениях аргумента, пусть, скажем, с \( P_{1} \). Но тогда \( P_{1} \) и \( P_{2} \) - одинаковые многочлены (поскольку их разность - многочлен степени не выше \( n \), имеющий не менее \( n + 1 \) различных корней). Из таблицы тогда получаем, что значения \( Q_{1} \) и \( Q_{2} \) совпадают в \( 2 n + 1 \) точке, а тогда и \( Q_{1} = Q_{2} \).

Обозначим через \( \omega \) окружность ( \( E T Z \) ) и через \( d \) - её диаметр. Поскольку \( B E = D T \), то \( B T = B E + E T = D T + + E T = D E \). Из условия \( \angle A + \angle D = 90^{\circ} \) следует, что лучи \( A B \) и \( D C \) пересекаются в некоторой точке \( F \) под прямым углом (см.

Рассуждая аналогично, мы получаем, что точка \( C^{\prime} \), диаметрально противоположная \( E \) на окружности ( \( C E D \) ), лежит на окружности \( \omega \), а также \( C^{\prime} Y \perp Z T \). Таким образом, \( B^{\prime} C^{\prime} \) - хорда окружности \( \omega \), а \( X \) и \( Y \) - проекции точек \( B^{\prime} \) и \( C^{\prime} \) на прямую \( Z T \), поэтому \( X Y \leqslant B^{\prime} C^{\prime} \leqslant d \), что и требовалось.

Замечание 1. На самом деле \( B^{\prime} C^{\prime} \) - диаметр окружности ( \( E T Z \) ), что нетрудно установить счётом углов, но для решения

этого не требуется. Равенство \( X Y = d \) достигается в том и только в том случае, когда исходный четырёхугольник - вписанный.

Замечание 2. Приведём план другого подхода к задаче. Используем обозначения из приведённого выше решения, а также введём новые : \( x = B F, y = A B, z = C F, t = D C, k = \frac{D E}{E B} \), \( m = \frac{A E}{F C}, p = Z T, \alpha = \angle A E D \). Из теорем Менелая для \( \triangle E Z T \) и прямой \( A Y B ; \triangle E Z T \) и прямой \( C Y D \) находим : \( X Z = Y T = = p \cdot \frac{1}{k l - 1} \). По теореме синусов для треугольника \( Z E T : d = = \frac{p}{\sin \alpha} \), в силу сказанного выше \( X Y = X Z + Y Z + Z T = p \cdot \frac{k l + 1}{k l - 1} \). Таким образом, достаточно доказать, что \( \sin \alpha \leqslant \frac{k l - 1}{k l + 1}(\star) \). Из теорем Менелая для \( \triangle A F C \) и прямой \( B E D ; \triangle B F D \) и прямой \( A E C \) легко видеть, что \( k = \frac{t(x + y)}{z y}, l = \frac{y(z + t)}{x t} \), отсюда \( k l = \frac{(x + y)(z + t)}{x z} \) и \( \frac{k l - 1}{k l + 1} = \frac{(x + y)(z + t) - x z}{(x + y)(z + t) + x z} \).

Обозначим \( \angle F A C = \beta, \angle F D B = \gamma \), тогда \( \alpha = = 90^{\circ} + \beta + \gamma \). Значит, \( \sin \alpha = \cos \gamma \cos \beta - \sin \gamma \sin \beta = = \frac{(x + y)(z + t) - x z}{\sqrt{\left(x^{2} + (z + t)^{2}\right)\left(z^{2} + (y + t)^{2}\right)}} \), последнее равенство получается из прямоугольных треугольников \( A F C \) и \( B F D \). Остаётся заметить, что \( \sqrt{\left(x^{2} + (z + t)^{2}\right)\left(z^{2} + (y + t)^{2}\right)} \geqslant x z + (z + t)(y + t) \) по

неравенству Коши - Буняковского - Шварца, получаем требуемое неравенство

Разобьём все позиции на две половины по 100 столбцов - «левую» и «правую». Предположим, что в каждой строке, в которой есть два солнца в одной половине (назовём их солнечными), ветер сдул листья с одной из таких пар солнц, а в каждой несолнечной строке-таких строк ровно \(101^{2}\) - ветер обнаружил положения всех солнц (в несолнечной строке не более двух солнц, так что ветер мог так поступить). Тогда Юрий * сообразит, что те строки, где открыты два солнца в одной половине-точно солнечные, а значит, несолнечные строки-это в точности те \(101^{2}\) строк, в которых ветер не открывал два солнца в одной половине. У каждой из них открыты все солнца, так что закрытые листьями изображения в этих строках-луна.

Первое решение. Без ограничения общности можно считать, что лучи \(A B\) и \(D C ; C B\) и \(D A\) пересекаются. Пусть отрезки \(A C\) и \(B D\) пересекаются в точке \(G\), а также \(A^{\prime} B^{\prime} C^{\prime} D^{\prime}\) - четырёхугольник, образованный прямыми \(\ell_{a}, \ell_{b}, \ell_{c}, \ell_{d}\) (см.

Пусть \(\angle B^{\prime} A B = \alpha\). Из вписанности четырёхугольника \(A^{\prime} B^{\prime} C^{\prime} D^{\prime}\) и условий \(A X\left\|\ell_{d}, C Y\right\| \ell_{b}\) имеем : \(\alpha = \angle B^{\prime} A X = = 180^{\circ}-\angle A^{\prime} B^{\prime} C^{\prime} = \angle C^{\prime} D^{\prime} X = \angle Y C A^{\prime}\). Значит, во-первых, точки \(A, D^{\prime}, X, C^{\prime}\) лежат на одной окружности, обозначим её \(\gamma_{1}\); во-вторых, точки \(C, Y, A^{\prime}, B^{\prime}\) лежат на одной окружности, обозначим её \(\gamma_{2}\); в-третьих, точки \(A, X, C, Y\) лежат на одной окружности, обозначим её \(\gamma_{0}\). Заметим, что точка \(B\) - радикальный центр окружностей \(\gamma, \gamma_{0}, \gamma_{1}\) (поскольку она лежит на прямых \(A X\) и \(C^{\prime} D^{\prime}\) ); точка \(D\) - радикальный центр окружностей \(\gamma, \gamma_{0}, \gamma_{2}\) (так как она лежит на прямых \(C Y\) и \(A^{\prime} B^{\prime}\) ). Таким образом, \(B D\) - радикальная ось окружностей \(\gamma_{0}\) и \(\gamma ; A C\) - радикальная ось окружностей \(\gamma_{0}\) и \(\omega ; E F\) - радикальная ось окружностей \(\omega\) и \(\gamma\), поэтому эти три прямые пересекаются в одной точке, что и требовалось доказать.

Второе решение. Введём обозначения как в первом решении. Для точки плоскости \(P\) обозначим через \(f(P)\) разность степеней точки \(P\) относительно окружностей \(\omega\) и \(\gamma\). Поскольку \(E F\) - радикальная ось окружностей \(\omega\) и \(\gamma\), то достаточно доказать, что \(f(G) = 0\). Кроме того, легко видеть, что \(f(A) = = A C^{\prime} \cdot A B^{\prime}\) и \(f(C) = -C D^{\prime} \cdot C A^{\prime}\)

Заметим, что функция \(f\) - линейная, то есть для точки \(P\) на отрезке \(Q R\) выполнено равенство \(f(P) = = \frac{P R \cdot f(Q) + P Q \cdot f(R)}{Q R}(\star)\). Мы докажем это утверждение позднее. Пока, применив его для точек \(A, G, C\), мы получим, что \(f(G) = \frac{A G \cdot f(C) + C G \cdot f(A)}{A C}\).

Таким образом, достаточно доказать, что \(\frac{f(A)}{-f(C)} = = \frac{A G}{C G}(\star \star)\). Заметим, что \(\frac{A G}{G C} = \frac{d(A, B D)}{d(C, B D)} = \frac{S_{A B D}}{S_{B C D}} = \frac{A B \cdot A D}{C B \cdot C D}\) (последнее равенство следует из того, что \(\angle B A D + \angle B C D = = 180^{\circ}\); через \(d(P, \ell)\) мы обозначаем расстояние от точки \(D\) до

прямой \(\ell\) ). Следовательно, равенство ( \(\star \star\) ) переписывается в виде : \(\frac{A C^{\prime} \cdot A B^{\prime}}{C D^{\prime} \cdot C A^{\prime}} = \frac{A B \cdot A D}{C B \cdot C D}\).

Из вписанности четырёхугольника \(A B C D\) и данных в условии параллельностей прямых следуют равенства углов : \(\angle C A^{\prime} D = 180^{\circ}-\angle A D B^{\prime} = \angle B A D = 180^{\circ}-\angle B C D = \angle C B C^{\prime} = = \angle A C^{\prime} B ; \angle A B C^{\prime} = \angle C D A^{\prime}\) и \(\angle B C D^{\prime} = \angle B^{\prime} A D\). Таким образом, \(\triangle A B C^{\prime}\) и \(\triangle C D A^{\prime}\), а также \(\triangle D A B^{\prime}\) и \(\triangle B C D^{\prime}\) подобны по двум углам. Из подобия получаем равенства отношений \(\frac{A C^{\prime}}{C A^{\prime}} = \frac{A B}{C D}\) и \(\frac{A B^{\prime}}{C D^{\prime}} = \frac{A D}{B C}\), остаётся лишь перемножить эти равенства.

Вернёмся к доказательству линейности функции \(f\). Введём декартовы координаты таким образом, чтобы центры окружностей \(\omega\) и \(\gamma\) лежали на оси абсцисс, пусть их координаты будут \(\left(x_{1}, 0\right)\) и ( \(x_{2}, 0\) ), а радиусы окружностей - \(R_{1}\) и \(R_{2}\). Тогда для произвольной точки \(P\) с координатами ( \(x, y\) ) по определению степени точки мы получаем, что \(f(P) = \left(x - x_{1}\right)^{2} + y^{2}-R_{1}^{2}- -\left(x - x_{2}\right)^{2}-y^{2} + R_{2}^{2} = a x + b\), где \(a\) и \(b\) - две константы. Если точка \(P\) лежит на отрезке \(Q R\) и \(x_{q}, x_{r}\) - координаты точек \(Q\) и \(R\) по оси абсцисс, то \(x = \frac{P R \cdot x_{q} + P Q \cdot x_{r}}{Q R}\), откуда немедленно следует ( \(\star\) ).

Замечание 1. Линейная функция в произвольным образом введённых декартовых координатах имеет вид \(f(x, y) = a x + + b y + c\). Если она отлична от константы, то решением уравнения \(f(x, y) = 0\) будет прямая. Например, таким образом (рассуждая как в приведённом решении) доказывается, что радикальная ось двух окружностей-это прямая, перпендикулярная линии центров.

Замечание 2. Приведём план решения задачи с помощью комплексных чисел. Пусть окружность \(\omega\) - стандартная единичная, координаты точек \(A, B, C, D\) обозначаются соответственно \(a, b, c, d\). Рассмотрим прямые (точнее, уравнения прямых) \(\ell_{a c}(z) = a c \bar{z} + z - a - c, \ell_{b d}(z) = b d \bar{z} + z - b - d-\) это соответствующие диагонали \(A C, B D\). Прямая \(\ell_{a}\) через точку \(A\) параллельно \(B C\) имеет уравнение \(\ell_{a}(z) = b c \bar{z} + z - b c / a - a\), аналогично три другие прямые из условия. Окружность \(\gamma\), проходящая через точки их пересечения, имеет уравнение \(F(z) : = = \ell_{a}(z) \ell_{c}(z)-\ell_{b}(z) \ell_{d}(z)\) : с одной стороны, точки пересечения удовлетворяют условию \(F = 0\), с другой стороны, коэффициенты при \(z^{2}\) и \(\bar{z}^{2}\) сокращаются, так что это именно окружность. Радикальная ось окружностей \(\gamma\) и \(\omega\) имеет уравнение \(\ell_{e f}(z) : = = F(z)-T(z \bar{z}-1)\), где \(T\) - подходящий коэффициент, чтобы получилась прямая (он нам не будет важен в дальнейшем). Докажем, что для некоторых коэффициентов \(\tau, \theta\) имеет место тождество \(\ell_{e f}(z) + \tau \ell_{a c}(z) + \theta \ell_{b d}(z) = 0(\mathrm{~A})\), из этого будет следовать требуемое. Тождество (A) достаточно проверять, когда \(z\) - одна из вершин четырёхугольника \(A B C D\), потому что на одной прямой они не лежат. Подставляя, например, \(z = a\), получаем тождество \(0 = F(a) + \theta \ell_{b d}(a) = -\ell_{b}(a) \ell_{d}(a) + \theta \ell_{b d}(a)\). Это даёт значение \(\theta\), и оно должно быть согласовано со значением, которое получается для \(z = c\), то есть должно выполняться тождество \(\ell_{b}(a) \ell_{d}(a) / \ell_{b d}(a) = \ell_{b}(c) \ell_{d}(c) / \ell_{b d}(c)\), и второе аналогичное. Все эти значения считаются непосредственно (и раскладываются на множители, например, \(\left.\ell_{b d}(a) = b d / a + a - b - d = (a - b)(a - d) / d\right)\), после чего не составляет труда доказать нужное тождество.

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

Докажем, что после сотого утра найдётся сугроб высотой не менее 112 дм. Предположим, что такого сугроба нет. Так как дворник в сотое утро полностью сгреб снег с какого-то ряда, в десяти клетках квадрата снега нет. В каждой из оставшихся 90 клеток, по нашему предположению, не более 111 дм³ снега, то есть всего снега не больше, чем 9990 дм³. Однако за 100 ночей суммарно выпало 10 000 дм³ снега. Противоречие.

Покажем, как может действовать дворник, чтобы после сотого утра каждый сугроб имел высоту не более 112 дм (то есть в каждой клетке было не более 112 дм³ снега).

Способ 1. Первые 11 дней дворник сгребает снег из второго столбца в первый, следующие 11 дней — из третьего столбца во второй, затем 11 дней — из четвёртого в третий, и т. д. Через 99 дней в десятом столбце не будет снега. Посчитаем, сколько снега стало в столбце \(i\le 9\) через 99 дней. Вечером \(11(i-1)\)-го дня в столбце номер \(i\) не было снега, а в столбце \(i+1\) в каждой клетке было по \(11(i-1)\) дм³ снега. На следующий вечер в столбце \(i\) станет по \(11(i-1)+2\) дм³ снега в каждой клетке. Затем ещё десять дней количество снега в каждой клетке \(i\)-го столбца будет увеличиваться на \(2\), а затем \(11(9-i)\) дней — на \(1\). Итого, через 99 дней в каждой клетке столбца \(i\) будет по \(11(i-1)+22+11(9-i)=110\) дм³ снега. В сотую ночь выпадет ещё по 1 дм³ в каждую клетку. А сотым утром дворник сгребёт снег из десятого столбца в девятый. Таким образом, в каждой клетке будет не более 112 дм³ снега.

Способ 2. Пусть дворник сгребёт снег из \(2\)-го столбца в \(1\)-й, из \(3\)-го — во \(2\)-й, …, из \(10\)-го — в \(9\)-й. Тогда вечером девятого дня в первых девяти столбцах будет по 10 дм³ снега в каждой клетке, а в десятом столбце снега не будет. Затем дворник проделывает аналогичный процесс в обратном порядке: из \(9\)-го — в \(10\)-й, из \(8\)-го — в \(9\)-й, …, из \(2\)-го — в \(1\)-й. Тогда вечером 18-го дня в клетках последних девяти столбцов будет по 20 дм³ снега, а в первом столбце снега не будет. Аналогично повторим такие сдвиги (каждый длится 9 дней) ещё \(9\) раз, и через 99 дней получим в клетках девяти столбцов по \(110\) дм³ снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более \(112\) дм³ снега в каждой клетке.

Первое решение. Пусть \(H'\) и \(X'\) — точки, симметричные точкам \(H\) и \(X\) относительно середины стороны \(BC\) соответственно.

Тогда \(HXH'X'\) — параллелограмм. Так как \(\angle BX'C=\angle BH'C=\angle BHC=180^\circ-\angle BAC\), точки \(X'\) и \(H'\) лежат на окружности \(\Omega\). При этом, поскольку \(H'B\parallel CH\perp AB\), точка \(H'\) диаметрально противоположна точке \(A\) на этой окружности; следовательно, \(AH'\) проходит через \(O\). Вспоминая, что \(XO\parallel H'X'\), получаем \(\angle AYX'=180^\circ-\angle AH'X'=180^\circ-\angle AOX=\angle AYX\); это и означает, что точки \(Y\), \(X\) и \(X'\) лежат на одной прямой.

Второе решение. Поскольку \(\angle BHC=180^\circ-\angle ABC\), окружность \((BHC)\) симметрична окружности \(\Omega\) относительно \(BC\); пусть \(O'\) — центр окружности \((BHC)\), а \(M\) — середина \(BC\). Тогда \(M\) — ещё и середина \(OO'\).

Как известно, \(AH=2\,OM\) (это доказывается, например, с помощью гомотетии с центром в точке пересечения медиан треугольника \(ABC\) и коэффициентом \(-2\)). Поэтому \(OO'=2\,OM=AH\). Поскольку \(OO'\parallel BC\parallel AH\), четырёхугольник \(AHO'O\) — параллелограмм.

Пусть \(T\) — точка на луче \(O'X\) такая, что \(O'T=2\,O'X\). Тогда \(XT=O'X=O'H=AO\). Кроме того, из равнобедренности треугольника \(O'XH\) получаем, что \(\angle TXO=\angle O'XH=\angle O'HX=\angle AOX\), поэтому треугольники \(TXO\) и \(AOX\) равны. Значит, \(\angle TOX=\angle AXO\).

Поскольку \(XM\) — средняя линия в треугольнике \(O'TO\), получаем \(\angle MXO=\angle TOX=\angle AXO\), то есть \(XO\) — биссектриса угла \(AXM\). Но в окружности \((AXOY)\) имеем \(OA=OY\), так что \(O\) — середина дуги \(AXY\), а потому \(XO\) — внешняя биссектриса угла \(AXY\). Отсюда и следует, что углы \(AXM\) и \(YXM\) смежные, то есть точки \(X\), \(Y\) и \(M\) лежат на одной прямой.

Построим пример 8 квадратных трёхчленов, удовлетворяющих условию задачи: \(\,f_1(x)=-x^2+2\,\), \(\,f_2(x)=3x^2-2\,\), \(\,f_3(x)=-4x^2+3\,\);

\(\,f_4(x)=2x^2-3\,\), \(\,f_5(x)=-4x^2+x+4\,\), \(\,f_6(x)=4x^2+x-4\,\);

\(\,f_7(x)=-5x^2-x+5\,\), \(\,f_8(x)=5x^2-x-5\,\).

Данные многочлены составлены так, чтобы их значения в точках \(x=-1,0,1\) соответствовали следующей таблице:

У трёхчленов этого примера нет общего корня (его нет даже у \(f_1(x)\) и \(f_2(x)\)). Осталось показать, что они удовлетворяют условию. Очевидно, никакие два из этих трёхчленов не дают в сумме ноль.

Пусть выбрана какая-то пара из этих квадратных трёхчленов. Если была выбрана пара \(\,(f_{2k-1}(x),\,f_{2k}(x))\,\), где \(k=1,2,3,4\), то все многочлены можно разбить на пары \(\,(f_1(x),f_2(x))\,\); \(\,(f_3(x),f_4(x))\,\); \(\,(f_5(x),f_6(x))\,\); \(\,(f_7(x),f_8(x))\,\), и каждая из этих сумм имеет корень \(0\).

В противном случае нетрудно убедиться, что значение суммы двух выбранных трёхчленов либо в точке \(x_0=-1\), либо в точке \(x_0=1\) (а может быть, и в обеих сразу) равняется нулю. Выберем такое \(x_0\). Оставшиеся многочлены в точке \(x_0\) принимают значения \(-1\) и \(1\) ровно по три раза, и их можно разбить на пары так, чтобы в \(x_0\) суммы всех четырёх пар равнялись нулю, т. е. \(x_0\) был их общим корнем.

Докажем, что в аналогичной задаче для шеренги из \(2n\) детей наибольшее возможное количество хороших пар равно \((n+1)^2-3\).

Пронумеруем детей числами \(1,2,\dots,2n\) в порядке убывания роста. Если расставить их как \(n+1,n+2,\dots,2n,1,2,\dots,n\), то все пары \((i,j)\) при \(i\le n\lt j\) окажутся хорошими; таких пар \(n^2\). Кроме того, все пары вида \((i,i+1)\) также хороши; их \(2n-1\). Пара \((n,n+1)\) учтена дважды, поэтому всего получаем \(n^2+(2n-1)-1=(n+1)^2-3\).

Остаётся доказать, что хороших пар не больше, чем \((n+1)^2-3\). Проведём индукцию по \(n\). При \(n=1\) утверждение тривиально, так как есть единственная пара.

Пусть \(n\gt 1\). Рассмотрим произвольную шеренгу и выберем в ней хорошую пару \((a,b)\), для которой \(\lvert a-b\rvert\) максимально; будем считать, что \(a\lt b\), а ребёнок \(a\) стоит левее \(b\). Назовём ребёнка \(c\) прекрасным, если он образует хорошие пары и с \(a\), и с \(b\).

Лемма. Прекрасных детей не больше двух.

Доказательство. Если \(c\) прекрасен, то по выбору \((a,b)\) имеем \(c-a\le b-a\) и \(b-c\le b-a\), откуда \(a\lt c\lt b\). Такой ребёнок \(c\) не может стоять между \(a\) и \(b\), иначе \((a,b)\) не была бы хорошей. Значит, любой прекрасный ребёнок стоит либо слева от \(a\), либо справа от \(b\).

Предположим, что есть два прекрасных ребёнка \(c_1\lt c_2\), стоящих левее \(a\); тогда \(a\lt c_1\lt c_2\lt b\). Ребёнок \(c_1\) не может стоять между \(a\) и \(c_2\), иначе \((a,c_2)\) не была бы хорошей; следовательно, \(c_1\) стоит левее \(c_2\). Тогда \(c_2\) стоит между \(c_1\) и \(b\), и пара \((c_1,b)\) не хорошая — противоречие. Значит, левее \(a\) не более одного прекрасного ребёнка; аналогично, не более одного — правее \(b\). Лемма доказана.

Завершим индукцию. Удалим \(a\) и \(b\). Все хорошие пары, не содержащие \(a\) и \(b\), сохраняются; по предположению индукции их не более \(n^2-3\). Пары с участием \(a\) или \(b\): это \((a,b)\); пары \((a,c)\) и \((b,c)\) для любого прекрасного \(c\); и для каждого прочего \(c\) — не более одной из \((a,c)\) или \((b,c)\). Итого не более \(1+(2n-2)+2=2n+1\) пар. Поэтому суммарно не более \((n^2-3)+(2n+1)=(n+1)^2-3\), что и требовалось доказать.

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

Считаем, что дощечки выложены на числовой прямой. Примем \( 1 = 1 с м \).

Возьмем \( 0 < \varepsilon < 0,01 \) такое, что разность длин любой пары соседних дощечек больше \( 10 \varepsilon \). Отметим на прямой бесконечную в обе стороны арифметическую прогрессию с разностью \( \varepsilon \) так, чтобы концы дощечек не были отмечены. Кузнечик будет прыгать только по отмеченным точкам, и длины его прыжков будут из множества \( \{\varepsilon, \ell, 2 \ell, 4 \ell, 8 \ell, 16 \ell, 32 \ell, 64 \ell\} \), где \( \ell = N \varepsilon \), а натуральное \( N \) подберём так, что \( \ell < 2 \) и \( 64 \ell > 101 \).

Стратегия кузнечика будет такой : прыгать вправо по зелёной дощечке на \( \varepsilon \) пока возможно, и далее перепрыгивать очередную красную дощечку прыжком минимальной возможной длины (такая длина найдётся, поскольку длина самого длинного прыжка больше \( 100 + \varepsilon \) ). Итак, пусть сделан прыжок длины \( 2 d \) из зелёного отрезка через очередной красный отрезок \( [a, b] \). Нам остаётся убедиться, что после этого прыжка кузнечик окажется в следующем зелёном отрезке \( [b, c] \). Предположим, что это не так, и кузнечик из точки \( a - x \), где \( 0 < x < \varepsilon \) перепрыгнул в точку \( a - x + 2 d > c \). Видим, что \( 2 d > (c - b) + (b - a) > 2 \), значит, в множестве длин прыжков кузнечика есть длина \( d \). Далее, по выбору \( \varepsilon \), имеем \( (c - b) > (a - b) + 10 \varepsilon \), поэтому можем оценить \( 2 d > (c - b) + (b - a) > 2(b - a) + 10 \varepsilon \). Видим, что \( d > (b - a) + \varepsilon \), а значит, кузнечик мог из точки \( a - x \) перепрыгнуть красный отрезок \( [a, b] \) прыжком более коротким, чем \( 2 d \). Противоречие.

Первое решение. Пусть \( \angle A D C = x \). Из равнобедренных треугольников \( D M E \) и \( D M F \) (или из того, что \( M \) - центр окружности \( (D E F) \) ) имеем \( \angle E M F = 360^{\circ} - 2 x \) Для решения задачи остаётся понять, что тому же равен \( \angle E B F \).

При гомотетии с центром \( D \) и коэффициентом \( 1 / 2 \) точки \( E \), \( F, B \) перейдут соответственно в \( E^{\prime}, F^{\prime}, B^{\prime} \) - середины отрезков \( D E, D F \) и \( D B \). Вместо \( \angle E B F \) найдём \( \angle E^{\prime} B^{\prime} F^{\prime} \), заметив, что \( E^{\prime} \) и \( F^{\prime} \) - проекции \( M \) на \( A D \) и \( C D \), а \( B^{\prime} \) - центр параллелограмма, или середина \( A C \), тем самым, \( B^{\prime} \) - проекция \( M \) на \( A C \). Видим, что \( M, E^{\prime}, A, B^{\prime} \) лежат на одной окружности с диаметром \( M A \). Отсюда \( \angle D E^{\prime} B^{\prime} = \angle A M B^{\prime} = \angle A M C / 2 = \angle A B C / 2 = x / 2 \). Аналогично \( \angle D F^{\prime} B^{\prime} = x / 2 \). Из четырёхугольника \( E^{\prime} B^{\prime} F^{\prime} D \) видим, что \( \angle E^{\prime} B^{\prime} F^{\prime} = 360^{\circ} - x - x / 2 - x / 2 = 360^{\circ} - 2 x \), что и требовалось.

Второе решение. Достаточно доказать равенство углов \( \angle A B E = \angle C B F \) (т.е. изогональность \( B E \) и \( B F \) относительно \( A B, B C) \). Действительно, тогда \( M \) будет лежать на внешней биссектрисе угла \( E B F \) и на серединном перпендикуляре к \( E F \), а значит, будет совпадать с серединой дуги ( \( E B F \) ).

Равенство углов \( \angle A B E = \angle C B F \), в свою очередь, эквивалентно подобию \( A B E \sim C B F \). Докажем это подобие.

Отметим на луче \( A B \) за точкой \( B \) точку \( X \) так, что \( B X = = B C \), а на луче \( C B \) за точкой \( B \) точку \( Y \) так, что \( B Y = B A \). Легко понять, что треугольники \( B M C \) и \( B M X \) равны по двум сторонам и углу между ними. Тогда \( M X = M C = M A \). Рассмотрим серединный перпендикуляр к \( D F \), тогда он является перпендикуляром к параллельной прямой \( A X \), а поскольку \( M A = M X \), то он же является серединным перпендикуляром к \( A X \). Таким образом, трапеция \( A D F X \) равнобедренная, а раз \( A B C D \) - параллелограмм, то \( C X B F \) - также равнобедренная трапеция, причём \( C B = B X = X F \) и \( \angle X B C = 180^{\circ} - - \angle A B C \). Аналогичное получим для трапеции \( A Y B E \). Видим, что \( A Y B E \sim C X B F \), откуда следует нужное нам \( A B E \sim C B F \).

Замечание. Требуемое в решении 2 подобие \( A B E \sim C B F \) можно доказать и по - другому - установив равенство \( A E \cdot B C = = C F \cdot A B \). Последнее можно сделать, например, счётом в синусах через элементы треугольника \( A B C \), выразив проекцию \( A M \) на \( A D \), далее выразив отрезок \( A E \) и т.д.

Имеются и другие вычислительные решения, в том числе с использованием комплексных чисел.

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

Пронумеруем белые отрезки слева направо как \(w_{1}, w_{2}, \ldots, w_{y_{1}}\), а чёрные — как \(b_{1}, b_{2}, \ldots, b_{y_{2}}\). Для каждого чёрного отрезка \(b_{j}\) назовём его силой \(S(b_{j})\) количество индексов \(i \le y_{1}-1\) таких, что \(b_{j}\) пересекается как с \(w_{i}\), так и с \(w_{i+1}\). Если с какой-то парой \((w_{i}, w_{i+1})\) пересекаются два чёрных отрезка, то они имеют общую точку, что невозможно по условию. Поэтому каждая такая пара учтена в силе не более чем одного чёрного отрезка, а значит,

\(\sum_{j=1}^{y_{2}} S(b_{j}) \le y_{1}-1.\)

Рассмотрим следующие \(y_{1}\) групп, состоящих из \(x_{1}\) белых отрезков каждая: при \(0 \le i \le y_{1}-x_{1}\) группа \(G_{i}\) состоит из отрезков \(w_{i+1}, w_{i+2}, \ldots, w_{i+x_{1}}\), а при \(y_{1}-x_{1}+1 \le i \le y_{1}-1\) группа \(G_{i}\) состоит из отрезков \(w_{i+1}, w_{i+2}, \ldots, w_{y_{1}}\), а также из \(w_{1}, w_{2}, \ldots, w_{i+x_{1}-y_{1}}\) (иначе говоря, каждая группа состоит из \(x_{1}\) последовательных отрезков в циклическом порядке). Для группы \(G_{i}\) обозначим через \(N(G_{i})\) количество чёрных отрезков, не пересекающихся ни с одним из отрезков в \(G_{i}\). По условию \(N(G_{i}) \le x_{2}-1\); поэтому

\(\Sigma := \sum_{i=0}^{y_{1}-1} N(G_{i}) \le y_{1}\bigl(x_{2}-1\bigr).\)

С другой стороны, каждый чёрный отрезок \(b_{j}\) пересекается максимум с \(1+S(b_{j})\) белыми отрезками, и все эти белые отрезки расположены подряд. Тогда количество групп, содержащих хотя бы один из этих белых отрезков, не превосходит \(1+S(b_{j})+(x_{1}-1)=S(b_{j})+x_{1}\). Поэтому отрезок \(b_{j}\) учтён хотя бы в \(y_{1}-\bigl(S(b_{j})+x_{1}\bigr)\) числах вида \(N(G_{i})\). Поэтому

\(\begin{aligned} \Sigma &\ge \sum_{j=1}^{y_{2}}\bigl(y_{1}-S(b_{j})-x_{1}\bigr) = y_{2}(y_{1}-x_{1}) - \sum_{j=1}^{y_{2}} S(b_{j}) \\ &\ge y_{2}(y_{1}-x_{1}) - (y_{1}-1). \end{aligned}\)

Из полученных двух оценок на \(\Sigma\) вытекает, что \(\;y_{1}(x_{2}-1) \ge y_{2}(y_{1}-x_{1}) - (y_{1}-1) \Longleftrightarrow (y_{1}-x_{1})(y_{2}-x_{2}) \le x_{1}x_{2}-1\), что и требовалось доказать.

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

Предположим, что утверждение задачи для некоторых \(x_{1}, x_{2}, y_{1}, y_{2}\) неверно: \((y_{1}-x_{1})(y_{2}-x_{2}) \ge x_{1}x_{2}\), и при этом условии сумма \(y_{1}+y_{2}\) — минимальная возможная.

Без ограничения общности тогда \(y_{1}-x_{1} \ge x_{1}\). Возьмём \(x_{1}\)-й слева белый отрезок \(W\) и \((y_{2}-x_{2})\)-й слева чёрный отрезок \(B\). У какого-то из них правый конец левее.

1) Пусть правый конец \(W\) левее (или концы совпадают). Тогда правые \(x_{2}\) чёрных отрезков не пересекаются с левыми \(x_{1}\) белыми. Противоречие.

2) Пусть правый конец \(B\) левее. Выкинем все белые отрезки слева от \(W\) (включая его) и все чёрные отрезки слева от \(B\) (включая его). Оставшиеся белые отрезки (их хотя бы \(x_{1}\)) не пересекаются с выкинутыми \(y_{2}-x_{2}\) чёрными; отсюда уже следует, что \(y_{2}-x_{2} \lt x_{2}\).

Положим \(x_{1}'=x_{1}\), \(y_{1}'=y_{1}-x_{1}\ge x_{1}'\), \(x_{2}'=x_{2}-(y_{2}-x_{2})\) и \(y_{2}'=y_{2}-(y_{2}-x_{2})=x_{2}\ge x_{2}'\); тогда осталось \(y_{1}'\) белых и \(y_{2}'\) чёрных отрезков. Рассмотрим любые \(x_{1}'\) оставшихся белых и \(x_{2}'\) оставшихся чёрных отрезков. Если среди них нет пересекающихся, то, добавив к ним все выкинутые чёрные отрезки, получим набор из \(x_{1}=x_{1}'\) белых и \(x_{2}=x_{2}'+(y_{2}-x_{2})\) чёрных отрезков исходного набора, среди которых нет пересекающихся; это невозможно. Значит, оставшийся набор удовлетворяет условию (для новых чисел \(x_{1}', y_{1}', x_{2}', y_{2}'\)), при этом в нём меньше отрезков, чем в исходном, поэтому

\(\begin{aligned} 0 &< x_{1}'x_{2}' - (y_{1}'-x_{1}')(y_{2}'-x_{2}') \\ &= x_{1}(2x_{2}-y_{2}) - (y_{1}-2x_{1})(y_{2}-x_{2}) \\ &= x_{1}x_{2} - (y_{1}-x_{1})(y_{2}-x_{2}) \le 0, \end{aligned}\)

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

Замечание. Отметим, что при \(x_{1}=x_{2}=1\) утверждение задачи превращается в двумерную (одномерную) теорему Хелли.

Будем измерять высоту сугроба в дециметрах. Также будем считать, что сторона одной клетки равна 1 дм, то есть за каждую ночь на клетку выпадает 1 дм \({ }^{3}\) снега.

Докажем, что после сотого утра найдется сугроб высотой не менее 112 дм. Предположим, что такого сугроба нет. Так как дворник в сотое утро полностью сгрёб снег с какого-то ряда, в десяти клетках квадрата снега нет. В каждой из оставшихся 90 клеток, по нашему предположению, не более 111 дм \({ }^{3}\) снега, то есть всего снега не больше, чем 9990 дм \(^{3}\). Однако за 100 ночей суммарно выпало 10000 дм \(^{3}\) снега. Противоречие.

Покажем, как может действовать дворник, чтобы после сотого утра каждый сугроб имел высоту не более 112 дм (то есть в каждой клетке было не более 112 дм \({ }^{3}\) снега).

Способ 1. Первые 11 дней дворник сгребает снег из второго столбца в первый, следующие 11 дней дворник сгребает снег из третьего столбца во второй, затем 11 дней из четвёртого в третий, и т. д. Через 99 дней в десятом столбце не будет снега. Посчитаем, сколько снега стало в столбце \(i \leqslant 9\) через 99 дней. Вечером \(11(i - 1)\)-го дня в столбце номер \(i\) не было снега, а в столбце \(i + 1\) в каждой клетке было по \(11(i - 1)\) дм \(^{3}\) снега. На следующий вечер в столбце \(i\) станет по \(11(i - 1) + 2\) дм \({ }^{3}\) снега в каждой клетке. Затем ещё десять дней количество снега в каждой клетке \(i\)-го столбца будет увеличиваться на 2 , а затем \(11(9-i)\) дней-на 1. Итого, через 99 дней в каждой клетке столбца \(i\) будет по \(11(i - 1) + 22 + 11(9-i) = 110\) дм \(^{3}\) снега. В сотую ночь выпадет ещё по 1 дм \({ }^{3}\) в каждую клетку. А сотым утром дворник сгребет снег из десятого столбца в девятый. Таким образом, в каждой клетке будет не более 112 дм \({ }^{3}\) снега.

Способ 2. Пусть дворник сгребёт снег из 2-го столбца в 1-ый, из \(3-\) го во \(2-\) й, . . . , из \(10-\) го в 9-ый. Тогда вечером девятого дня в первых девяти столбцах будет по 10 дм \(^{3}\) снега в каждой клетке, а в десятом столбце снега не будем. Затем дворник проделывает аналогичный процесс в обратном порядке : из 9-го в 10-ый, из 8-го в 9-ый, ..., из 2-го в первой. Тогда вечером 18-го дня в клетках последних девяти столбцов будет по 20 дм \(^{3}\) снега, а в первом столбце не будет снега. Аналогично повторим такие сдвиги (каждый длится 9 дней) ещё 9 раз, и через 99 дней получим в клетках девяти столбцов по 110 дм \({ }^{3}\) снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более 112 дм \({ }^{3}\) снега в каждой клетке.

Пусть прямая \(A H\) повторно пересекает окружность \(\omega\) в точке \(D\) . Тогда прямая, проведённая по условию через \(O\) - серединный перпендикуляр к хорде \(A D\), пусть она пересекает стороны \(A B\) и \(A C\) в точках \(X\) и \(Y\), а прямая через \(H\) из условия задачи пересекает их в точках \(Z\) и \(T\). Поскольку \(X Y \| A C\), то окружность ( \(A X Y\) ) касается окружности \(\omega\) в точке \(A\). При симметрии относительно \(X Y\) окружность \(\omega\) переходит в себя, а окружность ( \(A X Y\) ) переходит в окружность ( \(D X Y\) ), тогда она тоже касается окружности \(\omega\).

Поскольку \(Z H \perp A O\), то \(\angle A Z H = 90^{\circ}-\angle O A B = \angle A C B =\) \(= \angle A D B\).

Следовательно, четырёхугольник \(B Z H D\) - вписанный. Тогда \(\angle B Z D = \angle B H D = 90^{\circ}-\angle H C B = \angle A C B\). Значит, в силу сказанного выше, \(\angle X Y D = \angle A Y X = \angle A C B = \angle B Z D\), поэтому точка \(Z\) лежит на окружности ( \(D X Y\) ). Аналогично, на этой окружности лежит и точка \(T\), откуда и следует требуемое.

Замечание. Можно рассуждать несколько иначе : установить (похожими равенствами углов), что точки \(X, Y, Z, T\) лежат на одной окружности, а также что окружности ( \(D X Y\) ) и ( \(D Z T\) ) касаются окружности \(\omega\) в точке \(D\). Однако эти три окружности не могут быть различными, поскольку в таком случае их радикальные оси не пересекаются в одной точке, в чём нетрудно убедиться. Значит, все эти окружности совпадают, что нам и требовалось.

Дорогу, которую хотят строить сразу два мэра, назовём надёжной. Рассмотрим в каждой компоненте самую дешёвую дорогу \(A B\). Тогда она является надёжной. Предположим, что в этой компоненте есть ещё одна надёжная дорога \(C D\) (ясно, что города \(C, D\) отличны от \(A, B\) ) и рассмотрим путь по дорогам от одного из городов \(A, B\) до одного из городов \(C, D-\) не умаляя общности, он имеет вид \(A X_{1} X_{2} \ldots X_{k} C\) (города \(X_{1}\), \(\ldots, X_{k}\) отличны от \(A, B, C, D\), возможно, \(k = 0\) ). Тогда дорогу \(A X_{1}\) хочет строить мэр города \(X_{1}\) (мэр города \(A\) хочет строить \(A B\) ), дорогу \(X_{1} X_{2}\) - мэр города \(X_{2}\) (мэр города \(X_{1}\) хочет строить \(\left.X_{1} A\right)\) и так далее, мэр города \(C\) хочет строить дорогу \(C X_{k}\), а не \(C D\) - противоречие.

Итак, в каждой компоненте есть ровно одна надёжная дорога. Для каждой из \(n(n - 1) / 2\) пар городов \(A, B\) рассмотрим случайную величину \(\xi_{A B}\), которая равна 1 , если \(A B\) - надёжная дорога, и 0 в противном случае. Из доказанного следует, что \(M\) есть сумма \(\xi_{A B}\) по всем \(n(n - 1) / 2\) парам \(\{A, B\}\). Для данных \(A\), \(B\) событие \(\xi_{A B} = 1\) означает, что дорога \(A B\) - самая дешёвая из \(2 n - 3\) дорог, выходящих из \(A\) или \(B\), так что вероятность такого события равна \(1 / (2 n - 3)\) (из симметричности распределения цен эти дороги равноправны, так что каждая из них является самой дешёвой с вероятностью \(1 / (2 n - 3))\). Значит, математическое ожидание \(\xi_{A B}\) равно \(1 / (2 n - 3)\), а математическое ожидание случайной величины \(M\) равно сумме этих математических ожиданий по всем парам, то есть \(\frac{n(n - 1)}{2(2 n - 3)}\).

Все сравнения в этом решении производятся по модулю \(p\). Если \(a\) и \(b\) - целые числа, причём \(b\) не делится на \(p\), то через \(a / b\) мы обозначаем тот единственный остаток \(c\) по модулю \(p\), для которого \(a \equiv b c\).

Пусть числа \(1^{0}, 2^{1}, 3^{2}, \ldots, k^{k - 1}\) дают ровно \(d\) различных остатков при делении на \(p\). Обозначим \(t = [p / 4]\). Тогда выражения вида \(f(a) = (2 a)^{2 a - 1} / \left(a^{a - 1}\right)^{2} = 2^{2 a - 1} a\) при \(1 \leqslant a \leqslant t\) дают максимум \(d^{2}\) различных остатков.

Назовём пару натуральных чисел \((a, b)\) таких, что \(1 \leqslant a < < b \leqslant t\), исключительной, если \(f(a) \equiv f(b)\). Покажем, что для каждого \(\delta = 1,2, \ldots, t - 1\) существует не более одной исключительной пары \((a, b)\), в которой \(b - a = \delta\). Действительно, если \((a, b)\) - такая пара, то из \(2^{2 a - 1} a = 2^{2 b - 1} b\) вытекает, что \(a / b \equiv 2^{2 \delta}\), откуда \(b = a + \delta \equiv 2^{2 \delta} b + \delta\), или \(b\left(1 - 2^{2 \delta}\right) \equiv \delta\). Такой остаток \(b\) не более чем единственен (поскольку \(\delta \neq 0\) ), а по нему восстанавливается \(a\).

Итого, существует не более чем \(t - 1\) исключительная пара; обозначим их количество через \(S\). Пусть числа \(f(1), f(2), \ldots\), \(f(t)\) дают ровно \(\ell\) различных остатков по модулю \(p\), встречающихся \(a_{1}, a_{2}, \ldots, a_{\ell}\) раз соответственно. Тогда \(\sum_{i = 1}^{\ell} a_{i} = t\) и \(S = \sum_{i = 1}^{\ell} C_{a_{i}}^{2}\). Верна следующая цепочка неравенств : \(t - 1 \geqslant S = \frac{1}{2}\left(\sum_{i = 1}^{\ell} a_{i}^{2}-\sum_{i = 1}^{\ell} a_{i}\right) \geqslant \frac{t^{2} / \ell - t}{2}\)

откуда \(\ell \geqslant t^{2} / (3 t - 2) > t / 3\). Вспоминая, что \(\ell \leqslant d^{2}\), получаем оценку \(d > \sqrt{t / 3} \geqslant[\sqrt{p / 12}]\).

Таким образом, в качестве искомой константы \(c\) можно взять, например, число \(1 / 24\) : для простых \(p < 12\) неравенство \(d > \frac{\sqrt{p}}{24}\) тривиально, а для \(p > 12\) следует из неравенства \([x] \geqslant x / 2\) при \(x > 1\).

Будем наращивать множество ситуаций, в которых Тая побеждает (т.е. сможет получить \(n\) равных чисел).

(1) Пусть у нас \(n\) нечётных чисел.

Тогда за одну операцию можно получить \(n\) двоек.

(2) Пусть никакая сумма двух соседних чисел не является степенью двойки.

Тогда за одну операцию можно получить ситуацию (1).

(3) Пусть среднее арифметическое \(s\) всех чисел не равно степени двойки.

Покажем, что сможем прийти к ситуации (2). Воспользуемся следующей леммой, доказательство которой приведём в конце решения.

Лемма. Пусть \(a_{1}, a_{2}, \ldots, a_{n}\) - вещественные числа, \(s-\) их среднее арифметическое. За один ход меняем набор \(a_{1}, a_{2}\), \(\ldots, a_{n}\) на \(\frac{a_{1} + a_{2}}{2}, \frac{a_{2} + a_{3}}{2}, \ldots, \frac{a_{n} + a_{1}}{2}\). Тогда для любого \(\varepsilon > 0\) через несколько ходов все числа будут лежать в интервале ( \(s- -\varepsilon, s + \varepsilon)\).

Ясно, что \(s > 1\). Выберем \(\varepsilon > 0\) так, чтобы интервал \((s-\varepsilon, s + \varepsilon)\) целиком помещался между соседними степенями двойки : \(2^{t - 1} < s-\varepsilon < s + \varepsilon < 2^{t}\) для некоторого натурального \(t\). Будем проводить много раз операцию замены пары соседней на их сумму. Тогда, согласно лемме, найдётся \(N\) такое, что после \(N\) операций все числа будут лежать в интервале \(\left(2^{N}(s-\varepsilon), 2^{N}(s + \varepsilon)\right)\), а значит, в интервале между соседними степенями двойки \(2^{N} \cdot 2^{t - 1}\) и \(2^{N} \cdot 2^{t}\). Значит, после ( \(N - 1\) ) операции выполнялось условие (2).

(4) Пусть все числа не меньше 2.

Если мы не в ситуации (2), то есть пара соседей \(a, b\), сумма которых равна \(2^{t}\), где \(t \geqslant 2\) - натуральное. Попробуем сделать следующую операцию произвольно, только \(a\) и \(b\) заменим на число 2 . Пусть в такой попытке мы не пришли в ситуацию ( 3 ), то есть получили ситуацию, в которой среднее арифметическое \(s\) равно степени двойки. Тогда сделаем другую попытку, в которой все пары меняются так же, только только \(a\) и \(b\) заменяются на 4 . По сравнению с первой попыткой \(s\) увеличилось на \(\frac{2}{n}\), поэтому мы окажемся в ситуации (3).

(5) Пусть набор исходных чисел произвольный. Тогда после одной операции имеем ситуацию (4).

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

\(s + x_{0}, s + x_{1}, \ldots, s + x_{n}\) - данные числа, так что \(x_{0} + \ldots + x_{n} = 0\). Пусть \(M = \max \left\{\left|x_{0}\right|, \ldots,\left|x_{n}\right|\right\}\). Ясно, что после хода \(M\) не увеличится. Достаточно понять, что что через некоторое количество \(k\) ходов этот максимум отклонения станет не более \(\lambda M\) для некоторого фиксированного \(0 < \lambda < 1\). Ниже увидим, что можно положить \(k = n\) и \(\lambda = \frac{2^{n}-n - 1}{2^{n}}\).

Через \(n\) ходов у нас будет набор \(s + y_{0}, s + y_{1}, \ldots, s + y_{n}\), где \(y_{0} = \frac{1}{2^{n}}\left(x_{0} + C_{n}^{1} x_{1} + C_{n}^{2} x_{2} + \ldots + C_{n}^{n - 1} x_{n - 1} + x_{n}\right)\) и т.д.

Так как \(x_{0} + x_{1} + \ldots + x_{n} = 0\), имеем \(x_{0} + C_{n}^{1} x_{1} + C_{n}^{2} x_{2} + \ldots + + C_{n}^{n - 1} x_{n - 1} + x_{n} = \left(C_{n}^{1}-1\right) x_{1} + \left(C_{n}^{2}-1\right) x_{2} + \ldots + \left(C_{n}^{n - 1}-1\right) x_{n - 1}\). Отсюда \(\left|y_{0}\right| \leqslant \frac{1}{2^{n}}\left(\left(C_{n}^{1}-1\right) + \ldots + \left(C_{n}^{n - 1}-1\right)\right) M = \frac{2^{n}-n - 1}{2^{n}} M\). Аналогично все \(\left|y_{i}\right| \leqslant \frac{2^{n}-n - 1}{2^{n}} M\).