Задача М1140‍‍

а) Пусть первоначально данные кривые делили плоскость на области $V_1$‍,‍ $V_2$‍,‍ $\ldots$‍,‍ $V_n$‍.‍ Каждая из новых, перестроенных кривых ограничивает область, состоящую из нескольких областей $V_i$‍.‍ Выберем те из новых кривых, внутри которых нет других новых кривых, и отметим внутри каждой из них одну из областей $V_i$‍‍ (рис. 5). Теперь сотрём эти кривые, среди оставшихся снова выберем «минимальные» (внутри которых нет других кривых) и отметим внутри каждой из них одну из областей $V_i$‍,‍ не отмеченных на первом шагу. (Очевидно, такие области найдутся.) Продолжая в том же духе, мы сопоставили каждой новой кривой область $V_i$‍‍ внутри неё, отмечаемую на соответствующем шаге, причём разным кривым будут сопоставлены разные области. Значит, число кривых не больше числа областей.

б) Раскрасим исходную картинку в шахматном порядке, т. е. так, чтобы внешняя область была белой и цвет области менялся при переходе через границу (рис. 6, а). (Существование такой раскраски легко доказать по индукции. При добавлении к уже раскрашенной картинке одной несамопересекающейся замкнутой кривой все попавшие внутрь неё области или отрезаемые этой кривой от старых областей части перекрашиваются в другой цвет; внешняя раскраска сохраняется. При этом шахматный порядок цветов не нарушится. А любую замкнутую кривую можно разбить на несамопересекающиеся замкнутые куски.)

Построим по «шахматной раскраске» граф (рис. 6, б), сопоставив каждой чёрной области по одной точке — это будут вершины графа, а каждой точке пересечения кривых — одно ребро: оно соединяет вершины, отвечающие чёрным областям, которые примыкают к этой точке.

Два способа перестройки изображаются на графе двумя операциями: стиранием ребра и стягиванием ребра в точку (рис. 7).

Ясно, что на графе исходной картинки можно стереть часть ребер так, что он превратится в «дерево», т. е. граф, не имеющий замкнутых цепочек рёбер. Оставшиеся рёбра можно последовательно стянуть в точку. Соответствующая последовательность перестроек приводит к одной чёрной области. Её граница и есть искомая кривая (рис. 8).

Интересно, что по графу можно восстановить соответствующий набор кривых. Подумайте, например, какие кривые отвечают графам, изображённым на рисунке 9.

в) Каждая перестройка превращает набор ориентированных кривых снова в набор ориентированных кривых. Предположим, что существует последовательность перестроек, результатом которой будет единственная кривая. Тогда перед выполнением последней перестройки мы располагаем набором ориентированных кривых с единственной точкой пересечения. Такой набор может состоять из единственной кривой — «восьмёрки», изображённой на рисунке 10. Однако её перестройка приводит к двум, а не к одной кривой.