Гуляем по графу
Ошибка.
Попробуйте повторить позже
Рассмотрим граф, в котором 
вершины — это всевозможные строки из нулей и единиц длины 
, а ребро проводится между двумя
строками, если они отличаются ровно в одной позиции. В этом графе выбрали 
рёбер, не имеющих общих концов, и покрасили в
красный. Остальные ребра покрасили в синий. Докажите, что в графе найдется цикл длины не более чем 
, в котором красные и синие
рёбра чередуются.
Подсказка 1:
Попробуйте найти такой цикл в явном виде. Давайте рассмотрим произвольную вершину A и для удобства обозначим её соседа, отличающегося в i-м символе, через A_i. Пусть ребро AA₁ — красное. Давайте для A_i при i > 1 обозначим через B_i такую вершину, что A_iB_i — красное ребро. Что можно сказать про цвет рёбер между бэшками и ашками?
Подсказка 2:
Чтобы понять, какой цвет у некоторого ребра A_kB_i, нужно посмотреть на k-е символы у A_i и B_i. Если они разные, то ребро будет синим. Кажется, при некотором значении k цикл уже найден.
Подсказка 3:
Если для некоторого i такое k = 1, то мы нашли цикл длины 4: AA_iB_iA_1A. Давайте обозначим для A_i и B_i через f(i) символ, в котором они отличаются. Попробуйте соорудить нужный цикл.
Подсказка 4:
Давайте рассмотрим путь A_2B_2A_{f(2)}B_{f(2)}A_{f(f(2))}B_{f(f(2))}... — его идея заключается в том, что мы от соседа A идём по красному ребру, а потом идём к другому соседу по синему. Осталось лишь показать, почему этот путь рано или поздно замкнется в цикл, и разобраться с его длиной.
Выберем произвольную вершину 
обозначим через 
вершину, которая отличается от 
в точности в 
-ой позиции. Пусть не умаляя
общности ребро 
— красное. Для 
обозначим через 
соседа вершины 
соединенного с ней красным ребром.
Понятно, что 
так как любые две вершины 
и 
отличаются в 
позициях. Если 
и 
отличаются в позиции 
то
соединена синим ребром с 
Если для некоторого 
такое 
то мы нашли цикл длины 
с чередующимися
красными и синими ребрами. В противное случае обозначим для каждого 
через 
позицию, в которой отличаются
строки 
и 
Рассмотрим путь
то есть мы от соседа 
идем по красному ребру, затем возвращаемся в соседа 
по синему ребру, затем опять идем по красному и так
далее. Рано или поздно мы придем в ту вершину, в которой уже были, причем этой вершиной будет именно сосед 
так как в вершины на
расстоянии 
от 
мы приходим только по красным ребрам, а в каждую вершину ведет ровно одно красное ребро. Полученный цикл нам
подойдет. Исходя из сказанного выше, ребра в нем чередуются, и его длина не более чем 
так как каждая его вторая вершина — это
сосед 
причем не 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
