Найти граф

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

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

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

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

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

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

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

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

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

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

Доказательство и обсуждение см., например, в статьях: М. Большаков, «Паросочетания и транспортные сети («Квант» №4 за 1970 год); А. Романов, «Задачи и теоремы о представителях» («Квант» №1 за 2015 год); М. Шевцова, «Многократная лемма Холла в задачах про мудрецов» («Квант» № 7 за 2019 год)

В терминах решения 1 объявим чёрные клетки юношами (при этом ), белые девушками, а знакомыми — клетки, находящиеся в одном ряду. Мы докажем, что для каждой группы из юношей ( ) имеется по крайней мере девушки, имеющих знакомых среди этой группы юношей. Добавив трёх виртуальных девушек, знакомых со всеми юношами, мы окажемся в условиях леммы Холла. Переженив всех юношей и отбросив не более чем троих, которым достались виртуальные девушки, получим не менее 15 хороших пар.

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

Нам достаточно доказать, что , т.е. что .

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

Отбросим очевидный случай, когда лежит на границе доски (тогда или ). Если , то можно сдвинуть вправо, чтобы стало (поскольку 18 делится как на 2 , так и на 3 ), при этом не уменьшится. Если , то можно сдвинуть влево, чтобы стало , при этом увеличится.

Остался единственный случай , а в нём неравенство выполнено.

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

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

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

Ответ: 148.

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