|
|
 |
Условие
Город имеет вид квадрата $n\times n$, разбитого на кварталы 1×1. Улицы идут с севера на юг и с запада на восток. Человек каждый день утром идёт из юго-западного угла в северо-восточный, двигаясь только на север или восток, а вечером возвращается обратно, двигаясь только на юг или запад. Каждое утро он выбирает свой путь так, чтобы суммарная длина знакомых участков пути (тех, которые он уже проходил в том или ином направлении) была минимальна, и каждый вечер тоже. Докажите, что за $n$ дней он пройдёт все улицы целиком.
Решение
На каждом ребре сетки (отрезке улицы) поставим стрелки в направлениях на север или восток. Пусть город – квадрат $ABCD$, где $A$ – юго-западная вершина, $B$ – юго-восточная. Назовём весом узла сетки минимум из длин пути по сетке от него до вершин $A$ и $C$. Во все внутренние узлы, а также в $B$ и $D$ стрелок входит и выходит поровну (назовём эти узлы равновесными), в узлы на интервалах $BC$ и $CD$ входят две, выходит одна (назовём эти узлы финальными, обозначим их $B_k$ на $BC$ и $C_k$ на $CD$, где $k$ – вес), а в узлы на интервалах $AB$ и $AD$ входит одна, выходят две стрелки (назовём эти узлы стартовыми, обозначим их $A_k$ на $AB$ и $D_k$ на $AD$, см. рис.). Пути из $A$ в $C$ идут по стрелкам. Пути из $C$ в $A$ идут против стрелок, но их тоже будем считать путями по стрелкам из $A$ в $C$. Каждый путь имеет длину $2n$, веса узлов на нём сначала возрастают от 0 до $n$, затем убывают от $n$ до 0.
Будем нумеровать дни, начиная с 0, а также считать, что пройденные рёбра окрашиваются в синий цвет (исходный цвет рёбер – чёрный). Докажем индукцией по $k$, что в $k$-й день станут синими ровно $4(n - k)$ рёбер, после этого все рёбра, инцидентные узлам веса не более $k$, будут синими, а все синие рёбра, инцидентные узлам веса больше $k$, будут пройдены только по разу.
База $(k = 0)$. Проведём любой путь из $A$ в $C$. Заведомо есть ещё один путь из $A$ в $C$ по ещё не пройденным стрелкам, например, симметричный предыдущему относительно прямой $AC$. Проведём любой такой путь. Все четыре ребра, инцидентные $A$ и $C$ (узлам веса 0) пройдены. Каждый из узлов веса 1 имеет степень 3, через каждый прошел один путь.
Шаг индукции. Пусть настал $k$-й день. Первые $k$ звеньев любого пути выходят из узлов с весами от 0 до $k - 1$. По предположению индукции они пройдут по синим рёбрам. То же верно для $k$ последних звеньев. Значит, на пути может быть не более $2(n - k)$ чёрных рёбер. Докажем, что есть путь, где таких рёбер ровно $2(n - k)$.
На сторонах квадрата остались узлы веса не меньше $k$ и степени 3. По предположению индукции через них не могли пройти два пути, поэтому каждой из них инцидентна хотя бы одна чёрная стрелка (выходящая для $A_i$ и $D_i$, входящая для $B_i$ и $C_i$). При этом в узлах степени 3 веса $k$ осталось ровно по одной инцидентной стрелке, поскольку ребро, соединяющее его с узлом веса $k - 1$ по предположению индукции синее.
Стартуем из $A_{n-1}$ и будем идти по чёрным стрелкам, пока не дойдём до $B_{n-1}$ или не зайдём в тупик. Тупиком может быть только финальный узел $F$. Пусть он отличается от $B_{n-1}$. Ломаная $A_{n-1}F$ разбивает город на две части, и у части с узлом $B_{n-1}$ нет стартовых узлов на границе, кроме $A_{n-1}$. Выйдем из $B_{n-1}$ и будем идти против чёрных стрелок, пока не дойдём до ломаной $A_{n-1}F$. Далее по ломаной дойдём до $A_{n-1}$. Получим путь $A_{n-1}B_{n-1}$. Временно сотрём его звенья. После этого узлы $A_{n-1}$ и $B_{n-1}$ станут равновесными (а равновесные ранее узлы так и останутся равновесными). Аналогично строим путь $A_{n-2}B_{n-2}$: стартуем из $A_{n-2}$, получаем путь $A_{n-2}F$, если $F$ не $B_{n-2}$, то стартуем задним ходом из $B_{n-2}$ и дойдём до ломаной $A_{n-2}F$, потому что все неравновесные стартовые узлы лежат за этой границей. И т.д.
Построив путь $A_kB_k$ (и восстановив стёртые рёбра), получим путь $AA_kB_kC$ с ровно $2(n - k)$ чёрными рёбрами. Человек не обязан выбирать именно его, но ему придётся выбрать путь П, чёрная часть которого начинается в $A_k$ или $D_k$ и заканчивается в $B_k$ или $C_k$. Действительно, $2k$ путей, пройденные в первые $k$ дней, прошли через $2k$ узлов веса $k$ и окрасили $8k$ инцидентных им рёбер (по предположению индукции все эти рёбра различны). Но всего у нас есть 4 узла веса $k$ степени 3 и $2(k - 1)$ степени 4. Им инцидентны $8k + 4$ ребра. Как показано выше, все эти четыре ребра инцидентны узлам степени 3.
Окрасим путь П в синий цвет и обозначим те два из четырёх вышеперечисленных узлов, которые не стали концами П, $A'$ и $B'$. Докажем, что остался путь из $A'$ в $B'$ по чёрным рёбрам. Для этого, как и раньше, последовательно строим пути $A_{n-1}B_{n-1}, A_{n-2}B_{n-2}, ..., A_{k+1}B_{k+1}, A'B'$. Значит, человек выберет один из путей, проходящий через $A'$ и $B'$. Окрасив его в синий цвет, мы, в частности, сделаем синими последние четыре чёрных ребра, инцидентные узлам веса $k$.
В силу доказанного за $n$ дней будет пройдено всего $4(n + (n – 1) + ... + 1) = 2n(n + 1)$ рёбер, что совпадает с общим числом рёбер сетки.
Замечания
10 баллов
