Многократная лемма Холла в задачах про мудрецов

МАТЕМАТИЧЕСКИЙ КРУЖОК

Многократная лемма Холла в задачах про мудрецов

М.ШЕВЦОВА

Введение

Задачи, связанные с кооперативными алгоритмами (проще говоря, задачи о мудрецах) традиционно считаются довольно трудными. Дело в том, что зачастую придумать соответствующую стратегию действий, гарантирующую мудрецам успех (например, при отгадывании цветов колпаков, которые на них надеты), весьма непросто; нет какихто общих соображений, позволяющих строить нужные стратегии. Конечно, есть стандартные идеи нумерации, кодирования и т.д., но как именно занумеровать, закодировать и передать тем самым нужную информацию, приходится каждый раз придумывать заново. В этой статье мы расскажем об интересном подходе к подобным задачам, при котором придумывать подобные стратегии действий не нужно. Это кажется невероятным, но есть способ доказать существование стратегии, не предъявляя ее явно! Те же идеи применимы к задачам о фокусниках: можно доказать возможность фокуса, не раскрывая способ его проведения! Как это можно сделать, мы узнаем, познакомившись с классическим комбинаторным результатом: леммой Холла.

Обычная и многократная леммы Холла

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

DOI: https://doi.org/10.4213/kvant20190705

ему девушкой. Спрашивается, смогут ли все юноши пригласить на танец знакомых им девушек? Оказывается, что существует простое необходимое и достаточное условие, при выполнении которого каждому юноше найдется пара (хотя, возможно, какие-то девушки при этом останутся без пары). В этом и заключается суть леммы Холла. Теорема 1. Лемма Холла. Рассмотрим двудольный граф, где вершины первой доли – это юноши, а вершины второй доли – девушки. Соединим ребром юношу и девушку, если они знают друг друга. Предположим, что любые k юношей знают не меньше k девушек, для любого k от 1 до общего количества юношей. Тогда все юноши смогут пригласить на танец знакомых им девушек. Есть много разных способов доказать лемму Холла. Мы приведем классическое доказательство, которое еще называется методом чередующихся цепей. Другие доказательства можно найти в статье [1]. Доказательство. Предположим противное: пусть все юноши не смогут танцевать со знакомыми им девушками. Рассмотрим наибольшее количество танцующих пар, которое можно образовать. Далее рассмотрим юношу, не вошедшего в эти пары. Он начинает организовывать свое тайное общество. В первый день в этом обществе только он. Каждый следующий день каждый юноша, входящий в это общество, приглашает туда всех знакомых с ним девушек, а они приводят туда своих партнеров по танцу (если таковые есть).

Упражнения

1. Докажите, что рано или поздно в общество придет девушка, у которой не было пары. 2. Докажите, что в таком случае можно разбить юношей и девушек на пары так, чтобы количество пар увеличилось. 3. Выведите отсюда лемму Холла.

Суть леммы Холла заключается в установлении соответствий между двумя типами объектов (юноши и девушки) при выполнении некоторых условий связи между этими объектами. В комбинаторике существует не так уж много подобных утверждений, и лемма Холла – возможно, наиболее мощное из них. Чтобы потренироваться ее применять, попробуйте решить следующие задачи.

28

КВАН T 2019/№7

Упражнения

4. Каждый из двух равновеликих квадратов разбит на 100 равновеликих частей. Докажите, что можно сложить эти квадраты в стопку и проткнуть в 100 точках так, чтобы каждая из 100 частей каждого из квадратов была проткнута. 5. Из шахматной доски вырезали 7 клеток. Докажите, что на оставшиеся клетки можно поставить 8 не бьющих друг друга ладей. Указание. Рассмотрите двудольный граф, вершины которого – это строки (первая доля) и столбцы (вторая доля) данной таблицы.

На практике мы будем использовать лемму Холла в очень конкретной ситуации, соответствующей так называемому регулярному двудольному графу. Сформулируем отдельно соответствующее утверждение, которое и будет ключевым при решении задач с мудрецами. Теорема 2. Лемма Холла для регулярного графа. Предположим, что для некоторого l > 0 каждый юноша знает ровно l девушек и каждая девушка знает ровно l юношей. Тогда все юноши смогут пригласить на танец знакомых им девушек. В терминах графов это утверждение звучит так: если в двудольном графе степени всех вершин одинаковы, то вершинам из одной доли можно сопоставить ровно по одной смежной вершине из другой доли. Доказательство. Рассмотрим произвольных k юношей и докажем, что они знают не менее k девушек (в таком случае наше утверждение следует из леммы Холла). Предположим, что k юношей знают x девушек. Посчитаем количество ребер, исходящих из этих k юношей, и количество ребер, входящих в знакомых им x девушек. Ясно, что ребер, выходящих из юношей, не больше, чем ребер, входящих в девушек. Тогда kl d xl, откуда x t k, что и требовалось доказать.

Упражнение 6. В частном охранном предприятии работают n охранников. Ежедневно им нужно распределяться по n объектам. По прошествии k дней оказалось, что никто дважды на одном объекте не дежурил. Докажите, что можно составить расписание на оставшиеся n – k дней так, чтобы все охранники подежурили по одному разу на всех объектах.

В дальнейшем нам будут важны идеи, связанные с применением леммы Холла для решения задач про фокусников. Мы приве-

дем лишь одну задачу на эту тему, отсылая заинтересованного читателя к статье [2]. Задача 1 (Всероссийская олимпиада по математике, 2007). Фокусник с помощником собираются показать такой фокус. Зритель пишет на доске последовательность из N цифр. Помощник фокусника закрывает две соседних цифры черным кружком. Затем входит фокусник. Его задача – отгадать обе закрытые цифры (и порядок, в котором они расположены). При каком наименьшем N фокусник может договориться с помощником так, чтобы фокус гарантированно удался? Ответ: 101. Решение. Перед тем, как переходить к решению, попробуем понять, как можно формализовать отгадывание фокусником начальной расстановки цифр. У нас есть множество начальных наборов из N цифр. Один из этих наборов пишет зритель – его и должен отгадать фокусник. Эти наборы составят первую долю в нашем двудольном графе. Сам фокусник при этом видит лишь часть этого набора с двумя закрытыми помощником цифрами. Эти наборы составят вершины второй доли двудольного графа. Это простое соображение, позволяющее ввести в нашу задачу двудольный граф, подсказывает оценку для числа N. Рассмотрим все вершины второй доли. Этих вершин в точности N 1 ˜ $10^{N} 2$. С другой стороны, вершин в первой доле ровно $10^{N}$. Ясно, что если вершин во второй доле меньше, чем в первой, то фокус не удастся. Действительно, в таком случае найдутся два стартовых набора из N цифр, которые после закрытия цифр дадут один и тот же набор, который увидит фокусник, поэтому угадать нужный набор он не сможет. Отсюда получаем ограничение на N:

N 1 ˜ $10^{N} 2 t 10^{N}$, откуда N t 101. Осталось привести алгоритм действий фокусника, чтобы он мог угадать закрытые цифры в последовательности длины $N_{0} 101$. Вот здесь мы и применим лемму Холла. Что нам нужно сделать? У нас есть вершины второй доли, которые видит фокусник, и вершины первой доли, которые загадал зритель. Нам нужно установить биекцию, т.е.

30

КВАН T 2019/№7

Теорема 4. Многократная лемма Холла в регулярном случае. Рассмотрим двудольный граф, где вершины первой доли – это юноши, а вершины второй доли – девушки. Соединим ребром юношу и девушку, если они знают друг друга. Предположим, что степени всех вершин, соответствующих юношам, одинаковы и равны m и степени всех вершин, соответствующих девушкам, также одинаковы и равны d. Докажите, что каждый юноша может станцевать с ª m º « ¬ d » ¼ знакомыми ему девушками, причем каждая девушка при этом будет танцевать не более одного раза.

Упражнение 7. Докажите эту теорему.

Мудрецы и многократная лемма Холла

Итак, мы выяснили, как доказывать возможность проведения фокусов с помощью леммы Холла: ключевым является соображение о возможности установления инъекции между множеством стартовых состояний, которые видит фокусник, и множеством конечных (загаданных зрителем) состояний, которые нужно отгадать. Инъекция – это такое соответствие, что разным стартовым состояниям сопоставлены разные конечные. Однако в задачах с мудрецами и кооперативными стратегиями ситуация более сложная. Во-первых, в подавляющем большинстве таких задач мудрецы могут (и должны) ошибаться, т.е. безошибочного отгадывания просто не существует. Во-вторых, возможность наличия ошибок делает неоднозначным процесс декодирования. Иначе говоря, конечная ситуация, которую можно получить из стартовой, не однозначна. Но у нас на такой случай как раз есть многократная лемма Холла! Ключевое соображение, позволяющее заставить многократную лемму Холла работать в задачах с мудрецами, заключается в следующем. Предположим, что мудрецам надели колпаки разных цветов и им нужно угадать цвет своего колпака, видя перед собой только колпаки других мудрецов. Занумеруем мудрецов и будем надевать на них колпаки всеми возможными способами. Вооружимся фотоаппаратом и начнем их фотографировать. Будем делать фотографию каждой ситуации сверху, чтобы были

видны все шапки, а затем передадим фотоаппарат каждому из мудрецов, чтобы он сам сделал фотографии всех остальных мудрецов, которых он видит со своего места. Рассмотрим двудольный граф, в котором вершины первой доли – это все фотографии, сделанные нами (по факту просто всевозможные начальные расположения колпаков на мудрецах), а вторая доля – это все фотографии, сделанные всеми мудрецами. Далее, соединим вершину v из второй доли с вершиной u из первой, если фотография v сделана одним из мудрецов в ситуации u. Что должны сделать мудрецы? Для каждой сделанной им фотографии мудрец должен постараться восстановить цвет своего колпака. Разумеется, в некоторых случаях мудрецы ошибутся. Нам нужно найти тех мудрецов, которые гарантированно ответят верно. Точнее говоря, следует равномерно распределить ответы всех мудрецов по фотографиям u, чтобы на каждую фотографию приходилось достаточное количество правильных ответов. Для этого воспользуемся многократной леммой Холла. Мудрецы, чьи точки зрения выбраны в соответствии с данной общей фотографией u, будут отвечать исходя из предположения, что они находятся в этой ситуации, а значит, правильно. Таким образом, если каждой фотографии u поставлено в соответствие хотя бы m фотографий $u_{1},......, u_{m}$, сделанных мудрецами, то в каждой ситуации правильно ответят хотя бы m мудрецов. Число m мы определим из параметров задачи. Посмотрим, как эта схема работает на практике. Задача 2 (Московская математическая олимпиада, 2010). Команда из n мудрецов участвует в игре: на каждого из них надевают шапку одного из k заранее известных цветов, а затем по свистку все мудрецы одновременно выбирают себе по одному шарфу. Команда получает столько очков, у скольких ее участников цвет шапки совпал с цветом шарфа (шарфов и шапок любого цвета имеется достаточное количество; во время игры каждый участник не видит своей шапки, зато видит шапки всех остальных, но не имеет права выдавать до свистка никакую информацию). Какое наибольшее число очков команда, заранее наме-

31

МАТЕМАТИЧЕСКИЙ

тив план действий каждого ее члена, может гарантированно получить? Ответ: > n k @. Решение. Рассмотрим описанный выше граф, в котором вершины первой доли – это всевозможные начальные позиции команды мудрецов (т.е. всевозможные варианты надеть на них шапки k цветов), а вершины второй доли – это фотографии, сделанные каждым из мудрецов в каждой возможной стартовой ситуации. Ясно, что в первой доле $k^{n}$, а во второй $nk^{n} 1$ вершин. Каждая вершина из первой доли соединена с n вершинами из второй доли, так как такую рассадку может видеть каждый из n мудрецов. С другой стороны, каждая вершина из второй доли соединена с k вершинами из первой доли, так как у каждого мудреца есть k вариантов цвета своего шарфа. Теперь построим алгоритм действий для мудрецов, при котором они гарантированно наберут > n k @ очков. Для этого достаточно доказать, что можно сопоставить каждой вершине из первой доли > n k @ вершин из второй доли. Воспользуемся многократной леммой Холла в регулярном случае. Применим эту лемму, сопоставив каждой начальной расстановке u мудрецов из первой доли m > n k @ вершин из второй доли. Именно эти мудрецы ответят правильно при начальной расстановке u. Таким образом, мудрецы могут гарантированно набрать > n k @ очков. Осталось доказать, что больше > n k @ очков гарантировать нельзя. На самом деле это также объясняется возможностью применения леммы Холла: если бы можно было сопоставить каждой вершине первой доли больше > n k @ вершин из второй доли, то во второй доле нам просто не хватило бы вершин. Формально это можно доказать так. Предположим, что есть такая стратегия за мудрецов, которая гарантирует хотя бы > n k @ 1 очков. Заметим, что ответ каждого мудреца однозначно определяется цветом шапок у остальных мудрецов. Поставим в соответствие каждой фотографии из первой доли точки зрения мудрецов, которые в данной ситуации отвечают правильно. Если для каждой раскраски их больше > n k @, то

$nk^{n} 1 t k^{n} > n k$ @ 1! $k^{n} > n k$ @ $nk^{n} 1$ – противоречие. Таким образом, максималь-

КРУЖОК

ное количество очков, набранных мудрецами, равно > n k @.

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

Упражнения

8. В условиях предыдущей задачи будем считать, что n < k. С какой максимальной вероятностью хотя бы один из мудрецов угадает цвет своей шапки? 9. В этот раз мудрецы пишут предполагаемый цвет своего колпака r раз, при этом они не видят, что написали их соседи. Какую максимальную вероятность того, что хотя бы один из них угадает за эти r попыток, могут гарантировать мудрецы?

Задача 3 (Олимпиада имени Леонарда Эйлера, 2013). 99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого (но заранее неизвестно, какого именно из двух цветов 50 колпаков, а какого – 49). Каждый из мудрецов видит цвета всех колпаков, кроме своего собственного. Все мудрецы должны одновременно написать (каждый на своей бумажке) цвет своего колпака. Смогут ли мудрецы заранее договориться отвечать так, чтобы не менее 74 из них дали верные ответы? Ответ: да. Решение. Понятно, что если мудрец видит 50 колпаков одного цвета, то у него колпак цвета, отличного от того, которого 50, т.е. он знает свой колпак. Значит, 49 мудрецов знают цвет своего колпака и ответят правильно. Оставшихся 50 мудрецов, которые видят 49 колпаков одного цвета и 49 другого, будем называть невезучими. Добьемся того, чтобы из невезучих мудрецов 25 каждый раз угадывали колпак правильно. Рассмотрим описанный выше граф, в котором вершины первой доли – это всевозможные позиции команды мудрецов, а вершины второй доли – это фотографии, сделанные каждым из невезучих мудрецов в каждой возможной стартовой ситуации. Каждая вершина из первой доли соединена с 50 из

(Продолжение см. на с. 34)