Неподвижные точки и лемма Шпернера

Неподвижные точки и лемма Шпернера

Введение Лемма Шпернера Почти неподвижные точки Задачи для самостоятельного решения Решения задач

Введение

Когда мы хотим решить какое-нибудь уравнение, нам важно заранее знать, имеет ли оно корни. Это особенно существенно, когда речь идет о сложных уравнениях или системах уравнений и их решений на современных ЭВМ. Наличие корней уравнений обычно гарантируется так называемыми теоремами существования. Вот одна из простейших теорем такого типа: если непрерывная функция f задана на отрезке [0,1] и принимает на его концах значения разных знаков, то уравнение

f(x) = 0 (1)

имеет на этом отрезке по крайней мере один корень. (Мы не даем здесь точного определения непрерывности функции, для наших целей достаточно знать, что непрерывная функция принимает близкие значения в близких точках.)

Часто теоремы существования выражаются в виде принципов неподвижной точки. Например, уравнение (1) можно преобразовать так: lf(x)+x = x, где l - некоторый параметр. Введя обозначение lf(x)+x = F(x), приходим к уравнению

F(x) = x. (2)

Выберем параметр l так, чтобы все значения функции F лежали на отрезке [0,1]. Тогда каждая точка x этого отрезка при помощи функции, или, как говорят, отображения F переводится в какую-то точку F(x) = y этого же отрезка, вообще говоря, отличную от x. Но если точка x0 является корнем уравнения (2), то она никуда не перемещается, остается неподвижной. Эта же точка x0 служит корнем уравнения (1). Таким образом, на геометрическом языке теорема о разрешимости уравнения (2), а значит и уравнения (1), формулируется в виде следующего принципа неподвижной точки: всякое непрерывное отображение отрезка в себе имеет неподвижную точку.

Аналогично, если непрерывные функции f и g от двух переменных заданы на квадрате [0,1]´[0,1] и удовлетворяют там неравенствам 0 £ f(x,y) £ 1, 0 £ g(x,y) £ 1, то система уравнений

ì í î

f(x,y) = x, g(x,y) = y.

имеет хотя бы одно решение (x0,y0), потому что верна следующая теорема: всякое непрерывное отображение квадрата в себя имеет неподвижную точку.

Принципы неподвижной точки имеют многочисленные применения в математике: к ним сводятся теоремы существования решений дифференциальных, интегральных, операторных и других уравнение, они используются в новых прикладных разделах математики - математической экономике, теории игр.

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

Лемма Шпернера

Рассмотрим произвольный треугольник T, разбитый на малые треугольники. Мы всегда будем предполагать, что это разбиение удовлетворяет следующим условиям: любые два малых треугольника либо совсем не имеют общих точек, либо имеют только общую вершину или общую сторону.

Такое разбиение исходного треугольника называется триангуляцией, малые треугольники называются гранями триангуляции, стороны малых треугольников - ее ребрами, а их вершины - ее вершинами.

Следующее предложение опубликовано Э. Шпернером (1905-1980) в статье 1928 года, посвященной размерности евклидова пространства.

Лемма (Шпернер). Пусть имеется триангуляция треугольника T. Вершины самого треугольника отмечены числами 1, 2 и 3 соответственно. Все вершины триангуляции отмечены этими же числами с соблюдением следующего граничного условия: если такая вершина лежит на стороне треугольника T, то она получает в качестве отметки одно из тех двух чисел, которые соответствуют концам этой стороны. Тогда имеется хотя бы одна грань с тремя разными отметками вершин (назовем ее хорошей гранью). Более того, имеется нечетное число хороших граней.

Для определенности дальше всюду предполагается, что левая нижняя вершина треугольника T несет отметку 1, правая нижняя - 2 и верхняя - 3.

Доказательство леммы проводится методом прогулок по граням триангуляции. Прогулки будут выполняться с соблюдением следующих правил. Мы начинаем движение либо извне треугольника внутрь через граничное ребро с отметками 1 и 2 (короче, ребро (1,2)), либо из хорошей грани через ее ребро (1,2). Переход из одной грани в соседнюю разрешается только через их общее ребро (1,2), а выход из треугольника T наружу - только через граничное ребро (1,2). Каждая прогулка (или путь) заканчивается в одном из двух случаев: когда мы выходим из T наружу или когда попадаем в хорошую грань. Эти правила однозначно определяют каждый путь благодаря следующему простому наблюдению: если две вершины одной грани отмечены числами 1 и 2, то эта грань либо является хорошей, либо имеет в точности два ребра (1,2).

Итак, возможны пути трех типов: 1) от граничного ребра (1,2) к хорошей грани (или в обратном направлении, что несущественно), 2) от граничного ребра (1,2) к другому такому же ребру, 3) от хорошей грани к другой такой же грани. На рисунке показано по одному пути каждого из этих типов.

Обозначим через a, b, g общее число путей первого, второго и третьего типа, соответственно. Тогда число граничных ребер (1,2) равно a+2b, а число хороших граней a+2g. По условию граничные ребра (1,2) встречаются только на стороне треугольника T c отметками 1 и 2, и их число нечетно. (Последнее утверждение можно назвать одномерной леммой Шпернера, а его доказательство легко проведет сам читатель.) Значит, нечетным является число a и поэтому также число a+2g, что и требовалось.

Приведенное доказательство допускает следующее наглядное описание. Назовем треугольник T домом, грани его триангуляции - комнатами, а ребра типа (1,2) - дверями. Тогда каждая комната имеет 0, или 1, или 2 двери. Комната с двумя дверями называется проходной, а с одной дверью - тупиком. Тупик есть не что иное как хорошая грань. Дверь, лежащую на границе, назовем наружной. Лемма Шпернера получает теперь следующую формулировку.

Если каждая комната имеет 0, или 1, или 2 двери, то число тупиков и число наружных дверей имеют одинаковую четность, т. е. оба они либо четны, либо нечетны.

Фактически это утверждение сильнее леммы Шпернера, так как оно справедливо при любом распределении отметок 1, 2 и 3 на границе треугольника. Кроме того, дом и его комнаты могут быть не только треугольными, но и, например, квадратными.

Нам потребуется еще так называемый ориентированный вариант леммы Шпернера. Для его формулировки будем предполагать треугольник T ориентированным. Это значит, что на его границе выбрано направление ее обхода, называемое положительным. Для определенности пусть это будет обход границы против часовой стрелки. Граничное ребро (1,2) назовем положительным (или (+) - ребром), если движение по нему от отметки 1 к отметки 2 совершается в положительном направлении, и назовем отрицательным (или(-) - ребром) в противном случае. Аналогично, хорошую грань будем называть (+) - гранью, если обход ее границы от отметки 1 к отметке 2, затем от 2 к 3 и от 3 к 1 совершается против часовой стрелки, и (-) - гранью в противном случае.

Ориентированные варианты одномерной и основной (двумерной) лемм Шпернера звучат так.

Если условия основной леммы Шпернера выполнены, то

1) число (+) - ребер на единицу больше числа (-) - ребер,

2) число (+) - граней на единицу больше числа (-) - граней;

следовательно, имеется хотя бы одна (+) - грань.

Первый из них докажите сами. Для доказательства второго заметим, что каждый описанный выше путь первого типа связывает (+) - ребро с (+) - гранью или (-) - ребро с (-) - гранью, путь второго типа связывает (+) - ребро с (-) - ребром, и путь третьего типа связывает (+) - грань с (-) - гранью. Введем обозначения:

a - число (+) - ребер, каждое из которых соединено путем с (-) - ребром,

b - число (+) - ребер, соединенных с (+) - гранями,

c - число (-) - ребер, соединенных с (-) - гранями,

d - число (+) - граней, соединенных с (-) - гранями.

Согласно одномерной лемме имеем (a+b)-(a+c)= b-c= 1. Отсюда получаем (b+d)-(c+d)= b-c= 1, что и требовалось. Последнее доказательство проиллюстрируйте чертежом.

Почти неподвижные точки

Теорема о неподвижной точке была сформулирована для отрезка и для квадрата. Она одинаково верна для круга и всякого выпуклого многоугольника. Мы ограничимся тем, что докажем дискретный вариант этой теоремы для треугольника. Для определенности рассмотрим правильный треугольник T с триангуляцией, полученной следующим образом: каждая сторона треугольника делится на m равных частей, где m ³ 2 - любое фиксированной натуральной число, и через точки деления проводятся прямые, параллельные его сторонам (см. рисунок ниже, m = 5).

Мы скажем, что вершины этой триангуляции образуют остов треугольника. Пусть задано какое-то отображение f остова в себя. Это значит, что имеется правило, по которому каждой точке остова сопоставляется некоторая (другая или та же самая) точка остова, называемая образом первой. Говорят еще, что при отображении точка переходит в свой образ. Произвольно взятое отображение остова может совсем не иметь неподвижных точек. Мы наложим на него требование, напоминающее непрерывность: заставим близкие точки переходить в близкие. Более точно, предположим, что каждые две вершины каждой грани переходят в две вершина некоторой (вообще говоря, другой) грани или же склеиваются, т. е. переходят в одну точку. Такое отображение назовем почти непрерывным. Оказывается, и для такого отображения существование неподвижной точки не гарантируется (приведите пример). Но если ее нет, то обязательно найдется грань, все вершины которой перейдут в вершину этой же самой или соседней грани (две грани считаются соседними, если они имеют общее ребро). Такие вершины можно назвать почти неподвижными, ибо они смещаются мало - не более чем на удвоенную высоту грани. Итак, имеем следующую теорему.

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

Конечно, эти два случая не являются взаимно исключающими друг друга.

Доказательство. Напомним, что под расстоянием между точкой и отрезком понимается длина перпендикуляра, опущенного из точки на отрезок или на его продолжение.

Предположим, что ни одна точка остова не остается неподвижной: пусть все они смещаются. При движении точек их расстояния от сторон треугольника T = A1A2A3 меняются. Для каждой точки найдется одна или две (но не три!) стороны, к которым эта точка приближается, т. е. соответствующие расстояния строго уменьшаются. В соответствиии с этим мы выберем числовые отметки у точек остова. Если точка приближается сразу к двум сторонам, например, к A1A2 и A2A3, то мы даем ей одну из отметок 3 и 1, безразлично какую, если же - только к одной стороне, например, к A1A3, то отмечаем ее числом 2. Согласно этому правилу вершина A1 большого треугольника получает отметку 1, вершина A2 отметку 2 и вершина A3 отметку 3. Поэтому же каждая точка на стороне A1A2 отмечается числом 1 или числом 2; аналогично для двух других сторон.

Полученная система отметок удовлетворяет условиям леммы Шпернера. Согласно ее ориентированному варианту имеется грань F с отметками (1,2,3), идущими против часовой стрелки. Покажем, что вершины этой грани почти неподвижны. Для этого следует рассмотреть различные случаи расположения грани F и отметок у ее вершин. Два из этих случаев мы разберем подробно, а разбор остальных предоставляем читателю.

Первый случай: грань F не является угловой в треугольнике T и отметку 1 несет ее нижняя вершина.

Значит, вершина 1 при отображении приближается к стороне A2A3. Поэтому ее образ F (1) должен лежать на отрезке B1B2, проведенном через вершину 2 параллельно стороне A2A3, или правее отрезка B1B2. Аналогично, образ f(2) вершины 2 лежит на отрезке C1C2, проведенном через вершину 3 параллельно стороне A1A3, или левее отрезка C1C2. Наконец, образ вершины 3 лежит на отрезке D1D2 или ниже его. Мы видим, что образы вершин грани F должны лежать вне или на границе треугольника, полученного пересечением отрезков B1B2, C1C2 и D1D2. На самом деле благодаря почти непрерывности отображения свобода их передвижения еще более ограничена. Действительно, пусть d обозначает длину ребра каждой грани. Тогда расстояние между образами f(2) и f(3) точек 2 и 3 должно быть не больше, чем d. Поэтому если бы точка f(3) лежала строго ниже отрезка D1D2 ,то точка f(2) совпадала бы с точкой E - точкой пересечения отрезков C1C2 и D1D2. Но тогда расстояние между точками f(2) и f(1) было бы не меньше, чем удвоенная высота грани, т. е. dÖ3, что невозможно. Далее, если точка f(3) лежит на отрезке D1D2 и, например, f(3) = E, то расстояние между f(1) и f(2) будет не меньше, чем dÖ3. Итак, мы имеем f(3) = 1. Аналогично, f(1) = 2 и f(2) = 3.

Второй случай: грань F является угловой в треугольнике T. Тогда отметки ее вершин определены однозначно.

Как и раньше, строим треугольник A1B1B2, ограничивающий положения точек f(1), f(2) и f(3). Рассуждения, аналогичные приведенным выше, показывают, что точки 2 и 3 при отображении меняются местами: f(2) = 3, f(3) = 2, а точка 1 ( = A1) переходит в одну из трех точек: 2, 3 и E. Следовательно, либо множество вершин грани F переходит в себя, причем две из них склеиваются, либо это множество отображается на вершины соседней грани.

Вообще, возможны следующие случая расположения грани F и отметок ее вершин:

1. Грань имеет одну вершину внизу и две вверху, и отметку 1 несет ее левая или нижняя вершина (случай, частично рассмотренный выше). При этом три вершины грани циклически переходят одна в другую: 1® 2® 3® 1 или 1® 3® 2® 1.

Случай, когда грань расположена так же, но отметку 1 имеет ее правая вершина, невозможен (объясните, почему).

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

Случай такого же расположения грани, но с отметкой 1 у верхней или правой вершины - невозможен (объясните, почему).

3. Случай угловой грани уже рассмотрен.

После проверки всех этих случаев теорема о почти неподвижных точках доказана. Заметим, что если бы мы не учитывали ориентированный вариант леммы Шпернера, число случаев было бы больше.

Доказанную теорему можно считать шагом к доказательству существования неподвижной точки у любого непрерывного отображения треугольника в себя. Для дальнейшего продвижения применяется такая схема. Берут все более и более мелкие триангуляции и для каждой из них находят почти неподвижные точки. Когда число d стремится к нулю, почти неподвижные точки в пределе переходят в неподвижную.

Задачи для самостоятельного решения

1. Даже к простейшему уравнению x-1 = 0 теорема о неподвижной точке не может быть применена непосредственно. Поэтому преобразуем его к виду l(x-1)+x = x. Найдите все значения параметра l, при которых применение теоремы возможно на отрезке [0,2]. Решение

2. Каждая вершина триангуляции треугольника отмечена одним из четырех чисел 1, 2, 3 и 4 так, что для каждой отметки имеется сторона треугольника (включая ее концы), свободная от этой отметки. Имеются ли грани с тремя разными отметками? Можно ли что-нибудь сказать о четности их числа? Решение

3. Пусть P - выпуклый многогранник в пространстве, у которого все грани - треугольники (например, тетраэдр, октаэдр, икосаэдр). Пусть каждой вершине P отнесено одно из чисел 1, 2 и 3. Можно ли что-нибудь сказать о четности числа граней, у которых все вершины имеют разные отметки? Решение

4. Пусть Q - выпуклый многогранник, у которого в каждой вершине сходятся три грани (например, тетраэдр, куб, додекаэдр). Каждая грань Q помечена одним из чисел 1, 2 и 3. Можно ли что-нибудь сказать о четности числа вершин Q, в которых сходятся три грани с разными отметками? Решение

5. Ребра (но не вершины!) триангуляции треугольника отмечены числами 1, 2 и 3 так, что ребра, лежащие на одной его стороне, имеют одинаковые отметки, а лежащие на разных сторонах - разные. Кроме того, каждая вершина триангуляции имеет такое свойство: все выходящие из нее ребра несут не больше двух разных отметок. Имеются ли грани, у которых отметки всех трех ребер различны? Если да, что можно сказать о четности их числа? Решение

6. Квадрат Q разбит на малые квадраты с помощью прямых, параллельных его сторонам. Вершины квадрата отмечены числами 1, 2, 3 и 4. Вершины малых квадратов отмечаются этими же числами с условием: если вершина малого квадрата лежит на стороне Q, то она получает одну из отметок, отнесенных к концам этой стороны. Имеются ли малые квадраты с четырьмя разными отметками? А теперь разделим каждый малый квадрат на два треугольника и получим триангуляцию Q. Имеются ли хорошие грани триангуляции и что можно сказать о четности их числа? Теперь хорошие грани могут быть четырех типов: (1,2,3), (1,2,4),(1,3,4), (2,3,4). Решение

7. Пятиугольник (например, выпуклый) триангулирован, и все вершины триангуляции отмечены числами 1, 2, 3, 4 и 5 так, что все вершины самого пятиугольника получают разные отметки, и если вершина триангуляции лежит на стороне с отметками 1 и 2, то она получает одну из этих отметок; аналогично для других сторон. Назовем грань хорошей, если она имеет три разные отметки. Теперь имеется десять типов хороших граней: (1,2,3), (1,2,4),...,(3,4,5). Докажите, что общее число всех хороших граней нечетно. Решение

8. К остову треугольника (рис. 0.2) применяется одно из следующих отображений: 1) каждый угол треугольника, состоящий из четырех граней, загибается внутрь, 2) весь треугольник поворачивается вокруг центра на угол 120° против часовой стрелки. В каждом из этих случаев найдите неподвижные и почти неподвижнеы точки. Решение

Решения задач

1. Ответ: -2 £ l < 0.

2. Очевидно, вершины заданного треугольника несут разные отметки; пусть это будут 1, 2 и 3. Строим новую систему отметок следующим образом. Если у какой-то вершины триангуляции отметка отлична от 4, то сохраняем ее; если же она равна 4, то заменяем ее по такому правилу: пусть у нас свободна от отметки 4, например, сторона (1,3), тогда заменяем отметку 4 на 2, т. е. на ту, которую имеет вершина, противоположная стороне (1,3). Новая система удовлетворяет условиям леммы Шпернера. Поэтому существует грань (1,2,3). При обратном переходе грани с тремя разными отметками не исчезают, но могут появиться новые. О четности их числа ничего сказать нельзя: могут быть разные случаи.

3. Число таких граней четно (возмлжно, равно нулю). Действительно, пусть имеется одна грань (1,2,3). Выбрасывая ее из поверхности многогранника и применяя к оставшейся части рассуждения, в точности повторяющие доказательство леммы Шпернера, найдем еще нечетное число таких граней.

4. Число таких вершин четно (возможно, равно нулю). Для доказательства применяем метод прогулок, но не по граням, а по ребрам многогранника. Назовем комнатой его вершину, а дверью - ребро, примыкающее к граням с отметками 1 и 2. Тупик есть вершина, в которой сходятся три грани с разными отметками. Каждый путь ведет из тупика в тупик, поэтому число тупиков четно.

5. Да, и притом их число нечетно. Для доказательства используется следующий вариант метода прогулок по граням триангуляции. Вход в треугольник извне и переход из одной грани в другую разрешается только через вершины триангуляции, и притом такие, в которых сходятся ребра только с отметками 1 и 2. Тупиками являются грани с тремя разными отметками на ребрах. Из условия задачи следует, что к каждой вершине триангуляции (кроме одной) примыкает четное число граней, по которым могут проходить пути (для некоторых вершин это число граней может быть равным нулю). Исключение составляет вершина большего треугольника, отделяющая его сторону с отметками 1 от стороны с отметками 2. Через одну и ту же вершину триангуляции могут проходить несколько путей. Но благодаря указанному условию четности, их можно выбрать так, чтобы каждый из них проходил по своим граням, не мешая другим путям. Этим устанавливается взаимно однозначное соответствие между потями и парами тупиков. Кроме того, имеется один путь извне через вершину большого треугольника в тупик. Отсюда получается нужное утверждение.

6. Назовем ребро (1, 2) дверью. Метод прогулок дает нечетное число граней типов (1, 2, 3) и (1,2,4). Если дверь есть ребро (3,4), то получаем нечетное число граней типов (1,3,4) и (2,3,4). Итак, число хороших граней четно и отлично от нулю.

7. Пусть N - общее число всех хороших граней. Применяя метод прогулок и называя дверью ребро (1,2), проверим, что сумма

(123)+(124)+(124) (3)

нечетна. Здесь (123) обозначает число граней типа (1,2,3). О сумме (3) скажем, что она соответствует стороне (1,2) пятиугольника. Аналогичные суммы составляем для всех сторон, и все они нечетны. Если назвать дверью ребро (1,3), то метод прогулок показывает, что сумма (123)+(134)+(135) четна. Скажем, что она соответствует диагонали пятиугольника. И так - для всех диагоналей. Складывая десять сумм, соответтсвующих всем сторонам и всем диагоналям, получим нечетное число, равное, как легко видеть, 3N. Отсюда N нечетно;

8. Не дается.