Пример : \(1,2,3,4,5,6,8,10,12,20\). В этом наборе три числа \((5,10,20)\) делятся на 5 , четыре числа \((4,8,12,20)\) делятся на 4 , а общая сумма равна 71 .

Замечание. Можно доказать (но, конечно, в задаче этого не требуется), что на самом деле в любом примере, удовлетворяющем условию задачи, должны обязательно присутствовать числа \(1,2,3,4,5,8,10,12\) и 20 , а вместо числа 6 можно взять 7 или 9 .

Пусть \(S\) - сумма цифр числа \(N\). Тогда суммы цифр полученных чисел будут равны \(S + 1, S + 2, \ldots, S + 9\). Три из этих сумм будут делиться на 3. По признаку делимости на 3, соответствующие три числа на доске также будут делиться на 3. При этом они будут больше 3, а значит, будут составными. Поэтому больше 6 простых чисел на доске оказаться не может.

Шесть простых чисел может оказаться даже при \(N = 1\) -

например, если Петя получит, среди прочих, числа \(11,13,41\), 61,17 и 19.

Замечание. Петя может получить шесть простых чисел, даже если он будет приписывать цифры лишь с одной стороны например, из числа \(N = 3\) он может получить числа \(13,23,43\), 53,73 и 83.

Пусть \(d\) - абсцисса вершины параболы \(y = P(x)\), так что прямая \(x = d\) - ось симметрии параболы. Тогда для любых чисел \(t\) и \(s\) с суммой \(2 d\) (т.е. таких, что точки \(t\) и \(s\) симметричны относительно \(d\) ) выполнено \(P(t) = P(s)\). Таким образом, любая тройка попарно различных чисел \(a, b, c\) таких, что \(a + b + c = 2 d\), будет удовлетворять условию задачи. Можно взять, скажем, \(a = \frac{2 d}{3}-1, b = \frac{2 d}{3}, c = \frac{2 d}{3} + 1\).

Пусть \(P(x) = u x^{2} + v x + w\). По условию,

\(\begin{aligned} (a - b)(u(a + b) + v) = \left(u a^{2} + v a + w\right)-\left(u b^{2}\right. & + v b + w) = \\ & = P(a)-P(b) = n^{2} \end{aligned}\)

Поскольку \(n\) - натуральное число, \(a - b \neq 0\). Будем искать подходящие пары чисел \((c, d)\) в виде \(c = a + k\) и \(d = b - k\). Тогда разность \(P(c)-P(d)\) будет равна

\((c - d)(u(c + d) + v) = (a - b + 2 k)(u(a + b) + v) = \frac{a - b + 2 k}{a - b} n^{2} .\)

Таким образом, нам достаточно подобрать такие \(k\), для которых дробь \(\frac{a - b + 2 k}{a - b}\) будет квадратом натурального числа. При \(k = = (a - b) m\) дробь будет равна нечётному числу \(2 m + 1\). Тогда нам подойдут те \(m\), при которых \(2 m + 1\) будет квадратом нечётного числа.

Замечание. Заметим, что у многочлена из условия некоторые (или даже все!) коэффициенты могут оказаться иррациональными. Например, условие выполнено для многочлена \(P(x) = u x^{2} + (1-u) x - u\) и чисел \(a = -1, b = 2\), где \(u-\) произвольное число.

Заметим, что если число \(u\) иррационально, то выражение

\(P(c)-P(d)\) может оказаться целым только при \(c + d = a + b\) или \(c = d\).

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

Если граф-это цикл, содержащий 101 вершину, то на любых 100 вершинах ровно 99 рёбер, так что такая компания удовлетворяет условиям задачи. Осталось показать, что не существует такой компании из 102 человек (тогда и компании из более чем 102 человек тоже быть не может). Ниже мы приводим несколько различных способов сделать это; в каждом способе мы предполагаем, от противного, что такая компания нашлась.

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

Пусть теперь во всём графе на 102 вершинах \(\ell\) рёбер. При выкидывании любой вершины (скажем, степени \(d\) ) получается подграф с нечётным числом рёбер \(\ell - d\); аналогично рассуждению выше получаем, что и во всём графе степени всех вершин имеют одинаковую чётность. Заметим, что наш граф не может

быть пустым (т.е. не иметь рёбер) или полным (т.е. иметь все \(C_{102}^{2}\) рёбер), иначе на любых 100 вершинах будет либо 0 , либо \(C_{100}^{2} = 99 \cdot 50\) рёбер, то есть чётное количество. Тогда найдётся вершина, соединённая хоть с какой-то другой вершиной, но не со всеми. Иначе говоря, есть вершины \(u, v_{1}\) и \(v_{2}\) такие, что \(u\) соединена с \(v_{1}\), но не с \(v_{2}\). Степени вершин \(v_{1}\) и \(v_{2}\) в исходном графе одной чётности, поэтому после удаления \(u\) они будут иметь разную чётность. Это невозможно по доказанному выше.

Второе решение. Существует всего \(n = C_{102}^{2} = 51 \cdot 101\) способов выбросить две вершины из 102 , оставив 100. Пронумеруем эти способы числами от 1 до \(n\). Пусть \(a_{i}\) - количество рёбер на оставшихся 100 вершинах в \(i\)-м способе; по предположению, все числа \(a_{i}\) нечётны, а значит, нечётна и их сумма \(S\) (поскольку число \(n\) нечётно).

С другой стороны, рассмотрим любое ребро uv. Это ребро учтено в числе \(a_{i}\) ровно тогда, когда вершины \(u\) и \(v\) не выброшены в \(i\)-м способе, то есть когда выброшена какая-то пара из оставшихся 100 вершин. Это происходит в \(k = C_{100}^{2} = 50 \cdot 99\) способах. Итак, каждое ребро учтено в \(S\) чётное количество \(k\) раз, поэтому \(S\) должно быть чётным. Противоречие.

Третье решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.

Случай 1. Пусть общее количество рёбер в графе нечётно. Тогда, выкидывая любую пару вершин, мы должны выкинуть из графа чётное число рёбер (чтобы осталось нечётное число). С другой стороны, если мы выкидываем вершины со степенями \(d_{1}\) и \(d_{2}\), то число выкинутых рёбер равно \(d_{1} + d_{2}\), если эти вершины не соединены ребром, и \(d_{1} + d_{2}-1\), если соединены. Отсюда следует, что вершины одинаковой чётности всегда не соединены ребром, а вершины разной чётности-всегда соединены.

Значит, если в графе \(k\) чётных вершин и \(\ell\) нечётных, то чётные вершины имеют (чётную) степень \(\ell\), а нечётные (нечётную) степень \(k\). Это невозможно, ибо \(k + \ell = 102\).

Случай 2. Пусть общее количество рёбер в графе чётно. Аналогично получаем, что вершины одинаковой чётности всегда соединены ребром, а вершины разной чётности не соединены. Поэтому, если в графе \(k\) чётных вершин и \(\ell\) нечётных, то чётные

вершины имеют (чётную) степень \(k - 1\), а нечётные - (нечётную) степень \(\ell - 1\). Это опять же противоречит равенству \(k + \ell = 102\).

Замечание. Разумеется, существуют и другие примеры компании из 101 человека, удовлетворяющей условию.

Во всех решениях ниже окружность, описанная около треугольника \(C E F\), обозначается через \(\omega\), а её центр через \(O\).

Первое решение. Внешняя ( \(C D\) ) и внутренняя ( \(C E\) ) биссектрисы угла \(A C B\) перпендикулярны. Тогда \(\angle D A E = = \angle D C E = 90^{\circ}\), и четырёхугольник \(A D C E\) вписан. Поэтому \(\angle A D E = \angle A C E\), откуда \(\angle B E F = 180^{\circ}-\angle A E D-\angle D E F = = 90^{\circ}-\angle A E D = \angle A D E = \angle A C E = \angle E C F\). Значит, \(\omega\) касается \(A B\) (в точке \(E ;\) см. рис. 1).

Выберем на отрезке \(B C\) такую точку \(P\), что \(P E \| A C\). Тогда \(\angle P E C = \angle E C A = \angle P C E\), откуда \(P C = P E\). Поскольку \(O C = = O E\), получаем, что \(P O\) - биссектриса внешнего угла \(B P E\).

Совершим гомотетию с центром \(B\), переводящую треугольник \(B P E\) в \(B C A\). Тогда прямая \(P O\) перейдёт в \(C D\), а прямая \(E O\) (перпендикулярная \(A B\) ) - в \(A D\). Значит, точка \(O\) перейдёт в \(D\), откуда и следует, что точка \(O\) лежит на \(B D\).

Рис. 1

Рис. 2

Второе решение. Выберем на прямых \(C D\) и \(A C\) точки \(D^{\prime}\) и \(F^{\prime}\) так, что \(\angle A B D^{\prime} = \angle D^{\prime} E F^{\prime} = 90^{\circ}\) (см. рис. 2). Как и выше, докажем, что окружность \(\omega\) касается \(A B\). Аналогично, описанная окружность треугольника \(C E F^{\prime}\) также касается \(A B\) в точке \(E\) (и тоже проходит через \(C\) ). Поэтому эти окружности совпадают, то есть \(F^{\prime}\) лежит на \(\omega\).

Докажем, что центром \(\omega\) является точка \(T\) пересечения диагоналей \(B D\) и \(A D^{\prime}\) трапеции \(A D D^{\prime} B\). Заметим сразу, что из вписанных четырёхугольников \(A D C E\) и \(B D^{\prime} C E\) получаются равенства \(\angle A E D = \angle A C D = \angle B C D^{\prime} = \angle B E D^{\prime}\), так что прямоугольные треугольники \(A E D\) и \(B E D^{\prime}\) подобны, и \(\frac{A E}{B E} = \frac{A D}{B D^{\prime}} = \frac{D T}{B T}\). Значит, \(E T\|A D\| B D^{\prime}\).

Пусть \(T E\) пересекает \(D D^{\prime}\) в точке \(E^{\prime}\). Поскольку \(E^{\prime}\) лежит на диаметре \(\omega\), проходящем через \(E\), и \(\angle E C E^{\prime} = 90^{\circ}\), точка \(E^{\prime}\) лежит на \(\omega\). Прямая \(E E^{\prime}\) параллельна основаниям трапеции и проходит через точку пересечения диагоналей трапеции; как ихвестно, в этом случае \(E E^{\prime}\) делится точкой \(T\) пополам. Поскольку \(E E^{\prime}\) - диаметр \(\omega\), получаем \(T = O\).

Замечание. После доказательства того, что \(\omega\) касается \(A B\) в точке \(E\), существуют и другие способы продолжения решения. Приведём набросок одного из них.

Нетрудно видеть, что \(\angle C E F = \angle C A E = \mu\). Отметим на луче \(B D\) точку \(X\) так, что \(\angle B C X = 90^{\circ}-\angle C E F = \angle D A C\); тогда \(\angle X C D = \angle C D A = \nu\). Применяя теорему синусов, можно получить, что

\(\frac{B X}{X D} = \frac{B C}{C D} \cdot \frac{\cos \mu}{\sin \nu} = \frac{B C}{C D} \cdot \frac{C D}{C A} = \frac{B C}{C A} = \frac{B E}{E A} .\)

Таким образом, точка \(X\) лежит на прямых \(E O\) и \(C O\), то есть \(O = E\) (если эти две прямые не совпадают, то есть \(A C \neq B C\) ).

Записывая условие при \(n = 2022, k = 1011\) и при \(n = 1011, k = 2022\), получаем

\(a_{2022} = a_{2022}-a_{1011} \geqslant 2022^{3}-1011^{3}\)

и

\(-a_{2022} = a_{1011}-a_{2022} \geqslant 1011^{3}-2022^{3},\)

то есть \(a_{2022} \geqslant 2022^{3}-1011^{3} \geqslant a_{2022}\). Отсюда и следует ответ.

Замечание. Последовательность, удовлетворяющая условию, существует, а именно \(a_{n} = n^{3}-1011^{3}\). Более того, аналогично решению выше несложно показать, что такая последовательность единственна. Однако для решения задачи не требуemcя ни находить все такие последовательности, ни даже приводить пример такой последовательности.

Первое решение. Занумеруем вертикали слева направо

числами от 1 до 100, Пусть \(a\) - верхняя строка квадрата, а \(b\) - строка сразу под ней. Пусть в петином разбиении эти строки заняты вертикальными домино \(a 1-b 1, a 2-b 2, \ldots, a 98-b 98\) и горизонтальными домино \(a 99-a 100, b 99-b 100\). Очевидно, что оставшуюся часть доски можно разбить на домино (например, на горизонтальные), поэтому такое разбиение существует.

Предположим, что существует васино разбиение на домино, удовлетворяющее требованиям задачи. Если в васином разбиении какая-то из клеток \(a 1, a 2, \ldots, a 98\) занята вертикальным домино, то это-то же домино, что и в петином разбиении, и из этих двух клеток нельзя добраться до остальных. Поэтому в васином разбиении обязательно должны присутствовать домино \(a 1-a 2, a 3-a 4, \ldots, a 97-a 98\). Аналогично, клетки \(a 99\) и \(a 100\) не могут быть накрыты горизонтальными домино, поэтому они накрыты вертикальными домино \(a 99-b 99\) и \(a 100-b 100\). Но тогда из четырёх клеток \(a 99, a 100, b 99, b 100\) нельзя попасть в остальные-противоречие.

Замечание. Существуют и другие варианты петиного разбиения, при которых требуемое невозможно. Например, если обозначить через \(c\) строку непосредственно под \(b\), то годится любое разбиение, содержащее следующие пять домино : \(a 1-b 1\), \(a 2-b 2, a 3-a 4, b 3-b 4, c 1-c 2\) (такие разбиения существуют).

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

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

Пусть \(a\) - верхняя горизонталь, а \(z\) - нижняя. Пусть в петином разбиении присутствуют домино \(a 1-a 2\) и \(z 2-z 3\) (такое разбиение возможно, если, например, клетки \(z 1\) и \(z 100\) покрыть вертикальными домино, а все остальные домино сделать горизонтальными). Тогда эти отрезки будут ориентированы как

\(a 1 \rightarrow a 2\) и \(z 2 \rightarrow z 3\). Если они находятся в одном цикле, то этот цикл должен пройти от \(a 2\) к \(z 2\), а затем от \(z 3\) к \(a 1\). Но такие два пути должны иметь общую клетку, что невозможно.

Поскольку \(A D \| C B\), треугольники \(E A D\) и \(E C B\) подобны, и потому \(\frac{B E}{D E} = \frac{B C}{A D}\).

Достроим треугольник \(B C D\) до параллелограмма \(B C D K\) (см. рис. ??). Тогда треугольники \(D E F\) и \(D B K\) подобны, поэтому \(\frac{D F}{D E} = \frac{D K}{D B}\). Наконец, поскольку \(D K = B C\) и \(D B = D A\), получаем

\(\frac{D F}{D E} = \frac{D K}{D B} = \frac{B C}{A D} = \frac{B E}{D E}\)

откуда и следует, что \(D F = B E\). Рис. 3

Первое решение. Пример. Покажем сначала, что при \(N = 180\) требуемое возможно. Отметим на окружности 180 точек, разбивающих её на 180 равных дуг величиной по \(2^{\circ}\) каждая. Величина любой дуги с концами в двух из отмеченных точек выражается чётным числом градусов, поэтому величина любого вписанного в окружность угла, образованного тремя отмеченными точками, выражается натуральным числом градусов. Следовательно, 180 отмеченных точек удовлетворяют условию задачи.

Оценка. Осталось доказать, что \(N \leqslant 180\). Любые три отмеченных точки образуют треугольник, поэтому не могут лежать на одной прямой. Считая отмеченные точки расположенными на координатной плоскости, обозначим через \(A\) любую из них с максимальной ординатой. Среди оставшихся выберем точки \(B\) и \(C\) такие, что угол \(B A C\) максимален.

Из условия задачи следует, что в треугольнике \(A B C\) величины углов \(A B C\) и \(A C B\) не меньше \(1^{\circ}\), поэтому величина угла \(B A C\) не больше \(178^{\circ}\). Ввиду выбора точек \(B\) и \(C\) остальные \(N - 3\) отмеченные точки лежат строго внутри угла \(B A C\), и каждый луч с началом в точке \(A\) содержит не больше одной из них. Проведя через каждую отмеченную точку внутри угла \(B A C\) луч с началом в точке \(A\), получим \(N - 3\) различных луча, делящих \(\angle B A C\) на \(N - 2\) угла. Если \(N - 2 > 178\), то хотя бы один из этих углов имеет величину, меньшую \(1^{\circ}\), и является углом некоторого треугольника с вершинами в трёх отмеченных точках, что противоречит условию задачи. Следовательно, \(N - 2 \leqslant 178\), то есть \(N \leqslant 180\), что и требовалось доказать.

Замечание 1. Описать выбор используемой в решении точки \(A\) можно также следующими способами.

1. Рассмотрим вершину \(A\) выпуклой оболочки системы отмеченных точек. В качестве точек \(B\) и \(C\) тогда можно взять соседние с \(A\) вершины выпуклой оболочки.

2. Рассмотрим опорную прямую множества отмеченных точек, т.е. такую прямую, что все отмеченные точки лежат по одну сторону от этой прямой, а на самой прямой лежит хотя бы одна отмеченная точка. Эту точку и можно взять за точку \(A\).

Замечание 2. В примере отмеченные точки являются вершинами правильного 180-угольника. Все примеры для \(N = 180\) устроены именно таким образом (это несложно вывести, используя рассуждения из доказательства оценки, но конечно, это не требуется в решении).

Второе решение. Приведём другое доказательство оценки. Рассмотрим пару отмеченных точек \(A, B\) на наибольшем расстоянии друг от друга. Тогда для любой другой отмеченной точки \(C\) сторона \(A B\) - наибольшая в треугольнике \(A B C\), поэтому, в частности, угол \(\angle B A C\) острый.

Проведя из точки \(A\) лучи во все отмеченные точки, получаем, что все эти лучи различны (ибо три отмеченных точки не могут лежать на одной прямой), и каждый составляет с лучом \(A B\) острый угол, выражаемый целым числом градусов. Такой угол (если луч не совпадает с \(A B\) ) может принимать значения от \(1^{\circ}\) до \(89^{\circ}\), поэтому количество таких лучей \(N - 2\) не превосходит \(2 \cdot 89 = 178\). Отсюда \(N \leqslant 180\).

Замечание 3. Доказать более слабые оценки \(N \leqslant 361\) и даже \(N \leqslant 181\) можно, рассматривая любую отмеченную точку \(A\) (без какого-то специального выбора) и выходящие из нее лучи в другие отмеченные точки. Действительно, так как угол между любыми двумя такими лучми измеряется целым числом градусов, возможных направлений данных лучей - 360 , отсюда \(N \leqslant 361\). Кроме того, из любой пары противоположных направлений может присутствовать не более одного, поэтому лучей не более 180 , и \(N \leqslant 181\).

Замечание 4. Можно доказать оценку несколько подругому. Рассмотрим угол \(B A C\) выпуклой оболочки множества отмеченных точек. Он выражен натуральным числом градусов и меньше \(180^{\circ}\), значит он не превосходит \(179^{\circ}\). Далее повторяя

рассуждения из решения, получаем, что \(N - 2 \leqslant 179\), откуда \(N \leqslant 181\).

Если хотя бы один угол выпуклой оболочки не больше \(178^{\circ}\), то доказываем оценку \(N \leqslant 180\) так же, как в первом решении.

Остается случай, когда все углы выпуклой оболочки равны \(179^{\circ}\), или все внешние углы выпуклой оболочки равны \(1^{\circ}\). Но сумма внешних углов выпуклого многоугольника равна \(360^{\circ}\), поэтому в выпуклой оболочке не менее 360 вершин, тогда \(N \geqslant \geqslant 360\). Но ранее показано, что \(N \leqslant 181\) - противоречие.

Положим \(a = 10^{100}\). Через \(s(m)\) обозначим сумму цифр числа \(m\). Отметим простое свойство \(s(\ell) + s(m) \geqslant s(\ell + + m)\), которое сразу видно, если числа \(\ell\) и \(m\) сложить в столбик.

Лемма. Пусть \(k\) - натуральное число, и пусть натуральное число \(m\) кратно \(10^{k}-1\). Тогда \(s(m) \geqslant 9 k\).

Доказательство. Индукция по \(m\). База \(m = 10^{k}-1\) очевидна.

Предположим, что \(m \geqslant 10^{k}\), и что утверждение доказано для всех чисел, меньших \(m\). Докажем его и для \(m\). Пусть последние \(k\) цифр числа \(m\) образуют число \(v\) (возможно, с ведущими нулями), а все остальные-число \(u > 0\) (иначе говоря, \(m = \overline{u v} = 10^{k} u + v\) ). Поскольку \(m\) делится на \(10^{k}-1\), то и (положительное) число \(m^{\prime} = u + v = m-\left(10^{k}-1\right) u\) также кратно \(10^{k}-1\). Поэтому \(s\left(m^{\prime}\right) \geqslant 9 k\) по предположению индукции, а тогда и \(s(m) = s(u) + s(v) \geqslant s(u + v) = s\left(m^{\prime}\right) \geqslant 9 k\).

Для решения задачи осталось взять такое \(k\), что \(9 k \geqslant a\), и заметить, что если \(b = 10^{k}-1\) и \(n \geqslant b\), то \(n!\) делится на \(10^{k}-1\) и, значит, \(s(n!) \geqslant 9 k \geqslant a\).

Замечание. В доказательстве леммы по сути использован следующий признак делимости на \(10^{k}-1\). Разобьём десятичную запись числа \(m\) на блоки по \(k\) цифр (первый блок может быть неполон). Воспринимая эти блоки как обычные числа (возможно, с ведущими нулями), сложим их, получив число \(m^{\prime}\). Тогда \(m\) кратно \(10^{k}-1\) тогда и только тогда, когда \(m^{\prime}\) делится на \(10^{k}-1\).

У леммы есть несколько вариаций; например, любое число, делящееся на число \(\underbrace{11 \ldots 1}_{k \text { единиц }}\), имеет сумму цифр, не меньшую \(k\).

Оценка. Докажем, что \(n > 160 <\) не работает».

Пусть дан набор из \(n\) конфет. Назовем сорт критическим, если конфет этого сорта ровно 10 (среди всех данных \(n\) конфет). Пусть у нас \(k\) критических сортов, тогда всего конфет не менее \(10 k : n \geqslant 10 k\). Уберем по одной конфете каждого критического сорта и организуем группу из оставшихся \(n - k\) конфет. Для этой группы нет сорта, представленного ровно 10 конфетами. Кроме того, \(n - k \geqslant n-\frac{n}{10} = \frac{9 n}{10} > \frac{9 \cdot 160}{10} = 144\). Значит, в рассматриваемой группе не менее 145 конфет, поэтому условие задачи не выполняется.

Пример. Теперь приведём пример ситуации, в которой у Васи может быть 160 конфет. Пусть у него есть ровно по 10 конфет 16 сортов. Пусть выбрана группа, для которой нет сорта, представленного ровно 10 конфетами. Тогда в эту группу не входит хотя бы одна конфета каждого сорта (иначе говоря, ни один сорт не будет взят полностью), т.е. группа содержит не более \(16 \cdot 9 = 144\) конфет, значит, условие задачи выполнено.

Замечание 1. Оценка \(n \leqslant 160\) может быть доказана также следующим, несколько другим способом. Предположим, что некоторое \(n = 145 + m\) «работает», т.е. существует набор \(K_{0}\) из \(n\) конфет, удовлетворяющий условию задачи. Тогда в наборе \(K_{0}\) есть в точности 10 конфет некоторого сорта \(A_{0}\). Уберем конфету \(a_{0}\) сорта \(A_{0}\) и рассмотрим группу \(K_{1}\) из оставшихся \(n - 1\) конфет. В группе \(K_{1}\) есть в точности 10 конфет некоторого сорта \(A_{1}\), при этом сорт \(A_{1}\) отличен от \(A_{0}\), так как в \(K_{1}\) есть

ровно 9 конфет сорта \(A_{0}\). Уберем из \(K_{1}\) конфету \(a_{1}\) сорта \(A_{1}\) и рассмотрим группу \(K_{2}\) из оставшихся \(n - 2\) конфет, в котором найдем 10 конфет нового сорта \(A_{3}\), и т.д., продолжим по шагам убирать по одной конфете и рассматривать группы оставшихся конфет. Так дойдем до группы \(K_{m}\), состоящей из \(\left|K_{m}\right| = 145\) конфет. При этом, согласно нашему алгоритму, \(K_{0}\) содержит по 10 конфет сортов \(A_{0}, \ldots, A_{m}\), значит \(\left|K_{0}\right| \geqslant 10(m + 1)\). Имеем \(145 + m \geqslant 10(m + 1)\), откуда \(m \leqslant 15\) и \(n \leqslant 160\).

Замечание 2. Пример при \(n = 160\) единственный.

Достаточно доказать утверждение : многочлен \(P(x)\) делится на \((x - 1)^{2}\). Действительно, после деления (например, столбиком), в частном получится многочлен \(Q(x)\) с целыми коэффициентами, и тогда равенство многочленов \(P(x) = (x- -1)^{2} Q(x)\) влечет равенство \(P(2022) = 2021^{2} \cdot Q(2022)\), из которого следует утверждение задачи, поскольку \(Q(2022)\) - целое число.

Для доказательства утверждения сделаем замену \(t = x - 1\), положим \(R(t) = P(t + 1) = a_{n}(t + 1)^{n} + a_{n - 1}(t + 1)^{n - 1} + \ldots + a_{1}(t + + 1) + a_{0}\) и докажем, что \(R(t)\) делится на \(t^{2}\), т.е. что последние два коэффициента многочлена \(R(t)\) равны 0 .

Свободный член многочлена \(R\) равен \(R(0) = a_{n} + a_{n - 1} + + \ldots + a_{0} = 0\).

Поскольку в многочлене \((t + 1)^{k}\) коэффициент при \(t\) равен

\(k\), коэффициент при \(t\) многочлена \(R\) равен \(n a_{n} + (n - 1) a_{n - 1} + + \ldots + a_{1}\). Из условий \(a_{n - k} = a_{k}\) следует, что удвоенный коэффициент при \(t\) равен \(\left(n a_{n} + (n - 1) a_{n - 1} + \ldots + a_{1}\right) + \left(n a_{0} + (n-\right. \left.-1) a_{1} + \ldots + a_{n - 1}\right) = n\left(a_{n} + a_{n - 1} + \ldots + a_{0}\right) = 0\).

Тем самым, задача решена.

Замечание. Утверждение о делимости \(P(x)\) на \((x - 1)^{2}\) можно доказать несколькими другими способами. Например : 1) Можно доказать, что при делении \(P(x)\) на \(x - 1\) мы получаем многочлен \(Q(x) = b_{n - 1} x^{n - 1} + b_{n - 2} x^{n - 2} + \ldots + b_{1} x + b_{0}\) такой, что \(b_{n - 1-k} = -b_{k}\) при всех \(0 \leqslant k \leqslant n - 1\). Отсюда последует \(Q(1) = 0\), и тогда, в силу теоремы Безу, \(Q(x)\) делится на \((x - 1)\).

2) Можно заметить, что \(P(1) = 0\) и \(P^{\prime}(1) = 0\).

Отметим точку \(I\) - центр общей вписанной окружности \(\omega\) треугольников \(A B C\) и \(D E F\). Поскольку \(D\) - середина дуги \(B C\), точки \(A, I, D\) лежат на одной прямой. Окружность \(\omega\) вписана в угол \(\angle F D E\), поэтому \(D I\) - биссектриса угла \(\angle F D E\), а точка \(A\) - середина дуги \(F E\).

Заметим, что четырёхугольник \(F E Y X\) вписанный. Это следует из равенства углов \(\angle F E D = \frac{1}{2}(\overparen{F B} + \overparen{B D}) = \frac{1}{2}(\overparen{F B} + + \overparen{C D}) = \angle F X B\). Аналогично, четырёхугольник \(B C T Z\) - вписанный.

Если \(B C \| E F\), то конструкция симметрична относительно прямой \(A D\), и утверждение задачи очевидно. Иначе отметим точку \(S\) пересечения прямых \(F E\) и \(B C\). Приравнивая произведения отрезков секущих для окружностей \(\Omega,(B C T Z)\) и ( \(F E Y X\) ) (т.е. степени точки \(S\) относительно этих трех окружностей), имеем : \(S X \cdot S Y = S F \cdot S E = S B \cdot S C = S Z \cdot S T\). Доказанное равенство \(S X \cdot S Y = S Z \cdot S T\) означает, что \(X, Y, Z, T\) лежат на одной окружности, что и требовалось доказать.

Пусть \(r\) - остаток меньшего из данных нечетных чисел при делении на 2022, так что \(r\) - некоторое нечётное число из множества \(\{1,3,5, \ldots, 2021\}\). Если \(r \leqslant 2017\), то два других остатка \(-r + 2\) и \(r + 4\), так что сумма остатков равна \(r + (r + + 2) + (r + 4) = 3(r + 2)\) - это число составное, так как делится на 3 и больше 3. Отдельно рассмотрим случаи \(r = 2019\) и \(r = 2021\). В первом случае остатки данных чисел равны 2019, 2021 и 1. Во втором случае остатки данных чисел равны 2021,1 и 3 . В обоих случаях сумма остатков делится на 3 и больше 3.

Замечание 1. Во всех трёх случаях сумма трёх остатков равна \(3(r + 2)-2022 k\), где \(k \in\{0,1,2\}\).

Замечание 2. Если в условии задачи 2022 заменить на другое число (не кратное 3), утверждение задачи может стать неверным. Например, сумма остатков чисел \(19,21,23\) при делении на 20 равна \(19 + 1 + 3 = 23\) - простое число.

Обозначим \(\angle A B C = \alpha\), тогда по условию \(\angle D A B = 2 \alpha\). На продолжении отрезка \(A B\) за точку \(A\) отметим точку \(F\) так, что \(A D = A F\). Тогда треугольник \(A F D\) равнобедренный, и его углы при основании равны. Так как \(\angle F A D = 180^{\circ}-2 \alpha\), то \(\angle A F D = \angle A D F = \alpha\).

Поскольку четырехугольник \(A B C D\) - вписанный, то

\(\angle A D C = 180^{\circ}-\angle A B C = 180^{\circ}-\alpha = 180^{\circ}-\angle A D F\). Следовательно, точки \(C, D\) и \(F\) лежат на одной прямой. Тогда \(\angle C F B = \alpha = \angle C B F\), поэтому треугольник \(F C B\) равнобедренный. Значит, его биссектриса \(C E\) совпадает с медианой. Итого, \(B E = E F = A D + A E\), что и требовалось.

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

рой точке \(F\), и при этом \(\angle B F C = \alpha\). Поскольку \(\angle C F B = \alpha = = \angle C B F\), треугольник \(F C B\) равнобедренный. Значит, его биссектриса \(C E\) совпадает с медианой, поэтому \(B E = E F = A F + + A E\).

Для завершения решения остаётся показать, что \(A F = A D\). Это следует из вписанности четырёхугольника \(A B C D\), поскольку \(\angle A D F = \angle C B F = \alpha\). Значит, треугольник \(A F D\) равнобедренный с равными углами \(\angle A F D = \angle A D F = \alpha\).

Пример. Фишку 50 последовательно 99 раз меняем со следующей против часовой стрелки. Получаем требуемое расположение.

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

Первый способ. Предположим, что при некотором \(k < 50\) требуемая расстановка получена.

В каждый момент времени считаем покрашенной дугу от фишки 100 до фишки 1 по часовой стрелке. Так как фишки 100 и 1 нельзя поменять за один ход, каждая конкретная фишка \(m\) \((2 \leqslant m \leqslant 99)\) могла попасть на покрашенную дугу или покинуть покрашенную дугу только путём обмена с одной из фишек 1 или 100.

Поскольку изначально и в конце фишка \(m\) не была на покрашенной дуге, она сделала одинаковое количество входов на покрашенную дугу и выходов с покрашенной дуги. При \(m \leqslant 50\) фишка \(m\) не могла меняться с фишкой 100, поэтому она могла делать вход или выход только путём обмена с фишкой 1. При входе фишка 1 совершает сдвиг на 1 по часовой стрелке, а при выходе — на 1 против часовой стрелки. Проведём аналогичные рассуждения для фишек \(m \geqslant 51\), которые не могут меняться с фишкой 1.

Тем самым, мы получаем, что фишки 1 и 100 совершат одинаковый сдвиг по и против часовой стрелки, поэтому они останутся на своих позициях. Противоречие.

Второй способ. Будем считать сдвиги фишек относительно их начальной позиции, причём сдвиг по часовой стрелке будет считаться с плюсом, против часовой — с минусом. Тогда при обмене двух фишек к сдвигу одной из них прибавляется \(+1\), а другой — \(-1\). Значит, в результате проведённых операций сумма сдвигов будет равна 0.

Рассуждаем от противного: пусть при \(k < 50\) каждая фишка \(i\) в итоге сдвинута на одну позицию по часовой стрелке, т. е. её сдвиг оказался равным \(1 + 100 t_{i}\) (здесь \(t_{i}\) — целое «число оборотов» по часовой стрелке, в частности, при \(t_{i} < 0\) фишка \(i\) сделала \(\left|t_{i}\right|\) оборотов против часовой стрелки). Тогда суммарный сдвиг всех 100 фишек равен \(100\left(t_{1}+t_{2}+\ldots+t_{100}\right)+100\). Поскольку он должен равняться 0, имеем \(t_{1}+t_{2}+\ldots+t_{100}=-1\).

Поскольку \(k < 50\), фишки с номерами \(i\) и \(j\), где \(j \geqslant i+50\), не могли меняться местами, поэтому их сдвиги в любой момент заведомо отличаются меньше чем на 100, значит, «количества оборотов» \(t_{i}\) и \(t_{j}\) равны при \(j \geqslant i+50\). Отсюда имеем \(t_{1}=t_{51}\), \(t_{2}=t_{52}, \ldots, t_{50}=t_{100}\). Тогда сумма \(t_{1}+t_{2}+\ldots+t_{100}=2\left(t_{1}+t_{2}+\ldots+t_{50}\right)\) чётна, а значит, не равна \(-1\). Противоречие.

Замечание 1. Последнее рассуждение можно видоизменить следующим образом. Отсюда \(t_{1}=t_{51}, t_{1}=t_{52}, \ldots, t_{1}=t_{100}, t_{2}=t_{100}, t_{3}=t_{100}, \ldots, t_{50}=t_{100}\), таким образом, все \(t_{i}\) равны \(t_{1}\). Тогда \(t_{1}+t_{2}+\ldots+t_{100}=100 t_{1} \neq -1\).

Замечание 2. Завершить сведение к противоречию можно и по-другому, заменив последний абзац решения на такое рассуждение. Поскрасим красным фишки, для которых \(t_{i} \geqslant 0\), и синим фишки, для которых \(t_{i} < 0\). Ясно, что на каком-то ходе синяя и красная фишки должны будут поменяться, поскольку разность их сдвигов не менее 100. Поскольку \(k < 50\), пара фишек 1 и 51 — одного цвета, аналогично пары фишек 1 и 52, \ldots, 1 и 100, 2 и 100, 3 и 100, \ldots, 50 и 100 — одного цвета. Таким образом, все фишки одного цвета. Мы знаем, что \(t_{1}+t_{2}+\ldots+t_{100}=-1\), поэтому среди чисел \(t_{1}, \ldots, t_{100}\) есть как неотрицательные, так и отрицательные, т. е. имеются как красные, так и синие фишки — противоречие.

Из условия задачи следует, что точки \(A, A^{\prime}, B, B^{\prime}\) лежат в одной плоскости, поэтому прямые \(B A^{\prime}\) и \(A B^{\prime}\) пересекают ребро \(C D\) в одной точке \(X\). Из условия следует, что эти прямые являются биссектрисами углов \(C A^{\prime} D, C B^{\prime} D\) соответственно. Отсюда, по свойству биссек-Рис. 4

трисы, \(C A^{\prime} : A^{\prime} D = C X : X D = C B^{\prime} : B^{\prime} D\), а поскольку \(\angle C A^{\prime} D = \angle C B^{\prime} D = 120^{\circ}\), треугольники \(C A^{\prime} D\) и \(C B^{\prime} D\) подобны. Поскольку \(C D\) - общая сторона этих треугольников, эти треугольники равны. В этих равных треугольниках равны соответствующие высоты из вершин \(A^{\prime}\) и \(B^{\prime}\). Это и требовалось доказать.

Указано, что прямые \(B A^{\prime}\) и \(A B^{\prime}\) пересекают ребро \(C D\) в одной точке; и кроме того, доказано соотношение \(C A^{\prime} : A^{\prime} D = = C B^{\prime} : B^{\prime} D\) или подобие \(C A^{\prime} D \sim C B^{\prime} D - 4\) балла.

Во всех решениях ниже мы рассматриваем граф

дружб, в котором вершины-это люди в компании, а два человека соединены ребром, если они дружат.

Рассмотрим 102 вершины, и построим на них следующий граф. Одну вершину \(x\) соединим с тремя другими \(v_{1}, v_{2}, v_{3}\). Остальные 98 вершин разобьём на пары и соединим вершины в каждой паре. Получился граф с \(98 / 2 + 3 = 52\) рёбрами. При удалении любой вершины удаляется нечётное число рёбер, то есть остаётся также нечётное число. Поэтому компания, описанная в условии, может состоять из 102 человек.

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

Первое решение. Существует всего \(n = C_{103}^{2} = 51 \cdot 103\) способа выбросить две вершины из 103 , оставив 101. Пронумеруем эти способы числами от 1 до \(n\). Пусть \(a_{i}\) - количество рёбер на оставшихся 101 вершинах в \(i\)-м способе; по предположению, все числа \(a_{i}\) нечётны, а значит, нечётна и их сумма \(S\) (поскольку число \(n\) нечётно).

С другой стороны, рассмотрим любое ребро uv. Это ребро учтено в числе \(a_{i}\) ровно тогда, когда вершины \(u\) и \(v\) не выброшены в \(i\)-м способе, то есть когда выброшена какая-то пара из оставшихся 101 вершин. Это происходит в \(k = C_{101}^{2} = 50 \cdot 101\) способах. Итак, каждое ребро учтено в \(S\) чётное количество \(k\) раз, поэтому \(S\) должно быть чётным. Противоречие.

Второе решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.

Случай 1. Пусть общее количество рёбер в графе нечётно. Тогда, выкидывая любую пару вершин, мы должны выкинуть из графа чётное число рёбер (чтобы осталось нечётное число). С другой стороны, если мы выкидываем вершины со степенями \(d_{1}\) и \(d_{2}\), то число выкинутых рёбер равно \(d_{1}+d_{2}\), если эти вершины не соединены ребром, и \(d_{1}+d_{2}-1\), если соединены. Отсюда следует, что вершины одинаковой чётности всегда не соединены ребром, а вершины разной чётности — всегда соединены.

Значит, если в графе \(k\) чётных вершин, то общее число рёбер равно \(k(103-k)\), то есть чётно. Но мы предполагали, что это количество нечётно — противоречие.

Случай 2. Пусть общее количество рёбер в графе чётно. Аналогично получаем, что вершины одинаковой чётности всегда соединены ребром, а вершины разной чётности не соединены. Поэтому, если в графе \(k\) чётных вершин, то число отсутствующих рёбер равно \(k(103-k)\), то есть чётно. Поэтому общее число рёбер есть \[ \binom{103}{2} - k(103-k) = 103 \cdot 51 - k(103-k), \] то есть нечётно. Но мы предполагали, что это количество чётно.

Замечание 1. Разумеется, существуют и другие примеры компании из 102 человек, удовлетворяющей условию.

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

Рассмотрим теперь весь граф на 103 вершинах. Назовём вершину чётной, если после её удаления остаётся граф, в котором все степени вершин чётны, и нечётной иначе. Тогда две вершины одной чётности соединены с одними и теми же из остальных вершин, а две вершины разной чётности — с наборами вершин, дополняющими друг друга до всего множества из 101 оставшейся вершины. Отсюда несложно выяснить, как и во втором решении, что граф либо полный двудольный, либо объединение двух полных графов. Далее можно действовать так же, как и в этом решении.

Назовём тройку натуральных чисел \((x, y, z)\), элементы которой принадлежат \(S\), хорошей, если выполняется равенство \(x^2 + y^2 + z^2 = 2(xy + yz + zx)\).

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

Выясним, когда тройка хорошая. Перепишем (*) как квадратное уравнение относительно \(x\): \(x^2 - 2x(y+z) + (y-z)^2 = 0\).

Решая его, получаем \(x = (y+z) \pm 2\sqrt{yz} = (\sqrt{y} \pm \sqrt{z})^2\), откуда \(\sqrt{x} = \pm\sqrt{y} \pm\sqrt{z}\). Иначе говоря, тройка является хорошей тогда и только тогда, когда одно из чисел \(\sqrt{x}, \sqrt{y}\) и \(\sqrt{z}\) равно сумме двух других.

Пусть \(s_1 < s_2 < \ldots < s_{100}\) — все элементы множества \(S\). Положим \(t_i = \sqrt{s_i}\). Оценим количество хороших троек \((x, y, z)\), в которых \(z\) — наибольшее число, то есть \(\sqrt{z} = \sqrt{x} + \sqrt{y}\).

Заметим, что при любых \(1 \leqslant i < j \leqslant 100\) есть не более одной такой тройки, в которой \(\sqrt{x} = t_i\) и \(\sqrt{z} = t_j\) (по этим значениям восстанавливается \(\sqrt{y} = \sqrt{z} - \sqrt{x}\)). Поэтому оцениваемое количество не превосходит количества таких пар чисел \((i, j)\), то есть \(\binom{100}{2}\).

Аналогично, количества хороших троек, в которых наибольшими являются \(x\) и \(y\), не превосходят \(\binom{100}{2}\). Поэтому общее количество хороших троек не больше \(3 \cdot \binom{100}{2}\).

Эта оценка достигается, если положить \(s_i = i^2\), то есть \(t_i = i\): действительно, тогда при любых \(i < j\) найдётся хорошая тройка \((s_i, s_{j-i}, s_j)\).

Замечание 1. Можно показать, что для того, чтобы оценка достигалась, необходимо выполнение равенств \(t_i = i\,t_1\) при всех \(i\). Поскольку \(1 \leqslant t_i \leqslant 100\), приведённый выше пример единственный.

Замечание 2. Можно показать, что верен следующий факт: равенство \(\sqrt{z} = \sqrt{x} + \sqrt{y}\) при натуральных \(x, y, z\) возможно лишь тогда, когда отношения \(x/z\) и \(y/z\) являются квадратами рациональных чисел, то есть когда \(x = a^2 t\), \(y = b^2 t\) и \(z = c^2 t\) при некоторых натуральных \(a, b, c\) и \(t\) (где \(a + b = c\)).

Из условия следует, что \(x, y \geqslant 1\), поскольку произведение цифр натурального числа не может быть отрицательным. Следовательно, числа \(n\) и \(n + 1\) не содержат нулей в десятичной записи. Тогда эти числа отличаются лишь последней цифрой, причём у числа \(n + 1\) она больше на один. Таким образом, \(y > x\). Если \(x - 1 > 0\), то, рассуждая аналогично, мы получим, что \(y - 1 < x - 1\), это противоречит доказанному выше. Следовательно, \(x - 1 = 0\). Тогда \(x = 1\), и в десятичной записи числа \(n\) все цифры равны 1 . Отсюда следует, что в числе \(n + 2\)

последняя цифра-двойка, а остальные цифры-единицы, поэтому \(y = 2\). Значит, \(y - 1 = 1\), и число \(m\) состоит лишь из единиц. Но тогда число \(m + 1\) не содержит нулей в десятичной записи. Однако, произведение его цифр равно нулю, противоречие.

Обозначим через \(O\) центр окружности, описанной около трапеции \(A B C D\). Тогда \(\angle C O D = 2 \angle C A D = \angle P A D + + \angle A D P = \angle C P D\). Здесь мы воспользовались тем, что центральный угол вдвое больше вписанного, и что внешний угол треугольника равен сумме двух внутренних, с ним не смежных.

Следовательно, точка \(O\) лежит на окружности \(\gamma\), описанной около треугольника \(C P D\), и поскольку \(O C = O D\), то \(O\) - середина дуги \(C P D\). Тогда отрезок \(O N\) - диаметр окружности \(\gamma\), а прямая \(O N\) - серединный перпендикуляр к отрезку \(C D\). В частности, середина отрезка \(C D\), обозначим её через \(S\), лежит на отрезке \(O N\). Из сказанного выше, \(\angle O C N = 90^{\circ} = \angle C S N\). Значит, окружность, описанная около треугольника \(S C N\), касается прямой \(O C\), поэтому \(O S \cdot O N = O C^{2} = O K \cdot O L\). Отметим точку \(S^{\prime}\), симметричную точке \(S\) относительно точки \(O\). Тогда \(O K \cdot O L = O S^{\prime} \cdot O N\), поэтому точки \(S^{\prime}, K, L, N\) лежат на одной окружности.

Рис. 3

Теперь заметим, что точки \(M\) и \(S\) симметричны относительно прямой \(K L\). Значит, \(O S^{\prime} = O S = O M\) и \(\angle L O S^{\prime} = \angle K O S = = \angle K O M\). Таким образом, точки \(M\) и \(S^{\prime}\) симметричны относительно серединного перпендикуляра к \(K L\). Следовательно, точки \(K, M, S^{\prime}\) и \(L\) лежат на одной окружности. Из сказанного выше, на этой окружности лежит также и точка \(N\), что и требовалось.

Первое решение. Заметим, что

\(\frac{a^{3}}{a^{2} + b + c} = a-\frac{a(b + c)}{a^{2} + b + c} \geqslant a-\frac{a(b + c)}{2 a \sqrt{b + c}} = a-\frac{\sqrt{b + c}}{2} .\)

Здесь мы оценили знаменатель по неравенству о средних : \(a^{2} + b + c \geqslant 2 a \sqrt{b + c}\)

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

\(a + b + c + d-\frac{\sqrt{a + b}}{2}-\frac{\sqrt{b + c}}{2}-\frac{\sqrt{c + d}}{2}-\frac{\sqrt{d + a}}{2} \geqslant 4\)

Поскольку \(a + b + c + d = 8\), это равносильно неравенству

\(\frac{\sqrt{a + b}}{2} + \frac{\sqrt{b + c}}{2} + \frac{\sqrt{c + d}}{2} + \frac{\sqrt{d + a}}{2} \leqslant 4 .\)

Но из неравенства между средним арифметическим и среднем квадратичным мы получаем, что

\(\frac{\sqrt{a + b}}{2} + \frac{\sqrt{c + d}}{2} \leqslant \sqrt{\frac{(\sqrt{a + b})^{2} + (\sqrt{c + d})^{2}}{2}} = 2\)

и, аналогично,

\(\frac{\sqrt{b + c}}{2} + \frac{\sqrt{d + a}}{2} \leqslant 2 .\)

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

Второе решение. По неравенству Коши–Буняковского–Шварца

\(\displaystyle \frac{a^{3}}{a^{2}+b+c}+\frac{b^{3}}{b^{2}+c+d}+\frac{c^{3}}{c^{2}+d+a}+\frac{d^{3}}{d^{2}+a+b} \geqslant \frac{\left(a^{2}+b^{2}+c^{2}+d^{2}\right)^{2}}{a\left(a^{2}+b+c\right)+b\left(b^{2}+c+d\right)+c\left(c^{2}+d+a\right)+d\left(d^{2}+a+b\right)}. \)

Таким образом, достаточно доказать, что

\(\displaystyle \left(a^{2}+b^{2}+c^{2}+d^{2}\right)^{2} \geqslant 4\left(a^{3}+b^{3}+c^{3}+d^{3}+ab+bc+cd+da+2ac+2bd\right). \)

Заметим, что

\(\displaystyle 32=\frac{(a+b+c+d)^{2}}{2} =ab+bc+cd+da+ac+bd+\frac{a^{2}+c^{2}}{2}+\frac{b^{2}+d^{2}}{2} \geqslant ab+bc+cd+da+2ac+2bd, \)

поэтому достаточно проверить, что

\(\displaystyle \left(a^{2}+b^{2}+c^{2}+d^{2}\right)^{2} \geqslant 4\left(a^{3}+b^{3}+c^{3}+d^{3}+32\right). \) \(\quad (\star)\)

Сделаем замену

\(\displaystyle a=2+x,\quad b=2+y,\quad c=2+z,\quad d=2+t. \)

Тогда

\(\displaystyle x+y+z+t = a+b+c+d-8 = 0, \)

\(\displaystyle a^{2}+b^{2}+c^{2}+d^{2} =4\cdot 2^{2}+2\cdot 2(x+y+z+t)+x^{2}+y^{2}+z^{2}+t^{2} =16+x^{2}+y^{2}+z^{2}+t^{2}, \)

\(\displaystyle a^{3}+b^{3}+c^{3}+d^{3} =4\cdot 2^{3}+3\cdot 2^{2}(x+y+z+t) +3\cdot 2\left(x^{2}+y^{2}+z^{2}+t^{2}\right) +x^{3}+y^{3}+z^{3}+t^{3}. \)

Неравенство \((\star)\) примет вид

\(\displaystyle \left(x^{2}+y^{2}+z^{2}+t^{2}+16\right)^{2} \geqslant 4\left(x^{3}+y^{3}+z^{3}+t^{3} +6\left(x^{2}+y^{2}+z^{2}+t^{2}\right)+64\right). \)

После раскрытия и сокращения остаётся доказать, что

\(\displaystyle \left(x^{2}+y^{2}+z^{2}+t^{2}\right)^{2} +8\left(x^{2}+y^{2}+z^{2}+t^{2}\right) \geqslant 4\left(x^{3}+y^{3}+z^{3}+t^{3}\right). \)

Остаётся заметить, что

\(\displaystyle \left(x^{2}+y^{2}+z^{2}+t^{2}\right)^{2} +8\left(x^{2}+y^{2}+z^{2}+t^{2}\right) \geqslant x^{4}+y^{4}+z^{4}+t^{4} +4x^{2}+4y^{2}+4z^{2}+4t^{2} \geqslant 4\left(x^{3}+y^{3}+z^{3}+t^{3}\right). \)

Первое неравенство получается раскрытием скобок: после сокращения в левой его части остаются лишь неотрицательные слагаемые. Второе получается сложением четырёх неравенств о средних вида \(p^{4}+4p^{2} \geqslant 4p^{3}\).