Уральский Турнир Юных Математиков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: .
Решение. Оценка. Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами. Значит, по крайней мере из 99 селений выходит хотя бы один телеграфный провод. Тогда имеется не менее 50 проводов, и количество дорог не больше разности чисел (число дорог в полном графе) и 50 (число проводов, которые заменяют собой некоторые «несостоявшиеся» дороги). Пример. Разобьем селения произвольным образом на пары, каждое селение соединим дорогами со всеми остальными, кроме парного ему.

Возьмем полный граф на 1022 вершинах, которые условно будем называть «толстыми». В середине каждого ребра поставим новую вершину (иными словами, мы заменяем каждое ребро этого графа на двузвенный путь).

Ответ: не обманывает.

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

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

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

Решение. Будем доказывать индукцией по , что дерево на вершинах имеет не более (толстых) паросочетаний с независимыми рёбрами. Причём если и толстых паросочетаний ровно , то дерево является путем. А при граф является или путем, или «графом-ёжиком».

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

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

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

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

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

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

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

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

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

Ответ: 3.

Решение. Оценка. Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека . Пусть тот, у кого больше всех знакомых. Если у один знакомый, то у кого-то из и тоже есть один знакомый (сам ), но тогда у не больше всех знакомых. Следовательно, у два знакомых и он знаком с и . Пусть — человек, который ушел перед . Так как у хотя бы два знакомых из и , то у их должно быть не менее 3 . Значит, знаком с и . Но тогда и у три знакомых. Противоречие.

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