Тема . Иннополис (Innopolis Open)
Комбинаторика на Иннополисе
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела иннополис (innopolis open)
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#68881

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

PIC

Смежные круглосторонники - это круглосторонники, имеющие общую дугу окружности в качестве границы, причем дуга должна быть невырожденной, то есть не сводящейся к одной точке. Например, на рисунке выше смежными являются круглосторонники 1 и 2, 2 и 3, но не 1 и 3. Для какого наименьшего C ≥2023  можно нарисовать окружности так, что выполнены условия, перечисленные выше, и эти окружности образовывали ровно C  круглосторонников?

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

Источники: Иннополис-2023, 10-12 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 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 дугами.

Показать ответ и решение

Рассмотрим нарисованные окружности как плоский мультиграф (граф с кратными ребрами между вершинами): вершины – точки пересечений, ребра – дуги нарисованных окружностей, ограниченные точками пересечений. В такой интерпретации круглосторонники — это все грани этого графа, кроме «внешней» (т.е. части плоскости, лежащей вне всех окружностей).

Пусть нарисованы ровно m  окружностей. Согласно формуле Эйлера для плоских графов,

V − E +F = 2,

где V  — число вершин графа, E  — число ребер, а F  — – число граней (включая внешнюю).

Так как каждая пара окружностей пересекается ровно в двух своих уникальных точках, то число вершин

     m-(m-−-1)
V = 2⋅  2    = m(m− 1)

Так как каждая вершина – это точка пересечения ровно двух окружностей, то наш граф является регулярным степени 4  (то есть в каждую вершину входят ровно 4  ребра). Поскольку каждое ребро соединяет две вершины, общее число ребер

    4V
E = -2-= 2V = 2m(m− 1)

Следовательно число граней нашего плоского мультиграфа должно быть равно

F = 2+ E− V =2+ 2m(m − 1)− m(m − 1)= 2+ m(m − 1)

Значит, число круглосторонников

C =F − 1⇒ C =1+ m (m − 1)

Найти наименьшее m,  такое, что C ≥ 2023  — значит найти наименьшее натуральное решение неравенства

 2
m − m − 2022≥ 0

Решив, получаем, что наименьшее m  равно 46,  соответственно C =1 +46⋅45= 2071.

Теперь заметим, что для любого m ≥ 1  (в том числе для m = 46)  можно расположить m  окружностей на плоскости так, что каждая пара пересекается ровно в двух своих уникальных точках. Действительно, нарисуем произвольную окружность B  на плоскости и выберем произвольную точку O  внутри нее (но не являющуюся ее центром), а потом рассмотрим m  окружностей Bk,  где 0≤ k≤ (m− 1),  которые получаются в результате поворота окружности B  вокруг точки O  на угол 2πk
 m  (окружность B0  совпадает с B).  На рисунке приведен пример для m =4.

PIC

Теперь докажем, что обязательно найдется круглосторонник, ограниченный менее чем 4-мя  дугами. Предположим, что все круглосторонники ограничены не менее чем 4  дугами. Тогда общее число «сторон» (дуг, ограничивающих круглосторонники) не меньше, чем 4C = 4(1+ m(m − 1)).  Пусть K  — число границ внешней грани плоского мультиграфа, тогда

K + 4C = K +4+ 4m(m − 1)≤ 2m(m− 1)⇔ K +4 +2m (m − 2)≤ 0

Это невозможно, — следовательно, неверно предположение, что все круглосторонники ограничены не менее чем 4  дугами. Поэтому обязательно найдется круглосторонник, ограниченный менее чем 4  дугами, что и требовалось доказать.

Ответ: 2071

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!