|
|
 |
Условие
В виртуальном компьютерном государстве не менее двух городов. Некоторые пары городов соединены дорогой, причём из каждого города можно добраться по дорогам до любого другого (переходить с дороги на дорогу разрешается только в городах). Если при этом можно, начав движение из какого-то города и не проходя дважды по одной и той же дороге, вернуться в этот город, государство называется сложным, иначе – простым. Петя и Вася играют в такую игру. В начале игры Петя указывает на каждой дороге направление, в котором по ней можно двигаться, и помещает в один из городов туриста. Далее за ход Петя перемещает туриста по дороге в разрешённом направлении в соседний город, а Вася в ответ меняет направление одной из дорог, входящей или выходящей из города, куда попал турист. Вася победит, если в какой-то момент Петя не сможет сделать ход. Докажите, что
а) в простом государстве Петя может играть так, чтобы не проиграть, как бы ни играл Вася;
б) в сложном государстве Вася может гарантировать себе победу, как бы ни играл Петя.
Решение
Рассмотрим граф, вершинами которого являются города, а рёбрами – дороги.
а) Условие означает, что граф – дерево. Петя выбирает произвольную вершину. От каждой вершины существует ровно один путь в выбранную.
Все рёбра на этом пути он ориентирует в сторону выбранной вершины.
Первым ходом Петя перемещает туриста в выбранную вершину. Все ориентированные пути ведут к туристу. Вася разворачивает одно ребро.
Турист идёт по нему. Ясно, что все пути снова ведут к нему. Вася снова разворачивает одно ребро и так далее. Поэтому у Пети всегда есть ход и он не проиграет.
б) По условию граф связен и содержит цикл. Будем доказывать индукцией по количеству вершин, что Вася может гарантировать себе победу для любой изначальной расстановки стрелок перед его ходом (включая "невозможный" случай, когда все стрелки ведут из вершины, где стоит фишка перед первым ходом Васи).
База – простые циклы. Пусть в простом цикле
$A_1A_2...A_n$ как-то расставлены стрелки на рёбрах и турист смог сделать ход,
пойдя из $A_1$ в $A_2$. Вася будет разворачивать стрелки перед ним. Поэтому турист не сможет идти в обратную сторону. Допустим, турист смог дойти до $A_1$.
Тогда перед ним разворачивают стрелку, и ему некуда идти. Петя проиграл.
Шаг индукции. Граф не является простым циклом. Выберем в нём цикл $C$ минимальной длины. Ясно, что он простой и не содержит ребёр внутри себя.
Поэтому есть вершины вне $C$. Выберем из них вершину $V$ с максимальным расстоянием до $C$. Обозначим граф без $V$ буквой $G$. Ясно, что $G$ связен и содержит цикл.
По предположению индукции в $G$ есть выигрышная стратегия для Васи при любой ориентации рёбер. Внутри $G$ Вася будет следовать ей. Так как в $G$ Петя проигрывает, то турист вынужден будет когда-то пойти в $V$. Тогда Вася развернёт эту стрелку. Турист выйдет из $V$, а Вася сделает любой допустимый ход в $G$.
Турист пойдёт внутри $G$. Сейчас у Васи опять есть выигрышная стратегия в $G$, которой он и будет следовать. Турист снова будет вынужден зайти в $V$, уменьшив количество стрелок, идущих из $G$ в $V$. В конце концов они кончатся, и Петя проиграет в $G$, если он не проиграл раньше.
Замечания
баллы: 5 + 7
