|
|
 |
Условие
На плоскости даны две замкнутые ломаные $a,b$ (возможно, самопересекающиеся) и точки $K$, $L$, $M$, $N$. Вершины ломаных и эти точки находятся в общем положении (т.е. никакие три из них не лежат на прямой и никакие три отрезка, их соединяющие, не имеют общей внутренней точки). Каждый из отрезков $KL$ и $MN$ пересекает ломаную $a$ в четном количестве точек, а каждый из отрезков $LM$ и $NK$ – в нечетном. Ломаная $b$, наоборот, пересекает каждый из отрезков $KL$ и $MN$ в нечетном количестве точек, а каждый из отрезков $LM$ и $NK$ – в четном. Докажите, что ломаные $a$ и $b$ пересекаются.Решение 1
Так как вершины ломаной $a$ находятся в общем положении, то эта ломаная разбивает плоскость на части, которые можно раскрасить в черный и белый цвета правильно (т.е. так, что соседние области разноцветны). Пусть «внешняя» часть плоскости белая. Возьмем произвольную точку $O$ самопересечения ломаной $a$ и, отложив на ее звеньях, проходящих через $O$, отрезки $OA=OB=OC=OD=\varepsilon$, построим прямоугольник $ABCD$. При этом выберем $\varepsilon$ достаточно малым, чтобы все точки пересечения ломаной $a$ с $b$ и отрезками $KL$, $LM$, $MN$, $NK$ лежали вне этого прямоугольника. Если проделать эту операцию со всеми точками самопересечения и закрасить полученные прямоугольники белый цвет, то черная часть плоскости будет объединением нескольких непересекающихся многоугольников. Перекрасив теперь часть прямоугольников в черный цвет, соединим эти многоугольники в один многоугольник, границей которого будет несамопересекающаяся ломаная $a'$. Аналогично построим несамопересекающуюся ломаную $b'$. По построению ломаные $a'$, $b'$ будут пересекать друг друга и отрезки $KL$, $LM$, $MN$, $NK$ в тех же точках, что и ломаные $a$, $b$. Предположим, что $a'$ и $b'$ не пересекаются. Тогда они делят плоскость на три части и, следовательно, какие-то две из точек $K$, $L$, $M$, $N$ лежат в одной из этих частей. Но это невозможно, поскольку ломаная $a'$ отделяет точки $K$ и $L$ от точек $M$ и $N$, а ломаная $b'$ – точки $K$ и $N$ от точек $M$ и $L$. Значит, $a'$ и $b'$ пересекаются, а тогда пересекаются и исходные ломаные.Решение 2
Возьмем точку $C$ в общем положении с вершинами ломаных и точками $K$, $L$, $M$, $N$. Обозначим через $\gamma$ объединение отрезков $CK\cup CL\cup CM\cup CN$.
Как и в первом решении правильно раскрасим в черный и белый цвета части, на которые ломаная $a$ разбивает плоскость. Обозначим через $\alpha$ объединение черных частей. Аналогично построим двумерное множество $\beta$ по ломаной $b$.
Если ломаные $a$ и $b$ не пересекаются, то $a\cap\beta$ есть либо $a$, либо $\emptyset$, и $\alpha\cap b$ есть либо $b$, либо $\emptyset$. Тогда следующая цепочка сравнений по модулю 2 дает противоречие. $$0\underset{(1)}=|\partial(\gamma\cap\alpha\cap\beta)|\ \underset{(2)}= \ |\underbrace{\partial\gamma}_{=\{K,L,M,N\}} \cap\alpha\cap\beta|\ + \ |\gamma\cap \underbrace{\partial\alpha}_{=a}\cap\beta|\ + \ |\gamma\cap \alpha\cap \underbrace{\partial\beta}_{=b}|\ \underset{(3)}=1+0+0=1.$$ Здесь (1) выполнено, поскольку $\gamma\cap\alpha\cap\beta$ есть объединение конечного количества невырожденных незамкнутых ломаных, у которых четное число концов. Сравнение (2) доказывается несложно (это «формула Лейбница»).
Докажем сравнение (3). Имеем $$\{K,L,M,N\}\cap\alpha\cap\beta = \big(\{K,L,M,N\}\cap\alpha \big)\cap \big(\{K,L,M,N\}\cap\beta \big) = \{K,L\}\cap\{K,N\}=\{K\}.$$ Если $a\cap\beta=\emptyset$, то $\gamma\cap a\cap\beta=\emptyset$. Если же $a\cap\beta=a$, то $$|\gamma\cap a\cap\beta|=|\gamma\cap a|=|KN\cap a|+|LM\cap a|=1+1=0.$$ Итак, в обоих случаях $|\gamma\cap a\cap\beta|=0$. Аналогично $|\gamma\cap\alpha\cap b|=0$.
Замечания
1 «Программистское» пояснение нетривиальности и доказательство интуитивно очевидного утверждения о том, что если вершины ломаной $a$ находятся в общем положении, то эта ломаная разбивает плоскость на части, которые можно раскрасить в черный и белый цвета правильно (т.е. так, что соседние области разноцветны), приведено, например, в Алгебраическая топология с алгоритмической точки зрения (А. Скопенков), «Invariants of graph drawings in the plane», Arnold J. Math. (A. Skopenkov).
2. При помощи аналогичных соображений о трехкратных пересечениях доказывается, что кольца Борромео невозможно расцепить. См. простое изложение в Алгебраическая топология с алгоритмической точки зрения (А. Скопенков).
Аналогично доказывается многомерная версия утверждения задачи – лемма о кольцах Борромео (см. S. Avvakumov, I. Mabillard, A. Skopenkov and U. Wagner, «Eliminating Higher-Multiplicity Intersections», III. Codimension 2, Israel J. Math.)
Эта лемма играет важную роль при исследовании сложности реализуемости гиперграфов в многомерных пространствах (см. J. Matoušek, M. Tancer, U. Wagner., «Hardness of embedding simplicial complexes in $R^d$», J. Eur. Math. Soc. 13:2 (2011), 259-295 и A. Skopenkov, M. Tancer, «Hardness of almost embedding simplicial complexes in $R^d$», Discr. Comp. Geom. )
Источники и прецеденты использования
| олимпиада | |
| Название | Олимпиада по геометрии имени И.Ф. Шарыгина |
| год | |
| Год | 2019 |
| Заочный тур | |
| задача | |
| Номер | 23 [10-11 кл] |
