Формула Эйлера для графов и многогранников

Подсказка 1

Круглосторонники, окружности… Ну и ну. Хотя, вообще-то, вся это конструкция кое-что напоминает, если посмотреть на это под другим углом. У нас есть дуги, которые соединяют точки пересечения окружностей, у нас есть вот эти круглосторонники, которые отделены дугами , и внутри которых дуг нет. На что это похоже?

Подсказка 2

Верно, на плоский граф. Но, поскольку вершины этого графа, то есть точки пересечения пар окружностей, соединены дважды, то это плоский мультиграф. Интересно. А какую главную формулу мы знаем про плоские графы(и мультиграфы в том числе)?

Подсказка 3

Верно, формулу Эйлера для плоских графов. V - E + F = 2, где V - число вершин графа, E - число ребер, а F - число граней(здесь стоит сказать, что у нас вне этого плоского мультиграфа, тоже есть часть плоскости, которая отделена ребрами и внутри которой их нет - это часть плоскости вне графа, ее тоже стоит учитывать). Предположим, что окружностей у нас m, что тогда можно сказать про V? А как связать E и V?

Подсказка 4

Верно, так как окружностей m и каждая пара пересекается в двух точках, то всего точек пересечений, то есть вершин, 2*m(m-1)/2 = m(m-1)=V. Так как каждая вершина - точка пересечения ровно двух окружностей, то из нее исходит ровно 4 ребра. А значит E=4V/2=2V=2m(m-1). А значит F = 2 + E - V = m(m-1) + 2. Вспомним про рассуждения из предыдущего пункта, что число круглосторонников меньше числа граней на 1. Значит число круглосторонников равно m^2-m+1. Значит, нам надо решить неравенство m^2-m+1>=2023. Значит, m>=46. Но нужно привести пример. Подумайте как это можно сделать, использовав как-то правильный многоугольник и/или повороты на угол вокруг одной точки(что в общем-то, почти одно и тоже).

Подсказка 5

Теперь построим пример, для всех таких m от 1 до 46, когда никакие три окружности не пересекаются в одной точке. Возьмем окружность A_0 и точку О внутри нее, не совпадающую с ее центром. После чего построим, для всех i от 1 до m-1, окружности, которые получаются из А_0 поворотом на i*2pi/m против часовой стрелки, с центром в точке О. Почему этот пример подходит?

Подсказка 6

Верно, так как при такой картинке, «внешние» вершины соседних образуют правильный m-угольник, О - центр этого многоугольника. Тогда построим другую, неподходящую картинку, когда все окружности - есть описанные вокруг O и проходящие через свою сторону m - угольника. Тогда можно провести окружность(она не относится к нашим и нужна только для построения) с центром в точке О и посмотреть на пересечения этой окружностью серперов из точки О к сторонам нашего m-угольника. Тогда возьмем новые m штук окружностей, которые проходят через соответствующие стороны m-угольника и соответствующие точки пересечения серперов технической окружностью. Тогда, очевидно, они все перестанут пересекаться, так как мы на совсем чуть-чуть(пусть радиус технической окружности очень близок к нулю) сдвинули наши окружности(в силу непрерывности, доказали). Остался второй пункт задачи. Попробуйте доказать от противного.

Подсказка 7

Если предположить, что каждый круглосторонник ограничен как минимум 4 дугами, то общее число дуг, которые ограничивает круглосторонник не меньше чем 4*C=4(m^2-m+1). Пусть К - кол-во внешних граней мультиграфа, тогда K+4C<=E. Но тогда K+4+2m(m-1)<=0, что невозможно, так как K>=0, 4>0, 2m(m-1)>=0. Значит, предположение неверно, а значит, найдется круглосторонник, ограниченный не более чем 3 дугами.