8 класс

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых.

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых. Если таких пар наберется 25 , среди входящих в них 50 человек не найдется никого, кто был бы знаком с 49 остальными — противоречие. Значит, таких пар не больше 24 , и в них входит не больше 48 человек. Понятно, что среди 52 (или большего числа) остальных людей каждый знает каждого, что и требовалось доказать.

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

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

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

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

Ответ: Нет.

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

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

Ответ: .

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

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

Заметим, что четность числа горящих лампочек в любой момент такая же, как в начальном состоянии. Устроим систему из 2004 выключателей следующим образом: одна лампочка А является выделенной, и каждый выключатель подключен к ней и еще какой-то из других лампочек (разные выключатели — к разным лампочкам). Если в начальном состоянии горит четное число лампочек, то погасим их, последовательно выключая их и переключая лампочку А (в итоге все лампочки, включая А, будут погашены). Если же в начальном состоянии горит нечетное число лампочек, то включим все остальные (их четное число, поэтому в итоге лампочка А тоже будет включена). Докажем, что меньшего числа выключателей не хватит. Действительно, при меньшем количестве выключателей граф лампочек несвязен, поэтому есть или хотя бы одна четная компонента связности, или хотя бы три нечетных компоненты. В четной компоненте достаточно рассмотреть такое начальное состояние, в котором горит только одна лампочка (и с ним уже ничего нельзя сделать), а на двух нечетных компонентах достаточно зажечь 0 и 1 лампочек соответственно — тогда одну из компонент можно будет только погасить, а другую — только зажечь.

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

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

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

Ответ: 148.

Решение. Пример на 148. Построим ориентированный граф, вершинами которого будут числа от 1 до 100 , а каждое из ребер связывает номер места, на котором стоит том с данным номером, с самим этим номером. Поскольку из каждой вершины этого графа выходит ровно одно ребро, и в каждую его вершину входит ровно одно ребро, все его вершины и ребра разбиваются на непересекающиеся ориентированные циклы. Цикл, в который входит красный том, назовем особым, прочие — обычными. Возьмем любой обычный цикл и добавим в него красный том (пусть его номер равен ): . Затем последовательно поменяем местами красный том со всеми остальными элементами получившегося цикла. В итоге все элементы исходного обычного цикла встанут на предписанные им места, а красный том вернется на исходное место. Проделаем описанную процедуру со всеми обычными циклами длины, не меньшей 2 , а напоследок «прокрутим» особый цикл, после чего все тома окажутся на своих местах, т.е. будут идти в порядке возрастания. При этом на приведение в порядок каждого цикла длины , кроме особого, у нас ушла перестановка, а на особый цикл — перестановка, а всего — перестановки, где — число циклов длины не меньше 2 . Поскольку циклов длины 2 и больше не более 50, мы совершили не больше 148 перестановок. Оценка. Пусть получилось 50 циклов длины 2. На приведение в порядок каждого обычного цикла нужно минимум 3 перестановки: убрать один том, поставить на его место другой и поставить на место другого первый. Еще одна перестановка нужна на особый цикл. Итого .

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет.

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет. Заметим, что каждая компонента связности графа знакомств содержит не более 4 вершин (иначе там есть пять вершин, связанные минимум 4 ребрами). Такие компоненты могут иметь вид одиночного ребра, цепи из двух или трех ребер и «»ежа»» из трех ребер, исходящих из одной вершины. Легко проверить, что в каждой такой компоненте можно отметить не менее половины вершин так, чтобы никакие две отмеченные вершины не были связаны ребром. Сделав это, получим не менее 10 отмеченных вершин, попарно не соединенных между собой.

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

Ответ: 27. Решение. Напомним, что через обозначается полный двудольный граф на 6 вершинах, то есть граф, три вершины которого можно покрасить в один цвет, а три — в другой так, что любые две одноцветные вершины будут соединены ребром, а любые две разноцветные — нет. В графе циклов длины 4, потому что цвета вершин в цикле чередуются, и по две вершины каждого цвета в можно выбрать способами. Отсюда получается пример на 27 циклов: достаточно взять три графа , а из двух оставшихся вершин рёбер не проводить.

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

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

Пусть в нашем графе ровно компонент связности вида . Тогда в нём вершин, входящих в «плохие» компоненты, где через каждое ребро проходит не более 3 циклов длины 4. В этих компонентах не более рёбер и, стало быть, не более циклов длины 4, а всего в графе этих циклов не больше, чем . Если же в графе 3 компоненты связности вида , то в этих компонентах 27 циклов длины 4 , а две оставшиеся вершины, не будучи связанными с остальными 18 -ю, новых циклов длины 4 добавить не могут. Итак, циклов длины 4 у нас всегда не более 27.

Отметим в нашем графе любую вершину и построим дерево поиска в глубину с корнем .

Отметим в нашем графе любую вершину и построим дерево поиска в глубину с корнем .

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

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