Олимпиадная задача по теории графов: докажите отсутствие стрелочки в клетке квадрата 20×20

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

  Доказательство. Пусть ладья снизу доверху пройти не может. Увеличим доску: добавим справа и слева по белой вертикали, а потом снизу – чёрную горизонталь (при этом возможности короля и ладьи не изменятся). Отметим все чёрные клетки, до которых ладья доходит снизу. Закрасим все отрезки, отделяющие отмеченные поля от белых. Легко проверить, что из каждого узла в середине доски выходит чётное число закрашенных отрезков. Нечётный узел может быть только на краю. На нижнем краю их нет по построению, на верхнем – поскольку ладья до верха не доходит. Остаются только левый и правый края, и там есть ровно два узла на высоте 1. Значит, выйдя из одного и идя по окрашенным отрезкам без повторений, мы придём в другой. Заметим теперь, что к каждому отрезку примыкает по белой клетке, и клетки для двух соседних отрезков имеют общую вершину (в частности, могут совпасть), поэтому король по ним доберется от левого края до правого.   Рассмотрим путь (ладьи или короля) который существует согласно лемме. Стрелки в первой и последней клетках этого пути смотрят в противоположные стороны. Значит, на этом пути есть и соседние клетки со стрелками, смотрящими в противоположные стороны, что противоречит условию.   Второй способ. Для замкнутого пути по клеткам квадрата определим индекс как число оборотов (по часовой стрелке), которые делает на нём стрелочка. То есть пройдём по этому пути, на каждом шаге прибавляя к числу (равному нулю в начале пути) ¼, если стрелочка повернулась по часовой стрелке, вычитая ¼, если против, и не меняя число, если направление стрелки не изменилось (здесь мы пользуемся тем, что в соседних клетках стрелочки не смотрят в противоположных направлениях: если бы на каком-то шаге нашего пути стрелка поменяла направление на противоположное, неясно было бы, надо нам прибавлять ½ или вычитать); индекс – это число, которое мы получим, сделав полный круг. (Так как при этом мы возвращаемся в клетку, с которой начинали, стрелочка делает целое число оборотов, то есть индекс – целое число.)

  Индекс относительно пути вдоль границы квадрата равен 1. Начнём теперь уменьшать наш путь – "откусим" сначала его левый верхний уголок (см. рис.).

  Заметим, что индекс при такой операции не меняется (так как среди стрелочек, выходящих из точекA, B, CиD, нет противоположных). Откусывая так по углу, через некоторое время мы продеформируем наш путь до пути, состоящего из одной клетки – а индекс такого пути равен 0. Противоречие.

Ответ задачи отсутствует