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