Эйлеровы графы

Рассмотрим граф с вершинами в узлах сетки и ребрами — отрезочками между узлами. Заметим, что в графе есть 8 вершин нечетной степени (по 2 на каждой стороне). Заметим, что как минимум в 6 из них наш маршрут не начинается и не заканчивается. А значит, мы входили в эти вершины столько же раз, сколько и выходили из них. То есть для каждой такой вершины одно из ее ребер было пройдено дважды. Отметим для каждой из наших вершин такое ребро. Заметим, что одно и то же ребро может быть отмечено не более 2 раз (по одному раз для каждого конца). Поэтому мы прошли дважды хотя бы по 3 ребрам. Поэтому длина нашего пути не меньше, чем метров.

Теперь приведем пример. Начнем из второго сверху перекрестка на самой правой улице. Сначала обойдем всю границу. Мы вернулись в начальный перекресток. Теперь идем так: влево, вверх, влево, вниз, влево, вниз, вправо, вниз, вправо, вверх, вверх, влево, вниз, вправо, вправо. В итоге как раз получится 2700 метров.