Индукция в графах и теорема Турана

Переформулируем условие задачи на язык графов. Каждому племени поставим в соответствие вершину, между любыми двумя соседними проведем ребро. Для каждой вершины определен ее идол, если идол соседней вершины сильнее, то в этот день вершина меняет своего идола на более сильного.

Будем решать задачу индукцией по количеству вершин. База индукции для графа, состоящего из одной вершины, очевидна.

Докажем, что если условие задачи верно для некоторого натурального то оно же верно для Выберем висячую вершину исходного дерева, родителем которой является вершина

Будем говорить, что вершина влияет на вершину если данные вершины являются соседями и идол сильнее идола при этом не имеет соседа с более сильным идолом, отличным от

Если не существует дня, в котором вершина влияло на вершину В графе, полученном из данного удалением вершины по предположению индукции все вершины через несколько дней будут иметь одного и того же идола, в частности его же будет иметь вершина а значит и вершина

Предположим, что существует день, в котором повлияло на После этого дня вершины и имеют одинакового идола. Теперь, если вершина меняет идола на более сильного, то на следующий день так же начинает поклоняться этому идолу, а значит не наступит дня, в котором имело бы более сильного идола, следовательно больше никогда не повлияет на тем самым мы можем применить рассуждения, проделанные ранее, для дня, после которого вершина повлияла на

Докажем утверждение задачи по индукции. Для двух городов утверждение очевидно. Пусть верно для городов, докажем для Выкинем некоторую вершину и все рёбра, с концом в этой вершине. Для оставшегося графа верно предположение индукции, то есть существует вершина такая, что из него можно добраться до любой другой по не более, чем рёбрам. Пусть из вершины напрямую можно добраться в вершины а только через другую вершину в Если из вершины или из какой-нибудь из вершин ребро ведёт в то вершина по-прежнему подходит. Если же во все эти вершины ведут рёбра из то подойдёт вершина в вершины можно попасть непосредственно, а в вершины — через вершины

Индукцией по докажем утверждение задачи для любого ладейно связного множества состоящего из клеток. Клетками далее называем клетки множества База очевидна.

Шаг индукции. Будем называть пары клеток, лежащих в одной строке или в одном столбце, доминошками. Удалим какую-нибудь доминошку, состоящую, для определенности, из клеток и лежащих в одном столбце. Останется множество клеток Две клетки назовём связанными в если от одной из них до другой можно дойти ладьёй по клеткам из

Построим три ладейно связных подмножества множества в подмножество включим все клетки, связанные в хотя бы с одной клеткой, лежащей на одной горизонтали с в подмножество — связанные в хотя бы с одной клеткой, лежащей на одной горизонтали с в подмножество — связанные в хотя бы с одной клеткой, лежащей на вертикали Заметим, что если какие-то два из множеств пересеклись, то они совпадают; в таком случае будем считать одно из них пустым.

Ясно, что Кроме того, остаётся связным при добавлении клетки — при добавлении клетки а — при добавлении любой из этих двух клеток.

Если все три множества состоят из чётного числа клеток, применим предположение индукции к этим множествам, а потом добавим доминошку

Если, скажем, в множествах и количества клеток нечётны, то эти множества непусты и количество клеток в каждом из них не превосходит а количество клеток в множестве чётно и не превосходит Тогда можно применить предположение индукции к множествам и Остальные случаи чётности разбираются аналогично.

Будем считать, что в некоторых вершинах графа может быть целое отрицательное количество монет, но суммарное количество монет равно Докажем задачу индукцией по

База для очевидна, так как имеется всего одна вершина и в ней ровно монет. Пусть теперь в графе вершина. В любом связном графе есть некоторая вершина при удалении которой граф не теряет связности. Если в ней ровно монет, удалим её и воспользуемся предположением индукции. Если в ней больше монет, то переместим лишние в соседнюю вершину чтобы в осталось ровно монет. Далее удалим её. В оставшемся графе по предположению справимся за не более чем ход. Суммируя с одним ходом из в получаем не более ходов. Если же в менее монет, докинем в неё из соседней вершины, чтобы стало ровно и далее как в предыдущем случае. В соседней вершине количество монет может стать отрицательным, но это учтено.

Для начала переведем задачу на язык графов. Города будут вершинами, а дороги будут ребрами. Из условия следует, что не существует вершины, которая не соединена с тремя другими вершинами, иначе мы бы взяли эту вершины и трех ее не соседей в четверку и получили противоречие. Теперь докажем по индукции, что в графе на вершинах, в котором каждая вершина максимум не соединена с вершинами, есть полный подграф на вершинах. База, если очевидна. Теперь переход. Пусть мы знаем для и хотим доказать для Рассмотрим вершину графа на вершинах. У нее есть минимум соседей. Рассмотрим подграф на этих вершинах и заметим, что для него также выполняется условие, что каждая вершина не соединина максимум с вершинами. Значит, по предположению индукции там есть полный подграф на вершинах. Теперь давайте добавим в этот граф вершину и получим полный подграф на вершине исходного графа.

Давайте будем говорить о направлении обхода в цикле. Он бывает по часовой стрелке и против часовой. Покажем, что смежные грани имеют разные направления обхода и все проходы муравья по ребрам будут соответствовать направлениям обхода соответствующих граней. Сделаем это индукцией по построению прямых. Изначально есть только стартовая прямая, она делит плоскость на части с разными направлениями обхода. Когда мы встретим первый перекресток, добавится очередная прямая. Её добавление инвертирует направления обхода в полуплоскости, отличной от той, в которой сейчас жук. Тогда поворот направо по этой прямой сохранит обход грани, по ребру которой мы пришли (по часовой), а в смежной грани направление обхода как раз против часовой, поскольку мы его инвертировали. Аналогично, поворот налево тоже всё сохранит. Таким образом, наша ситуация всегда корректна, значит направление обхода по каждому ребру зафиксировано. Что и требовалось доказать.

Решим задача для произвольного Докажем утверждение, известное в олимпиадных кругах как теорема Турана.

Оценка: Докажем по индукции, что число ничьих не превосходит

База индукции: При это очевидно. При все три игры не могли закончиться вничью, иначе у всех команд было бы одинаковое число очков.

Шаг индукции: Рассмотрим две команды и сыгравшие вничью. С каждой из остальных команд хотя бы одна из них сыграла не вничью, иначе образуется запрещенная тройка команд. Значит, общее число ничьих в играх с участием этих двух команд не больше По предположению индукции в играх между остальными командами было не более ничьих. Следовательно, общее число ничьих не превосходит

Пример: Пронумеруем команды числами от до Пусть каждые две команды с номерами разной чётности сыграли вничью, а в играх между командами с номерами одной чётности победила команда в меньшим номером. Если то команд имеют нечётный номер и команда - чётный, поэтому количество ничьих равно При получаем по команд с номерами каждой чётности и ничьих. В обоих случаях полученное число равно При этом каждые три команды в играх между собой набрали либо 0, 2 или 4 очка, если имеют номера одной чётности, либо очка, если две из них имеют номера одной чётности, а третья - другой.

Замечание. Заметим, что идея примера приходит из двудольного графа, где разная чётность номеров отвечает разным компонентам.

Подставим и получим ответ.

Будем считать людей вершинами, а дружбу — ребром. Докажем задачу индукцией по количеству вершин. База для одной вершины очевидна. Пусть теперь в графе вершин. Если граф не связен и распадается на компоненты, то ясно, что для каждой компоненты задача решается отдельно, значит мы можем использовать предположение, потому что в каждой из компонент не более вершины.

Пусть граф связен. Тогда мы можем выкинуть одну вершину так, что связность сохранится, а значит степень каждой вершины будет хотя бы По предположению полученный граф удовлетворяет условию. У выкинутой вершины степень также хотя бы поэтому мы сможем добавить её в одну из двух групп.

Выделим в нашем графе из вершин остовное дерево.

Докажем индукцией по что в любом дереве на вершинах можно выкинуть несколько рёбер, чтобы степень всех вершин стала нечётной.

Будем искать вершины с чётной степенью, начиная с нижнего уровня (посмотрели последний уровень, потом предпоследний и так дальше). Если мы не нашли, то задача решена.

Предположим, что мы нашли вершину чётной степени. Предположим, что является корневой вершиной. В таком случае, на втором уровне чётное количество вершин, на третьем — тоже, потому что из каждой вершины второго уровня выходит чётное количество рёбер на третий (потому что степени нечётные). Аналогично чётное количество вершин на всех остальных уровнях. Таким образом, на всех уровнях, кроме первого, чётное количество вершин, но тогда во всём дереве количество вершин нечётно, противоречие.

Следовательно, вершина не корневая. Значит, существует ребро, которое соединяет её с вершиной из уровня выше. Удалим его. Наше дерево распалось на два дерева. Корнем одного из них является и степень каждой вершины в этом дереве нечётная, потому что — первая попавшаяся вершина чётной степени (после удаления ребра её степень также нечётна).

Покажем, что в дереве с корнем чётное количество вершин. Действительно, на первом уровне вершина, на втором — нечётное количество, на всех остальных — чётное, потому что из любой вершины второго и ниже уровней выходит чётное количество рёбер на более низкий уровень, потому что одним ребром она соединена с вершиной из уровня выше, а её степень нечётная. Таким образом, суммарно количество вершин чётное.

Значит и во втором дереве количество вершин чётно, потому что всего вершин Притом в нём не более вершины, то есть для него справедливо предположение индукции.

Докажем индукцией по числу вершин.

База индукции для четырёх вершин верна, поскольку из условия сразу следует, что вершины разбиваются на группы, состоящие из трёх и одной оставшейся вершин соответственно.

Пусть теперь для вершин уже получено разбиение на две доли по предположению индукции и теперь мы думаем, куда добавить вершину чтобы получить разбиение на две доли для вершин.

Если смежна со всеми вершинами из группы с попарно смежными, добавим её туда. В противном случае ( соединена с какой-то вершиной из второй группы) докажем, что мы сможем её добавить во вторую группу.

Пусть вершина не соединена с вершиной из первой группы, а вершина — с вершиной (если соединена со всеми в первой группе, то перекинем её туда). Если то четвёрка вершин и не удовлетворяет условию. Если возьмём произвольную вершину из первой группы и заметим, что четвёрка будет удовлетворять условию только если с ней будет соединена вершина Получается, что соединена со всеми вершинами из первой группы, кроме Поместим в первую группу, а — во вторую и продолжим алгоритм.

Число вершин, с которыми смежна, во второй группе уменьшилось, следовательно, такой процесс конечен и мы определим во вторую группу.

Докажем утверждение индукцией по числу жителей города.

База очевидна. Достаточно распределить по одному человеку в группы.

Шаг индукции. Пусть а  – общее количество звонков в этот день. По условию поэтому найдётся житель разговаривавший не более чем с двумя жителями (в противном случае ). По предположению индукции, всех жителей города, кроме можно разбить на три группы так, чтобы выполнялось условие задачи. Житель не разговаривал с жителями, входящими в одну из групп, поэтому его можно добавить к этой группе, сохранив в силе требуемое утверждение.

Рассмотрим множество всех ребер фиксированного цвета в таком графе. Ясно, что либо все ребра имеют одну общую вершину (и такую конструкцию мы будем называть “пучком”), либо ребер всего три, и они образуют треугольник.

Будем решать задачу индукцией по числу цветов

База Если ребра единственного цвета образуют треугольник, то его вершины можно распределить по одной по трем группам. Если они образуют пучок, то достаточно отнести вершину пучка в одну группу, а все остальные вершины – в другую.

Переход. Разберем сначала случай, когда ребра хотя бы одного из цветов образуют пучок. Зафиксируем один из таких цветов, и удалим из графа все ребра, окрашенные в него, а также вершину соответствующего пучка. В полученном графе ребра окрашены уже в цвет, поэтому, по предположению индукции, вершины можно распределить по -ой группам. Отнесем удаленную вершину в отдельную -ую группу. Ясно, что все удаленные ребра соединяют вершины из разных групп, поэтому построенное разбиение является правильным для исходного графа.

Теперь, пусть в графе нет пучков, а есть только треугольники, и пусть в графе есть неизолированная вершина степени Удалим из графа эту вершину, а также все исходящие из нее ребра. Получится граф, ребра которого окрашены в цветов, который гарантированно содержит пучки. По доказанному выше, вершины такого графа можно правильным образом разбить на группы. Теперь вернем в граф удаленную вершину и ребра. Так как ее степень меньше, чем число групп, существует группа, которая не связана ребром с этой вершиной, а значит ее можно отнести в эту группу.

Докажем, что не существует графа, состоящего из треугольников, степень каждой неизолированной вершины в котором Это завершит решение задачи по индукции. Отметим, что в любом таком графе есть хотя бы неизолированные вершины. Посчитаем двумя способами количество ребер в нем. С одной стороны, оно равно так как ребра можно разбить по цветам; цветов ровно а ребер фиксированного цвета – ровно 3. С другой, так как степень каждой неизолированной вершины то число ребер Значит, натуральное число должно удовлетворять неравенству

Квадратный трехчлен имеет отрицательный дискриминант, откуда следует, что для любого выполнено Значит, неравенство выше не имеет решений. Следовательно, не существует графа с описанными выше свойствами.

(a) Рассмотрим граф с вершинами в городах, ребра которого соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в цвета правильным образом (то есть так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно утверждению задачи.

Выберем по одному ребру в каждом нечётном цикле графа и удалим их графа. Обозначим полученный граф В нем нет циклов нечётной длины. Любой такой граф можно окрасить в два цвета правильным образом. Зафиксируем одну такую раскраску, и присвоим одному цвету номер а другому номер

Рассмотрим граф, состоящий из удаленных ребер, который мы будем обозначать В нем степень каждой вершины не превосходит так как по условию задачи через каждую вершину в исходном графе проходит не более нечетных циклов. Ясно, что вершины такого графа можно окрасить в цвет. Действительно, вершины можно красить по очереди, и поскольку на каждом этапе окрашиваемая вершина соединена не более чем с уже окрашенными, для нее существует хотя бы один свободный цвет. Зафиксируем одну такую раскраску, и пронумеруем в ней цвета числами от до

Теперь рассмотрим исходный граф На каждой его вершине напишем пару из двух чисел соответствующих ее цвету в графах и По построению, число может быть либо 1, либо 2, а число  – произвольным от до Ясно, что для любых двух вершин, соединенных ребром в графе эти пары различаются хотя бы по одной из координат. Изготовим окраску графа в новые цвета следующим образом: если на вершине написана пара и то окрасим ее в цвет, имеющий номер если то в цвет с номером Нетрудно проверить, что две вершины будут окрашены в один цвет тогда и только тогда, когда написанные на них пары совпали, и значит по замечанию выше построенная окраска является правильной. Также ясно, что число использованных в ней цветов не превосходит что и требовалось.

(b) Рассмотрим граф с вершинами в городах, рёбра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более нечётных циклов. Докажем индукцией по количеству вершин, что вершины такого графа можно покрасить в цвета так, чтобы никакие две вершины одного цвета не были соединены ребром.

База для графа из одной вершины очевидна.

Шаг индукции. Пусть утверждение верно для графа, в котором менее вершин. Рассмотрим граф с вершинами, в котором через каждую вершину проходит не более нечётных циклов. Удалив из этого графа любую вершину и все выходящие из неё рёбра, мы получим граф с вершиной. Очевидно, через каждую вершину графа проходит не более циклов нечётной длины. Тогда покрасим вершины графа в цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).

Для цвета () рассмотрим граф из всех вершин графа покрашенных в цвета и и всех проведённых между ними рёбер графа Поскольку никакие две вершины одинакового цвета в графе не соединены ребром, то в этом графе нет циклов нечётной длины. Построим граф добавив к графу вершину и все выходящие из неё к вершинам рёбра.

Если для некоторого в графе через вершину не проходит ни один цикл нечётной длины, то циклов нечётной длины в этом графе нет. В этом случае мы можем так перекрасить вершины графа (используя лишь цвета и ), чтобы все рёбра в этом графе соединяли пары вершин разных цветов. Так как все остальные вершины графа покрашены в цвета, отличные от и , то и во всём графе никакие две вершины одинакового цвета не соединены ребром.

Остаётся рассмотреть случай, когда для каждого () в графе через вершину проходит хотя бы один цикл нечётной длины. Заметим, что такой нечётный цикл проходит только по вершинам цветов и причём среди них есть хотя бы одна вершина цвета Следовательно, любые два нечетных цикла из графов и проходящие через различны. Таким образом, через вершину проходит хотя бы цикл нечётной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.

Докажем индукцией по количеству вершин. База для треугольника очевидна, так вершин три и все три цвета присутствуют.

Если в многоугольнике ровно одна вершина определенного цвета, то несложно построить нужное разбиение, проведя все диагонали из этой вершины. Теперь пусть вершин всех цветов хотя бы две.

Пусть у нас есть -угольник. Обозначим его вершины последовательно через Попробуем у него найти три последовательные разноцветные вершины и Если мы их найдём, то мы сможем провести диагональ и решать задачу для выпуклого многоугольника без точки с помощью предположения индукции.

Итак, предположим, что такой тройки точек нет. Пусть точка окрашена в цвет а точка — в цвет тогда точка — снова в цвет иначе мы получим нужную тройку либо две соседние вершины одного цвета. Далее по аналогичным рассуждениям покрашена в цвет , — в цвет и так далее. В конечном итоге мы получим, что все вершины раскрашены в цвета и а вершины третьего цвета нет, противоречие.

Докажем индукцией по что если в связном графе вершин, то можно его обойти, пройдя не более чем по рёбрам. База для очевидна. Для этого выделим в графе остовное дерево и будем решать задачу для дерева.

Пусть у нас есть дерево на вершинах. Удалим висячую вершину и выходящее из неё ребро Оставшееся дерево по предположению можно обойти по рёбрам. Вернём вершину и вставим в маршрут кусок Количество пройденных рёбер станет что и требовалось.

Докажем индукцией по количеству игроков. База для двух игроков очевидна.

Пусть всего имеется игроков. Выкинем произвольного игрока Оставшихся игроков по предположению индукции выстроим по условию: Предположим, что игрока нельзя добавить в эту цепочку сразу после то есть выиграл у Далее предположим, что нельзя вставить между и тогда выиграл у Аналогичными рассуждениями получаем, что выиграли у Но тогда вставить в начало цепочки перед

Докажем индукцией по количеству вершин. Если в графе одна вершина, то утверждение задачи очевидно.

Пусть в графе вершин. В графе есть такая вершина при выкидывании которой граф не теряет связность. Выкинем её. В оставшемся графе по предположению индукции проведём нужную раскраску. Вернём вершину

Какая проблема могла возникнуть при возврате Чтобы не была одного цвета с одним из соседей, просто покрасим её в один из цветов, в который не покрашены соседи (такие цвета есть, потому что соседей не больше а цветов ).

Могло так оказаться, что какие-то соседи одного цвета, тогда при возврате одноцветные вершины имеют общих соседей. Рассмотрим вершины смежные с ней. Также рассмотрим вершины, с которыми соединены все Всего рассмотренных вершин вместе с не более Следовательно есть хотя бы цветов, в которые не покрашены ни одна из рассмотренных вершин. Покрасим вершины в эти цвета (каждую в свой цвет). Тогда все будут разных цветов и одноцветные вершины не будут иметь соседей. Что и требовалось.

Будем доказывать по индукции для связного графа. Если граф не связный, разобьём его на компоненту связности и решим задачу отдельно для каждой компоненты связности.

Итак, для графа на вершине утверждение очевидно. Рассмотрим граф на вершинах. Выкинем из него вершину так, чтобы оставшийся граф был связным. Полученный граф по предположению можно разбить на две части так как нужно. Теперь вернем вершину Она обязательно соединена с какой-то вершиной Добавим в часть, в которой нет

Докажем задачу индукцией по

Прежде чем доказывать базу, давайте поймём, какое минимальное значение может быть. Ясно, что оно ограничено, потому что, например, при описанная в задаче конструкция вообще невозможна.

Итак, в графе не более рёбер. Значит откуда . При описанная в условии конструкция реализуется, притом только если граф полный (это следует из рассмотренного неравенства).

База для очевидна, потому что степень каждой вершины то есть можно выкинуть одну вершину и степень остальных будет по

Переход. Пусть у нас есть граф на рёбрах. Рассмотрим вершину наименьшей степени. Если её степень не больше выкинем её. Мы получим граф на вершине с хотя бы рёбрами. Для этого графа мы умеем решать задачу по предположению.

Если же её степень хотя бы то и степень всех остальных хотя бы Значит, если её выкинуть, то степень соседних с ней вершин будет хотя бы а у несоседних — хотя бы Что и требовалось.

Первое решение. Докажем сначала следующую лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер.

Доказательство. Рассмотрим вершину наибольшей степени (пусть Пусть вершина cоединена с Ясно, что никакие и не могут быть соединены, потому что иначе в графе будет треугольник Степень оставшихся вершин не превосходит Таким образом, всего в графе не более Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь к задаче. Предположим, что в графе нет треугольников, тогда по лемме в нём не более рёбер. Но по условию в графе хотя бы ребро, пришли к противоречию.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем по индукции.

База при предположим, что у каждой вершины не более двух рёбер, тогда всего рёбер не более но их хотя бы Значит некоторая вершина соединена с тремя остальными. Но тогда остальные не могут быть соединены между собой, но в этом случае будет не более трёх рёбер, противоречие. Значит, треугольник всё-таки есть.

Переход: пусть у нас есть граф на вершинах с хотя бы рёбрами. Рассмотрим две смежные вершины. Если из них суммарно выходит не более ребро, выкинем их и применим предположение. Пусть из них выходит хотя бы ребра, одно из них — ребро, соединяющее эти вершины. Заметим, что если эти вершины соединены с одной и той же вершиной, то мы нашли треугольник, поэтому предположим обратное. Но тогда из них ведут рёбра к хотя бы -й различной вершине, тогда всего в графе не меньше вершин, пришли к противоречию.