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

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

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

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

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

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

Ответ: 148.

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

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

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

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

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

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

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

Пусть . Всего у 20 ребер 40 концов и легко понять, что есть не менее 12 ребер, концы которых не совпадают с другими концами наших 20 ребер. Выберем 5 таких ребер — пусть это ребра . Обозначим через множество, состоящие из вершин и произвольных 40 вершин не входящих в . Применим операцию ко всем 50 вершинам множества . Тогда на каждом из ребер образуется по 30 треугольников (со всеми вершинами, не входящими в ), а на каждом из 15 оставшихся ребер — по 50 треугольников (со всеми вершинами множества ). Итого получается треугольников.