На плоскости нарисовано несколько окружностей, причём каждая пара окружностей пресекается ровно в двух точках, и никакие три окружности не имеют общей точки. \(\textit{Круглосторонник}\) \(-\) это часть плоскости, со всех сторон ограниченная дугами этих окружностей, граница которой состоит из каких-то дуг этих окружностей, причём между любыми двумя внутренними точками круглосторонника можно пройти, не пересекая ни одной дуги данных окружностей.
\(\textit{Например, на рисунке ниже изображены две окружности, образующие 3 круглосторонника, обозначенные номерами 1, 2, и 3.}\)

Смежные круглосторонники \(-\) это круглосторонники, имеющие общую дугу окружности в качестве границы, причём дуга должна быть невырожденной, то есть не сводящейся к одной точке.
\(\textit{Например, на рисунке ниже смежными являются круглосторонники 1 и 2, 2 и 3, но не 1 и 3}\).

Для какого наименьшего \(С \geqslant 2023\) можно нарисовать окружности так, что выполнены условия, перечисленные выше, и эти окружности образовывали ровно \(C\) круглосторонников?
Докажите, что для любого расположения нарисованных окружностей на плоскости, удовлетворяющих перечисленным условиям и образующих не менее 2023 круглосторонников, обязательно найдётся круглосторонник, ограниченный менее чем 4-мя дугами.

Решение

Рассмотрим нарисованные окружности, как плоский \( \href{https://examp.info/onedef/grafy/}{\text{мультиграф}}\): вершины \(-\) точки пересечений, ребра \(-\) дуги нарисованных окружностей, ограниченные точками пересечений. В такой интерпретации круглосторонники \(-\) это все грани этого графа, кроме «внешней» (т.е. части плоскости, лежащей вне всех окружностей).
Пусть нарисованы ровно \(m\) окружностей. Согласно \( \href{https://examp.info/onedef/formula-ejlera-dlya-mnogogrannikov/}{\text{формуле Эйлера}} \) для плоских графов, \[
V - E + F = 2,
\] где \(V -\) число вершин графа, \(E -\) число ребер, а \(F -\) число граней (включая внешнюю).
Так как каждая вершина - это точка пересечения ровно двух окружностей, то наш граф является \(\href{https://examp.info/onedef/grafy/}{\text{регулярным}}\) степени 4 (то есть в каждую вершину входят ровно 4 ребра). Поскольку каждое ребро соединяет две вершины, общее ребер \[
F = 2 + E - V = 2 + 2m(m - 1) - m(m - 1) = 2 + m(m - 1)
\] Значит, число круглосторонников \[
C = F - 1 \Rightarrow C = 1 + m(m - 1)
\]
Найти наименьшее \(m\) такое, что \(C \geqslant 2023 -\) значит найти наименьшее натуральное решение неравенства
\[
m^2 - m - 2022 \geqslant 0
\] Решив, получаем, что наименьшее \(m\) равно 46, соответственно \(C = 1 + 46 \cdot 45 = 2071.\) Теперь заметим, что для любого \(m \geqslant 1\) (в том числе для \(m = 46\)) можно расположить \(m\) окружностей на плоскости так, что каждая пара пересекается ровно в двух своих уникальных точках. Действительно, нарисуем произвольную окружность \(B\) на плоскости и выберем произвольную точку \(O\) внутри нее (но не являющуюся ее центром), а потом рассмотрим \(m\) окружностей \(B_k\), где \(0 \leqslant k \leqslant m - 1\), которые получаются в результате поворота окружности \(B\) вокруг точки \(O\) на угол \(\frac{2 \pi k}{m}\) (окружность \(B_0\) совпадает с \(B\)). На рисунке приведен пример для \(m = 4\).
Теперь докажем, что обязательно найдется круглосторонник, ограниченный менее чем 4-мя дугами. Предположим, что все круглосторонники ограничены не менее, чем 4-мя дугами. Тогда общее число «сторон» (дуг, ограничивающих круглосторонники) не меньше, чем \(4C = 4(1 + m(m - 1))\). Пусть \(K -\) число границ внешней грани плоского мультиграфа, тогда \[
K + 4C = K + 4 + 4m(m - 1) \leqslant 2m(m - 1) \Leftrightarrow K + 4 + 2m(m - 2) \leqslant 0
\] Это невозможно, следовательно, неверно предположение, что все круглосторонники ограничены не менее, чем 4 дугами. Поэтому обязательно найдется круглосторонник, ограниченный менее, чем 4 дугами, что и требовалось доказать.