Отзывы пользователей

В некоторых клетках квадрата 20× 20 стоит стрелочка в одном из четырёх направлений ...

В некоторых клетках квадрата 20× 20 стоит стрелочка в одном из четырёх направлений. На границе квадрата все стрелочки смотрят вдоль границы по часовой стрелке (рис.). Кроме того, стрелочки в соседних (возможно, по диагонали) клетках не смотрят в противоположных направлениях. Докажите, что найдётся клетка, в которой стрелочки нет.



Решение

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


Без ограничения общности можем считать, что имеет место первый вариант. Но стрелки в первой и последней клетках этого пути смотрят в противоположные стороны. Значит, на этом пути есть и соседние клетки со стрелками, смотрящими в противоположные стороны, что противоречит условию.
Набросок доказательства леммы. Рассмотрим клетки, до которых можно дойти по чёрным клеткам от верхней стороны. Если образованная ими фигура касается нижней стороны, то существует чёрный путь, соединяющий верхнюю и нижнюю стороны. В противном случае вдоль нижней границы этой фигуры можно дойти от правой стороны до левой по белым клеткам (рис.).
Второе решение. Предположим, что клеток без стрелочек нет. Для замкнутого пути по клеткам квадрата определим индекс как число оборотов (по часовой стрелке), которые делает на нём стрелочка. Т.е. пройдём по этому пути, на каждом шаге прибавляя к числу (равному нулю в начале пути) 1/4 , если стрелочка повернулась по часовой стрелке, вычитая 1/4 , если против, и не меняя число, если направление стрелки не изменилось (Здесь мы пользуемся тем, что в соседних клетках стрелочки не смотрят в противоположных направлениях: если бы на каком-то шаге нашего пути стрелка поменяла направление на противоположное, неясно было бы, надо нам прибавлять 1/2 или вычитать.); индекс — это число, которое мы получим, сделав полный круг(Так как при этом мы возвращаемся в клетку, с которой начинали, вектор делает целое число оборотов, т.е. индекс — целое число.).





Индекс относительно пути вдоль границы квадрата равен  1 . Начнём теперь уменьшать наш путь — "откусим" сначала его левый верхний уголок (см. рис.). Заметим, что индекс при такой операции не меняется (так как среди стрелочек, выходящих из точек A , B , C и  D , нет противоположных). Откусывая так по углу, через некоторое время мы продеформируем наш путь до пути, состоящего из одной клетки — а индекс такого пути равен 0 . Противоречие.
Комментарии. 1. Второе решение доказывает и более общий факт. А именно, если в клетках какой то фигуры расставлены стрелочки так, что индекс относительно границы фигуры не равен  0 , то внутри фигуры обязательно есть пустая клетка. Более того, можно показать, что если индекс относительно границы равен k , то внутри есть хотя бы |k| пустых клеток.
2. Эта задача представляет собой дискретный аналог следующего известного топологического факта. Пусть на круге задано векторное поле — т.е. в каждой точке круга задан вектор, причём вектор зависит от точки непреры-вно. Тогда если на окружности эти вектора направлены по касательной (см. рис.), то внутри найдётся точка, вектор в которой равен нулю.1
Доказательство этого факта проходит в духе второго решения. А именно, определяется индекс векторного поля относительнокривой (Представляя себе векторное поле как отметки скорости ветра, можно сказать, что это число оборотов, которые сделает вокруг своей оси флюгер, если пронести его вдоль этого пути.) , проверяется, что для граничной окружности он равен 1, а для маленького контура вокруг точки с ненулевым вектором индекс равен 0 (рис.). После чего доказывается, что, если нулей у векторного поля нет, при уменьшении контура индекс не меняется.
Таким образом, имеет место теорема: если на границе некоторой области векторное поле имеет ненулевой индекс, то внутри области поле имеет хотя бы одну особую точку — точку, вектор в которой равен нулю.
Более подробно намеченное выше рассуждение изложено в пункте V.3.4 книги [1] (где оно применяется для доказательства замечательной теоремы Брауэра о существовании неподвижной точки непрерывного отображения диска в себя). А полное формальное доказательство можно узнать, прочитав книгу [2].
Более того. Определим индекс особой точки векторного поля как индекс относительно маленького пути вокруг этой точки. Тогда аналогичными рассуждениями можно показать, что индекс векторного поля относительно границы области равен сумме индексов особых точек внутри области (ср. с последним утверждением в комментарии 1). Дальнейшим развитием этого сюжета является знаменитая теорема Хопфа, связывающая эйлерову характеристику с суммой индексов особых точек.

[1] Р.Курант, Г.Роббинс. Что такое математика. МЦНМО, 2007.
[2] Н.Стинрод, У.Чинн. Первые понятия топологии. Мир, 1967.
 
Поделиться: