Question

В Тридесятом государстве есть 2018 городов, каждые два из которых соединены прямыми авиалиниями. Сотруднику авиакомпании под Новый год дали премию: 213 бесплатных перелетов (один перелет – из города в город, только в одну сторону). Он хочет посетить как можно большее количество городов и вернуться домой, пользуясь только премиальными перелетами. Какое наибольшее количество городов ему удастся посетить? (Город, в котором он живет, в ответе не учитывается).

Answer 1

212 городов он сможет посетить т.к. 213 будет билет в его родной город

Answer 2

Давайте рассмотрим эту задачу. У нас есть 2018 городов в Тридесятом государстве, и каждые два города соединены прямыми авиалиниями. Сотруднику авиакомпании дано 213 бесплатных перелетов, и его цель - посетить максимальное количество городов и вернуться домой, используя только премиальные перелеты.

Для начала заметим, что мы можем посетить только четное количество городов, поскольку каждый полет соединяет два города.

Теперь давайте построим граф, где вершины представляют города, а ребра - прямые авиалинии между городами. У нас есть 2018 вершин, и каждая вершина имеет степень 2017, так как каждый город соединен со всеми остальными городами.

Если мы рассмотрим цикл в этом графе, то мы можем посетить 2 города, используя только 1 перелет. Например, пусть у нас есть города A, B и C, и есть прямые авиалинии A-B и B-C. Мы можем начать с города A, лететь в город B, затем в город C и, наконец, вернуться обратно в город A, используя всего один перелет.

Теперь наша цель - посетить максимальное количество городов с помощью 213 перелетов. Если мы сможем построить несколько циклов, то каждый цикл даст нам возможность посетить 2 города, используя только 1 перелет.

Максимальное количество циклов, которое мы можем построить с помощью 213 перелетов, равно 213 / 2 = 106. Таким образом, сотруднику авиакомпании удастся посетить 106 * 2 = 212 городов (поскольку каждый цикл дает нам возможность посетить 2 города).

Итак, наибольшее количество городов, которые сотрудник сможет посетить, составляет 212 (не учитывая город, в котором он живет).