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