То, что граница пройдет от одной стороны моста до другой и при этом не заблудится, следует из того, что она конечна, пересекает каждую сторону ровно в одной точке и "тупиков" в ней нет.
А вот что пути пешехода и лодки обязательно пересекутся... это действительно очевидно.
Интеграл голоморфной функции по
замкнутому контуру всегда равен нулюСамо по себе утверждение, вынесенное в эпиграф, в доказательстве не используется, а служит, скорее, руководящим и направляющим указанием.
Рассмотрим планарный граф, вершинами которого будут камни и центры шлюзов, причем для каждого мостика, соединяющего два камня и разделяющего два шлюза каждый из этих камней соединен ребром с каждым из этих шлюзов. Каждый берег считаем за один большой камень, а каждую половинку реки - за один большой шлюз. Весь граф умещается внутри большого квадрата и делит его на четырехугольные ячейки, каждая из которых соответствует ровно одному мосту.
Рассмотрим простые (без самопересечений) контуры этого графа. Если рассмотреть контур и траекторию лодки (или пешехода), то пересекаться они могут только в вершинах графа, причем их относительное поведение в вершине может быть трояким:
- либо траектория вошла в контур
- либо траектория вышла из контура
- либо траектория коснулась контура (изнутри или снаружи).
Пусть G - свободная неабелева группа с двумя образующими a и b. Каждому контуру сопоставим элемент группы следующим образом:
если траектории лодки и пешехода не пересекали контур (но могли касаться его), этому контуру соответствует единичный элемент e.
в противном случае обойдем контур против часовой стрелки и рассмотрим его вершины.
Если в очередной вершине:
- лодка вошла в контур, то этой вершине соответствует элемент a
- лодка вышла из контура, то этой вершине соответствует элемент a
-1- пешеход вошел в контур, то этой вершине соответствует элемент b
- пешеход вышел из контура, то этой вершине соответствует элемент b
-1Остальным вершинам соответствует элемент e, а контуру в целом - произведение элементов его вершин по порядку (напоминаю, что группа неабелева!).
По-хорошему, надо рассматривать контуры с отмеченной стартовой точкой, но из следующей теоремы видно, что это не обязательно.
ТеоремаЕсли траектории лодки и пешехода не пересекаются, то каждому простому контуру соответствует элемент e.Доказывать будем индукцией по площади контура.
Для элементарного контура, содержащего ровно один мост, возможны три ситуации.
Если ни одна из траекторий его не пересекла, ему соответствует элемент e;
Если по мосту прошел пешеход, то контуру соответствует элемент bb
-1 или b
-1b;
Если под мостом проплыла лодка, то контуру соответствует элемент aa
-1 или a
-1a.
Во всех случаях результат равен e.
Теперь рассмотрим контур, содержащий больше одного моста. Разделим область, которую он обходит, на две части, граница каждой из которых - простой контур. Пусть общая часть этих контуров - C: один маленький контур имеет вид AC, другой - C
-1B, а большой контур - AB. Тогда f(AB)=f(A)*f(B)=f(A)*f(C)*f(C
-1)*f(B)=f(AC)*f(C
-1B) (тут надо аккуратно рассмотреть поведение на концах разреза). По индукции получаем, что f(AB)=e.
А теперь предположим, что пешеход прошел, лодка проплыла, а траектории не пересеклись. Рассмотрим самый внешний контур графа (берег1 - река1 - берег2 - река2). Очевидно, что этому контуру соответствует элемент группы, равный aba
-1b
-1. А мы уже доказали, что это невозможно.
Для тех, кто не следил - здесь доказывалось, что если шахматную доску разрезать от края до края (по границам клеток), то она распадется хотя бы на две части.
(8 kombinacuj). Kakim obrazom tu y4ituvaaesh nali4ie perehodov megdy nedostigumuni kamniami?