Азия-тынық мұхит математикалық олимпиадасы, 2016 жыл

Бір елде 2016 қала бар. Starways авиакомпаниясы бірнеше ел жұптары арасында, әр қаладан дәл бір сапар шығатындай бір бағытты сапарлар ұйымдастырғысы келеді. Келесі шарттар орындалатындай ең кіші натурал $k$ санын табыңыздар: авиакомпания сапарларды қалай ұйымдастырмаса да, кез келген қаладан сол қала кіретін жиындағы кез келген басқа қалаға 28-ден артық емес сапар жасау арқылы жете алмайтындай, барлық қалаларды $k$ жиынға бөлуге болады.

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

Ответ: 57

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

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

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