Принцип крайнего
Ошибка.
Попробуйте повторить позже
В стране каждые два города соединены дорогой с односторонним движением. Докажите, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.
Подсказка 1
Рассмотрим город A, из которого ведет больше всего дорог. Попробуйте доказать, что это как раз город, который мы искали.
Подсказка 2
Рассмотрим город B, из которого идет дорога в A. Тогда попробуйте доказать, что найдется город С такой, что в него идет дорого из A и не идет дорога из B.
Рассмотрим город 
из которого выходит наибольшее число дорог, и произвольный город 
Если дорога ведёт из 
в 
то всё в порядке. Если же дорога ведёт из 
в 
то, поскольку из 
выходит не больше дорог, чем из 
найдётся город 
в который ведёт дорога из 
но не ведёт дорога из 
Тогда можно из 
попасть в 
по маршруту
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
