Средняя сложность

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

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

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

Таким образом, все наборы разбились на пары, то есть их четное число. Противоречие.

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

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

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

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

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

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

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

Заметим, что может быть взято за тогда и только тогда, когда ни для какого мальчика множество его знакомых в не совпадает с . Аналогично с и .

Заметим, что может быть взято за тогда и только тогда, когда ни для какого мальчика множество его знакомых в не совпадает с . Аналогично с и . Предположим, что нашлось множество из мальчиков, в котором нельзя выделить , удовлетворяющее условию. Тогда для любого найдется девочка, которая в множестве знакома в точности с мальчиками из . Выберем в мальчиков, из них — 256 , и каждому мальчику сопоставим своё четырёхзначное двоичное число. Выберем 8 девочек так, чтобы -ая девочка знала в множестве в точности тех мальчиков, которым сопоставлено число с 1 в -ом разряде (мальчиков, которым ничего не сопоставлено, все эти девочки не знают). Тогда легко видеть, что в выбранном множестве девочек никакое подмножество нельзя назначить . Действительно, если — номера девочек в подмножестве, то мальчик, которому сопоставлено число с единицами в разрядах и нулями во всех остальных разрядах, из восьми выбранных девочек знает в точности .

Всего троек команд можно составить . Назовем плохой командой не разносторонней тройки ту, которая с двумя другими играла в одну и ту же игру. Так как нет трех команд, которые друг с другом играли в один и тот же вид спорта, в каждой не разносторонней тройке одна плохая команда.

Ответ. 14.

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

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

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

Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Согласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир и выберем те партии, победители которых до этого не выигрывали (например, такова первая партия).

Ответ. 3.

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

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

Осталось привести пример при . Пусть участники пронумерованы от 1 до 8 и пары в кубке таковы (первым указан проигравший, вторым победитель): , тогда при игре навылет пары могли быть такими (победитель снова указан вторым): , .

Допустим, что каждый город соединен не более чем с двумя другими. Тогда все дороги объединяются в циклы (замкнутые маршруты) и цепи (незамкнутые маршруты), не связанные между собой.

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

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

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

Ответ: Нет.

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

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

Ответ: .

Решение. Рассмотрим любую группу из 51 человека. Если выкинуть любого из них, среди оставшихся будет одно и то же число знакомств. Поэтому в этой группе каждый имеет среди остальных 50 одно и то же число знакомых. Пусть оно равно . Тогда общее число знакомств среди 50 человек должно равняться . Значит, значение а будет одним и тем же для всех компаний из 51 человека. Возьмем любого человека Ч. Среди остальных 99 есть либо 50 знакомых с ним, либо 50 незнакомых с ним. Добавляя их к Ч, получим компанию, где в первом случае , а во втором . Но второй случай невозможен по условию, а в первом случае, очевидно, каждый знаком с каждым. Отсюда получаем ответ.