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