9 класс

Попробуйте доказать индукцией по количеству сенаторов.

Докажем индукцией по числу сенаторов. База. Для трех сенаторов есть только два круговых порядка. Они получаются друг из друга пересадкой двух соседей, которые не в ссоре. Шаг индукции. Найдется сенатор А, который в ссоре не более чем с одним сенатором (иначе часть сенаторов можно будет рассадить по кругу так, что у каждого соседями будут враги). Пусть Б в ссоре с А (а если А дружит со всеми, то Б — любой другой). По предположению индукции, если А уйдет из-за стола, то есть способ рассадить оставшихся в нужном круговом порядке. Однако это можно сделать и при наличии А. Придвинем А к Б (это можно сделать) и попросим А и Б взяться за руки. Считая эту пару сенатором Б, рассадим всех в нужном порядке вышеуказанным способом. Теперь можно А посадить на нужное место, последовательно «отодвигая» его от Б.

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

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

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

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

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

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

Для построение примеры выделите одну из вершин. А часть рёбер сделайте очень длинными.

Ответ: 99.8 часов.

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

Пример. Все города связаны с дорогами, требующими 4 часов каждая. Остальные города либо связаны дорогами, либо нет, чтобы общее число дорог равнялось 1000. Все дороги между ними требуют 8 часов. Легко видеть, что оценка достигается.

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

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

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

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

Каждую вершину можно перекрасить двумя способами. Поэтому количество способов, которыми можно испортить вершины нашего графа, равно . С другой стороны, столько же должно получиться, если просуммировать по всем вершинам количество способов, которыми они могут быть испорчены. Поскольку в этой сумме все слагаемые не больше 2 , все они должны равняться 2. Это возможно только если в нашем графе степень каждой вершины равна 2 . Стало быть, он распадается на непересекающиеся циклы, причём каждую вершину каждого цикла можно испортить двумя способами. Такое возможно только если каждая вершина и те вершины, что идут в цикле через одну от неё, покрашены в три разных цвета. Нетрудно показать, что длина цикла в этом случае должна делиться на 3 . Но 2008 на 3 не делится.

Построим новый граф, вершинами которого будут остовные деревья нашего графа.

Пусть — наш граф, обозначим через количество его вершин. Построим новый граф , вершинами которого будут остовные деревья графа . Вершины, соответствующие деревьям и соединим ребром тогда и только тогда, когда в деревьях и совпадают ребра (то есть одно дерево получается из другого заменой одного ребра). Рассмотрим любое остовное дерево графа и рассмотрим любое его ребро . Уберем ребро , вершины дерева распадутся на две компоненты связности и . Так как степень каждой вершины графа четна, то в графе четное число ребер с одним концом в и другим концом в . Заменив ребро на любое другое ребро между и , мы получим все остовные деревья, получающиеся из заменой ребра на какое-то другое ребро. Количество таких деревьев нечетно. То же самое верно для любого ребра дерева . Так как в нечетное число ребер, то из соответствующей дереву вершины графа выходит нечетное число ребер. Это означает, что количество вершин графа (то есть, остовных деревьев графа ) четно.

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

Пусть — наши пары. Каждую девочку соединим с другой девочкой, знакомой с . В результате получится граф на вершинах , с 2015 рёбрами. Нам нужно покрасить этот граф правильным образом в три цвета, это и будет искомая покраска девочек. Рассмотрим компоненту связности построенного графа, пусть в ней вершин, тогда и рёбер в ней тоже (Мы провели по одному ребру из каждой вершины этой компоненты связности, из вершин вне компоненты рёбра в нее не входят). Если есть вершина степени 1 , удалим ее, эту вершину можно будет легко докрасить после покраски остальных вершин компоненты. После серии таких операций наша компонента связности будет иметь минимальную степень вершины 2 , а значит, это будет простой цикл, который мы легко покрасим в три цвета.

Рассмотрим двуцветный ориентированный граф, у которого вершинами будут элементы множества , и от вершины к вершине идет синяя стрелка, если делится на , и красная, если делится на .

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

Поделим вершины на три группы: исходные, выбранные и хорошие (вершины будут перемещаться из группы в группу, но никакая вершина на может находиться в двух группах одновременно). Изначально все вершины находятся в группе исходных. Выберем среди них такие, в которые не входит ни одна синяя стрелка и отправим их в группу выбранных. Тогда, в силу транзитивности синих стрелок, в каждую исходную вершину ведет хотя бы одна синяя стрелка из выбранных вершин. Если так случилось, что между выбранными вершинами нет красных стрелок, то, приняв за множество выбранных вершин, мы решим задачу. Если же красные стрелки есть, то найдем все выбранные вершины, в которые ведет хотя бы одна красная стрелка из других выбранных, и отправим их в группу хороших. После этого, могло оказаться, что в некоторые исходные вершины не идет синей стрелки из выбранных. В этом случае добавим в множество выбранных те вершины из исходных, в которые синие стрелки приходят только из хороших вершин. После этого снова отправим в группу хороших те из выбранных вершин, в которые ведет хотя бы одна красная стрелка из других выбранных. В силу транзитивности теперь уже красных стрелок, в любую хорошую вершину все еще ведет хотя бы одна красная стрелка из выбранных. Будем продолжать такие перемещения (из исходных в выбранные, из выбранных в хорошие). Заметим, что если в некоторый момент мы не смогли уменьшить множество исходных вершин, то задача решена,а так как изначально там конечное число вершин, этот момент обязательно наступит.

Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города и город соединен только с городом 100.

Ответ: 2500.

Решение. Оценка. Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города и город соединен только с городом 100. Предположим, что все города были посещены хотя бы три раза. Тогда есть хотя бы два города, которые соединены только с городом 100 . Но наибольший из таких городов может быть посещен только один раз (когда путешествие начинается в нем). Если все города посещены 1 раз, то в стране вообще нет дорог, что нас не устраивает. Значит, все города посещены ровно два раза. Удалим город 100 и город , соединенный только с ним. Мы удалили не более дорог. Для оставшейся части страны всё ещё верно утверждение, что при путешествиях с началом в каждом из городов, все города посещаются поровну раз, так как города и 100 посещались ровно 2 раза в путешествиях с началом и 100. Повторяя такие рассуждения, мы будем удалять пары городов, удаляя не более дорог. Значит, изначально в стране было не более 2500 дорог. Пример: при город соединим с городами с номерами хотя бы . Также соединим попарно города с номерами, большими 50. Тогда начиная в городе мы перемещаемся в город и останавливаемся. Значит, все города будут посещены дважды. И количество ребер равно .

Рассмотрим пару знакомых человек: назовем их и . В множестве членов компании, отличных от и , выделим три множества: — множество общих знакомых и — множество знакомых с , но не с множество знакомых с , но не с .

Ответ. ( ) для любого .

Решение. Рассмотрим пару знакомых человек: назовем их и . В множестве членов компании, отличных от и , выделим три множества: — множество общих знакомых и — множество знакомых с , но не с множество знакомых с , но не с .

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

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

Если , то мы получили, что любые два знакомых человека имеют одинаковое число знакомых. А поскольку любые два либо знакомы, либо имеют общего знакомого, то такое невозможно, так как Дима и Саша имеют разное число знакомых.

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

Если все враги одного из двух друзей являются врагами другого, то у любых двух друзей одни и те же враги. При этом друг моего друга — мой друг, иначе у меня был бы враг, который не враждует с моим другом.

Ответ. 11, 12, 15, 20.

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