Гуляем по графу
Ошибка.
Попробуйте повторить позже
В стране 30 городов и 30 двусторонних авиалиний, соединяющих города по циклу. Можно ли добавить дополнительно ещё 10 авиалиний так, чтобы после этого из любого города можно было добраться до любого другого не более чем за 4 перелёта?
Источники:
Подсказка 1:
Эта задача - конструктив. Попробуйте придумать пример.
Подсказка 2:
Для удобства введите нумерацию городов по кругу от 0 до 29. Попробуйте строить пример, опираясь на остаток при делении на 3 номеров городов. Это удобно, потому что, например, из любого города мы можем за не более чем 1 перелёт попасть в город с номером, кратным трём.
Подсказка 3:
А что, если соединить 0 город с остальными городами, номера которых кратны 3? Почему это рабочий пример?
Занумеруем города числами 0, 1, 2, …, 29 так, чтобы изначально у нас был цикл 
Добавим 9 авиалиний
…, 
(а 10-ю авиалинию добавим какую угодно).
Покажем, что условие выполняется. Возьмем любые два города 
и 
От 
можно не более чем за 1 перелёт добраться до города
с номером, кратным 3. Аналогично, от 
можно не более чем за 1 перелёт добраться до города 
с номером, кратным 3. А между
городами 
и 
либо есть путь не более, чем из двух перелётов, так как все города с номерами, кратными 3, соединены с городом номер
0.
да, можно
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
