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