ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64727
Темы:    [ Теория графов (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

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


Решение

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

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


Ответ

Неверно.

Замечания

В эквивалентной задаче 64663 приведён другой контрпример.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2014
Номер 77
класс
Класс 11
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .