Question

В стране 50 городов, каждые два города соединены (двусторонними) авиалиниями, цены всех перелетов попарно различны (для любой пары городов цена перелета «туда» равна цене «обратно»). В каждом городе находится турист. Каждый вечер все туристы переезжают: богатые туристы — по самой дорогой, бедные — по самой дешевой линии, ведущей из соответствующего города. Через k дней оказалось, что в каждом городе снова по одному туристу. За это время ни один турист не посетил никакой город дважды. При каком наибольшем k такое возможно?

Answer 1

Решение:
Предположим, что среди туристов 25 или более богатых. Рассмотрим граф из 50 вершин, где каждая вершина обозначает город, а рёбра задают авиалинии. Пусть богатые туристы начинают движение из ближайшей к корню вершины своего дерева. Богатые загружаются на первую половину пути. Отсюда следует, что число переездов не может превышать 25.

Таким образом, бедные туристы также совершат 25 переездов, занимая в начальный момент вторую половину “богатого” пути.

Изложенная конфигурация позволяет туристам перемещаться следующим образом: A26 → A28 → ⋅⋅⋅→ A50 → A27 → A29 → ⋅⋅⋅→ A49 → A2 → A4 → ⋅⋅⋅→ A24 → A1 → A3 → ⋅⋅⋅→ A25

Цены авиалиний нечётных городов будут убывать от 49 до 1 рубля, а для чётных - от 50 до 2 рублей.

Ответ:
Наибольшее возможное k равно 25.