Задача 64663

Темы:    [ Теория графов (прочее) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4+ Классы: 10,11

Условие

Авторы: Пахарев А., Скопенков М.Б., Устинов А.В.

Каждому городу в некоторой стране присвоен индивидуальный номер. Имеется список, в котором для каждой пары номеров указано, соединены города с данными номерами железной дорогой или нет. Оказалось, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, но список по-прежнему будет верным. Верно ли, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, город с номером N получит номер M, но список по-прежнему будет верным?

Решение

  Рассмотрим страну из 12 городов, соединённых дорогами так, как показано на рисунке.

  Заметим, что рисунок симметричен относительно каждого диаметра, проходящего через середины малых хорд окружности, на которой лежат все города. Этими симметриями мы можем поменять номерами любую пару соседних по кругу городов. А с помощью нескольких симметрий каждый номер можно перевести в любой другой, то есть условие выполнено. Предположим, что нам удалось поменять номерами города 1 и 3 с сохранением списка соседних городов. Тогда их единственный общий сосед 2 обязан сохранить свой номер. Оставшемуся соседу 9 города 2 тоже придётся сохранить номер. Но у городов 3 и 9 два общих соседа (2 и 8), а у 1 и 9 – только один. Противоречие.

Ответ

Неверно.

Замечания

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

2. 9 баллов.

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

олимпиада
Название	Турнир городов
Турнир
Номер	35
Дата	2013/2014
вариант
Вариант	весенний тур, сложный вариант, 10-11 класс
задача
Номер	6