В стране n городов. Между каждыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придётся поменять вид транспорта не более одного раза.

   Решение

Темы:    [ Процессы и операции ] [ Полуинварианты ] [ Разбиения на пары и группы; биекции ]

Сложность: 4+ Классы: 7,8,9

Прислать комментарий

Условие

Круг разбит на n секторов, в некоторых секторах стоят фишки – всего фишек  n + 1.  Затем позиция подвергается преобразованиям. Один шаг преобразования состоит в следующем: берутся какие-нибудь две фишки, стоящие в одном секторе, и переставляются в разные стороны в соседние секторы. Докажите, что через некоторое число шагов не менее половины секторов будет занято.

Решение

  Поскольку фишек больше чем секторов, то в любой момент в каком-то секторе будут находиться не менее двух фишек. Значит, движение продолжается бесконечно долго.
  Занумеруем все секторы, начиная с данного, числами 1, ..., n  в порядке их обхода по часовой стрелке. Для каждой фишки вычислим квадрат номера её сектора. Пусть S – сумма этих квадратов. Если сектор 1 все время пуст, то S с каждым ходом увеличивается: при ходе из сектора k  (k < n)  к S добавляется
(k + 1)² + (k – 1)² – 2k² = 2.  С другой стороны,  S ≤ (n + 1)n².  Противоречие.
  Значит, когда-то в сектор 1 попадёт фишка. После этого всегда либо сектор 1, либо сектор 2 будет непустым: всякий раз, когда освобождается один из них, второй заполняется.
  Поскольку все секторы равноправны, наступит момент, когда все они побывают заполненными. После этого, как показано выше, оба соседа каждого пустого сектора непусты. Поэтому пустых секторов будет не больше чем непустых.

Замечания

1. 12 баллов.

2. Задача предлагалась в 1992 г. на Санкт-Петербургской математической олимпиаде (7-8 кл., задача 7).

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