|
|
 |
Условие
В некоторых клетках квадрата 20×20 стоит стрелочка в одном из четырёх направлений. На границе квадрата все стрелочки смотрят вдоль границы по часовой стрелке (см. рис.). Кроме того, стрелочки в соседних (возможно, по диагонали) клетках не смотрят в противоположных направлениях. Докажите, что найдётся клетка, в которой стрелочки нет.
Решение
Предположим, что клеток без стрелочек нет.
Первый способ. Покрасим все клетки с горизонтальным стрелочками в чёрный цвет, а все клетки с вертикальными стрелочками – в белый.
Лемма. Либо хромая ладья (которая каждый раз сдвигается на одну клетку по вертикали или горизонтали) может пройти по чёрным клеткам с нижнего края на верхний, либо король может пройти по белым клеткам с левого края на правый.
Доказательство. Пусть ладья снизу доверху пройти не может. Увеличим доску: добавим справа и слева по белой вертикали, а потом снизу – чёрную горизонталь (при этом возможности короля и ладьи не изменятся). Отметим все чёрные клетки, до которых ладья доходит снизу. Закрасим все отрезки, отделяющие отмеченные поля от белых. Легко проверить, что из каждого узла в середине доски выходит чётное число закрашенных отрезков. Нечётный узел может быть только на краю. На нижнем краю их нет по построению, на верхнем – поскольку ладья до верха не доходит. Остаются только левый и правый края, и там есть ровно два узла на высоте 1. Значит, выйдя из одного и идя по окрашенным отрезкам без повторений, мы придём в другой. Заметим теперь, что к каждому отрезку примыкает по белой клетке, и клетки для двух соседних отрезков имеют общую вершину (в частности, могут совпасть), поэтому король по ним доберется от левого края до правого.
Рассмотрим путь (ладьи или короля) который существует согласно лемме. Стрелки в первой и последней клетках этого пути смотрят в противоположные стороны. Значит, на этом пути есть и соседние клетки со стрелками, смотрящими в противоположные стороны, что противоречит условию.
Второй способ. Для замкнутого пути по клеткам квадрата определим индекс как число оборотов (по часовой стрелке), которые делает на нём стрелочка. То есть пройдём по этому пути, на каждом шаге прибавляя к числу (равному нулю в начале пути) ¼, если стрелочка повернулась по часовой стрелке, вычитая ¼, если против, и не меняя число, если направление стрелки не изменилось (здесь мы пользуемся тем, что в соседних клетках стрелочки не смотрят в противоположных направлениях: если бы на каком-то шаге нашего пути стрелка поменяла направление на противоположное, неясно было бы, надо нам прибавлять ½ или вычитать); индекс – это число, которое мы получим, сделав полный круг. (Так как при этом мы возвращаемся в клетку, с которой начинали, стрелочка делает целое число оборотов, то есть индекс – целое число.)
Индекс относительно пути вдоль границы квадрата равен 1. Начнём теперь уменьшать наш путь – "откусим" сначала его левый верхний уголок (см. рис.).
Замечания
1. Второй способ доказывает и более общий факт. А именно, если в клетках какой то фигуры расставлены стрелочки так, что индекс относительно границы фигуры не равен 0, то внутри фигуры обязательно есть пустая клетка. Более того, можно показать, что если индекс относительно границы равен k, то внутри есть хотя бы |k| пустых клеток.
2. Эта задача представляет собой дискретный аналог следующего известного топологического факта. Пусть на круге задано векторное поле – то есть в каждой точке круга задан вектор, причём вектор зависит от точки непрерывно. Тогда если на окружности эти вектора направлены по касательной, то внутри найдётся точка, вектор в которой равен нулю. Подробности можно найти в книгах Р. Курант, Г.Роббинс. "Что такое математика". МЦНМО, 2007 (п. V.3.4) и Н.Стинрод, У.Чинн. "Первые понятия топологии". Мир, 1967.
