Все задачи

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

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

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

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

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

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

На турнире можно одержать от 0 до 15 побед. Так как это ровно 16 вариантов, то каждый из этих вариантов встретился у одного из спортсменов. Следовательно, было сыграно игр, а это все возможные игры, которые могли быть сыграны. Таким образом, каждый участник сыграл 15 игр, у всех участников разное число побед, поэтому и разное число поражений.

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

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

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

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

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

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

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

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

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

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

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

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

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

Сопоставим каждой команде свою пятерку судей.

Ответ. Можно.

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

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

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

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

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

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

Ответ. 51 человек.

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

Пример. Пусть человек с номером знаком с людьми с номерами от до 99, других знакомств нет. Уходить они будут по порядку от 1 до 48 . На момент ухода -го человека: ему не знакомы только следующих за ним, остальным из этих 48 — хотя бы следующих и предыдущий, а последним 51 — хотя бы 50 , что тоже не меньше .

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

Ответ: 2500.

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

Можно оставить только остовное дерево.

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