Принцип крайнего, индукция и другие методы в комбигео
Ошибка.
Попробуйте повторить позже
В общем случае лемма касается триангуляции 
-мерного симплекса
Рассмотрим его триангуляцию 
, являющуюся разбиением 
на меньшие 
-мерные симплексы. Обозначим функцию цвета вершины
как
где 
обозначает множество вершин триангуляции 
. Раскраска называется Шпернеровской, если выполнены следующие
правила:
- 1.
-
Вершины большого симплекса покрашены в разные цвета, то есть:
для 
.
- 2.
-
Те вершины
, что лежат в одной 
-мерной грани большого симплекса
покрашены в цвета образующих её вершин
Докажите, что при любой Шпернеровской раскраске вершин в триангуляции 
-мерного симплекса найдётся ячейка триангуляции,
вершины которой покрашены во все цвета.
Усилим утверждение, найдется нечетное число таких ячеек.
База индукции: Для 
оно очевидно, ведь симплекс это просто отрезок с разноцветными концами и, если на нем отметить точки
двух цветов, то найдется нечетное число отрезков с разноцветными концами.
Индукционный переход: Предположим, что лемма верна для всех симплексов размерности 
Докажем её для 
-мерного
симплекса 
.png)
Построим граф 
- Вершины графа
-мерные симплексы триангуляции 
и внешняя область.
- Ребра
соединяют две вершины, если соответствующие им симплексы имеют общую 
-мерную грань, вершины
которой раскрашены в цвета 
- На внешней грани симплекса
содержащей вершины 
по индукционному предположению существует нечётное
число 
-мерных симплексов с вершинами цветов 
Следовательно, степень вершины, соответствующей
внешней области, нечётна.
- В графе
число вершин с нечётной степенью чётно. Так как внешняя область имеет нечётную степень, существует нечётное
число внутренних 
-мерных симплексов с нечётной степенью.
- У симплекса нечетной степени есть грань с вершинами цветов
Если оставшаяся вершина не цвета 
то его
степень равна двум, противоречие, значит, все его вершины разноцветны.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
