Азиатско-Тихоокеанская математическая олимпиада, 2016 год

В стране 2016 городов. Авиакомпания Starways хочет организовать односторонние рейсы между некоторыми парами городов так, чтобы из каждого города выходил ровно один рейс.
Найдите наименьшее натуральное $k$, удовлетворяющее условию: как бы авиакомпания ни организовала рейсы, все города можно будет разбить на $k$ групп так, что из любого города нельзя будет добраться ни до какого другого города той же группы, используя не более 28 рейсов.

Комментарий/решение

Ответ: 57

Назовем цикл простым если в этом цикле из каждой вершины выходит ровно одно ребро, таким образом этот цикл образует круг. Очевидно, что изначальный граф состоит из простых циклов (возможно с некоторыми хвостиками).

Пример: Рассмотрим любой простой цикл и пусть длина этого цикла $N=29k+r$. Тогда нам достаточно разбить вершины на $29+r \le 57$ групп, чтобы выполнялось условие задачи.

Оценка: Рассмотрим цикл состоящий из 57 вершин и докажем, что потребуется хотя бы 57 групп, что бы разбить данные вершины. Если групп максимум 56, то по Принципу Дирихле найдутся две вершины которые попадут в одну группу. Не сложно догадаться, что любые две вершины данного цикла имеют расстояние $\le 28,$ противоречие.