Question

Вволшебном лесу росло 2019 деревьев. между некоторыми деревьями лесные жители протоптали тропинки. оказалось, что если какая-либо дорога заросла бы бурьяном, по остальным можно было бы добраться от любого дерева до любого другого. однажды лиса и волк поймали зайца и никак не могли решить, кому он достанется. они стали по очереди (начиная с лисы) вводить на обычных тропинках одностороннее (направленное) движение, изменяя по одной тропинке за раз. тот, после чьего изменения не от каждого дерева можно будет добраться до каждого из остальных, проигрывает, отдавая зайца сопернику. кому достанется заяц при правильной игре?

Answer 1

Рассмотрим связный граф на 2019 вершинах, в котором вершины представляют собой деревья, а ребра - тропинки между ними.

Назовем граф правильным, если из каждой вершины можно добраться до каждой.

У этого графа есть важное свойство: если удалить любое из ребер, граф не потеряет связность.

Из этого следует, что между любыми двумя вершинами существует по крайней мере два пути по ребрам (*).

Рассмотрим следующую тактику для волка: пусть лиса сделала ход. Рассмотрим две вершины, между которыми она установила одностороннее движение (пусть это вершины A и B). По (*) ясно, что между A и B, помимо самого ребра, соединяющего эти вершины, есть по крайней мере еще один путь. Рассмотрим любой из таких путей. Тактика волка будет заключаться в том, чтобы на любом из ребер, которое принадлежит пути, поставить противоположное направление по отношению к AB. Покажем, что такая тактика является для волка непроигрышной. То есть докажем, что после хода волка граф останется правильным. Предположим противное. Пусть из некоторой вершины X нельзя добраться до вершины Y. Рассмотрим два случая:

1) между X и Y есть ребро.

Тогда оно ориентировано. Поскольку волк следует тактике, то волк только что поставил одностороннее движение на XY. Но XY, согласно тактике, является частью пути между какими-то вершинами (пусть M и N). M и N друг для друга достижимы, точно так же M достижимо для X, а N для Y (без ограничения общности). Пусть из X можно добраться в Y (по ребру между ними), тогда добравшись из Y в N, а там из N в M, а из M в X мы доберемся из Y в X, тогда X и Y взаимно достижимы, противоречие.

2) между X и Y нет ребра.

Точно так же, XY - часть какого-то пути между двумя вершинами. Путь между XY состоит из взаимно достижимых вершин, соединенных ребрами ( доказано в 1) ). Значит, и X и Y взаимно достижимы, противоречие.

Итак, данная тактика является непроигрышной. Пусть волк не будет действовать по этой тактике. Тогда по этой тактике будет действовать лиса, а, значит, волк будет действовать по невыигрышной тактике (что называется неправильная игра). Пусть тогда волк будет действовать волк. Но тогда точно так же придется поступить и лисе. Осталось доказать, что лиса не может проиграть первым ходом. Пусть она изменила напр. на каких-то двух вершинах (они соединены ребром). Тогда они взаимно достижимы по второму пути (после хода лисы всего одно ребро ориентировано). Итак, при правильной игре будет ничья.