Комбинаторика на ММО: графы, турниры, логика, конструктивы

Пусть города королевства расположены и соединены железными дорогами так, как указано на рисунке. Тогда условие задачи выполнено. Действительно, можно представить, что на рисунке изображен многогранник с равными ребрами, который получается из правильного тетраэдра отсечением четырёх его вершин плоскостями. Тогда для любой упорядоченной пары его вершин можно совершить такое движение этого многогранника, при котором вторая вершина пары перейдет в первую её вершину и все вершины многогранника поменяются местами. Соответствующее такому движению переименование городов останется не замеченным королем, так как каждые два города с новыми названиями будут соединены железной дорогой тогда и только тогда, когда такой дорогой были соединены города, прежде носившие эти имена.

Рассмотрим такое переименование всех городов, при котором города и поменялись именами. Покажем, что в этом случае король заметит изменения. Действительно, если город изменил свое название, то король заметит, что единственный город, который был соединен дорогой и с и с теперь называется иначе. Если же город не изменил свое имя, то новый город теперь не будет соединен и с городом и с новым городом ведь новый город раньше был городом а городов, соединенных и с и с не было.