Задачи о фокусниках и теоремы Холла и Шпернера

Квант 2019, №2 с. 15, 17, 22, 23 Тег CBDG

А.ЭВНИН

Теорема Холла

В популярной математической литературе широкую известность получила следующая задача. Задача о свадьбах. Имеется множество юношей, каждый из которых знаком с некоторыми девушками. При каких условиях можно одновременно поженить всех юношей так, чтобы каждый из них женился на знакомой ему девушке? Ответ таков: задача разрешима тогда и только тогда, когда любые k юношей из данного множества знакомы в совокупности не менее чем с k девушками. Заметим, что необходимость здесь очевидна. Действительно, если для каких-то k юношей число потенциальных невест меньше k, то уже этих k юношей одновременно поженить не удастся. Достаточность доказывается не так просто! Для того чтобы сформулировать задачу о свадьбах на математическом языке, приведем некоторые определения из теории графов [1]. Вершины графа – смежные, если они соединяются ребром. Ребра графа называются смежными, если у них есть общая вершина, и несмежными в противном случае. Попарно несмежные ребра графа образуют паросочетание. Например, в графе на рисунке 1 можно указать несколько паросочетаний из четырех ребер. Одно из них ^ $aa_{1}, bb_{1}, cc_{1}, dd_{1}$ `. Пусть $G V_{1}, V_{2}$ – двудольный граф с долями $V_{1}$ и $V_{2}$ (в этом графе любое ребро соединяет некоторую вершину из $V_{1}$ с некоторой вершиной из $V_{2} ).$ Совершенным паросочетанием из $V_{1}$ в $V_{2}$ называется паросочетание в этом графе, покрываю-

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

Рис. 1

щее $V_{1}$ (т.е. для всякой вершины из $V_{1}$ в паросочетании найдется выходящее из нее ребро). Например, на рисунке 2 изображен граф с долями $V_{1}$ ^ $x_{1}, x_{2}, x_{3}$ ` и

Рис. 2

$V_{2}$ ^ $y_{1}, y_{2}, y_{3}, y_{4}$ `. Ребра $x_{1} y_{1}, x_{2} y_{2}$ и $x_{3} y_{4}$ образуют совершенное паросочетание из $V_{1}$ в $V_{2}$ . Пусть G – граф с множеством вершин V, а A – подмножество V. Окружением множества A называют множество

$\cup$ * v, v A где * v – множество вершин, смежных с v.

ЗАДАЧИ

ФОКУСНИКАХ

ТЕОРЕМЫ

Напомним также, что мощность конечного множества – это число его элементов. Теперь решение задачи о свадьбах может быть сформулировано следующим образом. Теорема 1 (Ф.Холл, 1935 г.). Совершенное паросочетание из $V_{1}$ в $V_{2}$ в двудольном графе $G V_{1}, V_{2}$ существует тогда и только тогда, когда для любого множества A $V_{1}$ мощность его окружения не меньше мощности A, т.е. * A t A. Четыре разных способа доказательства теоремы Холла можно найти в книге [2].

Достаточное условие

В данной статье речь пойдет об одном (простом, но малоизвестном) достаточном условии существования совершенного паросочетания в двудольном графе. Теорема 2. Пусть в непустом (т.е. имеющем хотя бы одно ребро) двудольном графе $G V_{1}, V_{2}$ степень любой вершины из доли $V_{1}$ не меньше степени любой вершины из доли $V_{2}$ . Тогда в этом графе существует совершенное паросочетание из $V_{1}$ в $V_{2}$ . Доказательство. Пусть q – число, которое не больше степени любой вершины из $V_{1}$ и не меньше степени любой вершины из $V_{2}$ . Возьмем произвольные k вершин первой доли $b_{1}, b_{2}$ , … $, b_{k}$ и смежные с ними вершины $g_{1}, g_{2}$ , … $, g_{l}$ второй доли. Рассмотрим порожденный этими k + l вершинами подграф G c исходного графа (в G c входят указанные вершины и все ребра между ними, имеющиеся в исходном графе). Ясно, что в графе G c степень любой вершины из первой доли не меньше q, а из второй не больше q. Число ребер двудольного графа равно сумме степеней вершин любой из его долей. Поэтому k kq d ¦ deg $b_{i}$ i 1 l

¦ deg $g_{j} d lq$ , j 1 откуда k d l. Таким образом, выполнены условия теоремы Холла о существовании совершенного паросочетания в двудольном графе.

ХОЛЛА

ШПЕРНЕРА

Граф называется регулярным, если степени всех его вершин равны между собой. Назовем двудольный граф полурегулярным, если в каждой доле степени всех ее вершин равны между собой. Извлечем из теоремы 2 следующие следствия. Следствие 1. В любом непустом регулярном двудольном графе существует совершенное паросочетание. Следствие 2. В непустом полурегулярном двудольном графе $G V_{1}, V_{2}$ совершенное паросочетание существует тогда и только тогда, когда в доле $V_{1}$ вершин не больше, чем в $V_{2}$ . Доказательство. Необходимость очевидна. Достаточность. Пусть в $V_{1}$ и $V_{2}$ степени вершин равны a и b соответственно. Подсчитав двумя способами количество ребер в двудольном графе, получим $a V_{1} b V_{2}$ . Учитывая неравенство $V_{1} d V_{2}$ , отсюда получаем, что a t b. Осталось воспользоваться теоремой 2.

Задачи о фокусниках

Имеется ряд задач, которые легко решаются с помощью теоремы 2 и следствий из нее. Фабула этих задач такова. Зрители предъявляют ассистенту фокусника некоторый случайным образом выбранный объект (например, несколько игральных карт), после чего ассистент по своему выбору как-то изменяет этот объект. Далее фокусник по новому объекту восстанавливает исходный. Построим двудольный граф $G V_{1}, V_{2}$ следующим образом. Пусть вершины из $V_{1}$ – это всевозможные конфигурации, которые зрители могут предъявить ассистенту фокусника, а вершины из $V_{2}$ – те конфигурации, которые может получить ассистент. Если из конфигурации a $V_{1}$ может быть получена конфигурация b $V_{2}$ , то в графе должно быть ребро ab; других ребер в графе нет. Если в данном графе существует совершенное паросочетание из $V_{1}$ в $V_{2}$ , то фокусник с ассистентом, используя его, смогут осуществить фокус: фокусник по конфигурации b однозначно определит конфигурацию a.

ЗАДАЧИ

ФОКУСНИКАХ

ТЕОРЕМЫ

Задача 4. Зритель пишет на доске слева направо n цифр. Помощник фокусника закрывает одну из цифр красной карточкой, другую синей, еще одну зеленой. После этого входит фокусник и называет закрытые цифры. При каком наименьшем n такой фокус возможен? Ответ: при n = 12. Решение. Пусть $V_{1}$ и $V_{2}$ – множества тех «картинок», которые могут увидеть помощник и фокусник соответственно. Рассмотрим двудольный граф $G V_{1}, V_{2}$ , ребра которого описывают возможные переходы от картинок из $V_{1}$ к картинкам из $V_{2}$ . Граф полурегулярный, $V_{1} 10^{n}, V_{2} n n 1 n 2$ • $10^{n} 3$ . По следствию 2, для существования совершенного паросочетания из $V_{1}$ в $V_{2}$ необходимо и достаточно, чтобы в доле $V_{2}$ вершин было не меньше, чем в $V_{1}$ . Отсюда $n n 1 n 2 t t 10^{3}$ , что равносильно неравенству n t 12. Таким образом, наименьшее значение n равно 12. Покажем, как фокус осуществить практически при n t 12. Места, где записаны первые 12 цифр, пронумеруем слева направо: 1, 2, …, 9, 0, 11, 12 (остальные места, если они есть, не нумеруем!). Пусть S – сумма всех записанных зрителем цифр. Будем действовать за помощника следующим образом. Закроем красной карточкой место, номер которого является последней цифрой числа S, после чего мысленно удалим это место, а синей карточкой закроем место с номером, равным цифре, которая спрятана под красной карточкой. Затем зеленой карточкой закроем место, номер которого (вычисленный после «удаления» цифр, находящихся под красной и синей карточками) спрятан под синей карточкой. Теперь фокусник по положению зеленой карточки поймет, какая цифра под синей, а по положению синей карточки – какая цифра под красной. Все цифры, кроме той, которая под зеленой карточкой, уже известны фокуснику, а положение красной карточки говорит о последней цифре суммы всех цифр, записанных зрителем. Поэтому фокусник сможет определить цифру и под зеленой карточкой.

ХОЛЛА

ШПЕРНЕРА

Задачи для самостоятельного решения

Приведем подборку $задач^{1}$ , при решении которых возможно применение теоремы Холла. Некоторые задачи совсем простые (решаются простой ссылкой, например, на следствие 1; нужно лишь увидеть соответствующий двудольный граф!), некоторые предлагались на школьных и студенческих олимпиадах различного уровня. Задачи 11–15 посвящены доказательству и применениям теоремы Шпернера.

Имеется бесконечное множество юношей и бесконечное множество девушек. Для любого натурального числа k верно, что любые k юношей знакомы в совокупности не менее чем с k девушками. Верно ли, что всех юношей удастся одновременно поженить на знакомых им девушках? Другими словами, справедлива ли теорема Холла в случае бесконечного графа? 2. Решите задачу 1 в предположении счетности $^{2}$ множеств юношей и девушек. 3. В некотором районе, состоящем из нескольких деревень, число женихов равно числу невест. В каждой деревне общее число женихов и невест не больше половины общего их числа. Докажите, что можно всех переженить так, чтобы в каждой паре жених и невеста были из разных деревень. 4. Однокруговой волейбольный турнир 2n команд продолжался 2n – 1 дней. Каждый день проходило n игр, каждая команда в один день проводила ровно одну игру. По окончании турнира организаторы решили наградить тортами некоторые команды: за каждый игровой

1 Задача 3 предлагалась на III этапе Россий- ской олимпиады школьников 1995 года, задача 4 – на Putnam Competition 2012 года, задача 14 – на Московской олимпиаде 2017 года, задача 15 – на Открытой олимпиаде ФМЛ 239 в 2004 году. Остальные задачи взяты из сборников [3, $4].^{2}$ Множество называется счетным, если существует взаимно однозначное соответствие между ним и множеством натуральных чисел (другими словами, элементы данного бесконечного множества можно пронумеровать натуральными числами). Счетными являются множества натуральных чисел, неотрицательных целых чисел, целых чисел, рациональных чисел.

КВАН T 2019/№2

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

Вместо клеток будем рассматривать их центры, которые назовем узлами. Таким образом, у нас есть конечное множество изначально черных узлов и шаблон – множество центров клеток бумажного многоугольника M. В задаче происходит следующий процесс: если удается положить шаблон так, что из его узлов ровно один узел белый, то этот узел мы можем перекрасить в черный цвет. Зафиксируем некоторое положение шаблона $K_{0}$ и проведем вертикальную прямую через самой левый узел, принадлежащий $K_{0}$ (рис.1). (Поскольку мы не знаем,

Рис. 1

черные или белые узлы попали в $K_{0}$ , на рисунке 1 они изображены третьим цветом – красным.) Если эта прямая не содержит других узлов шаблона, то будем поворачивать прямую по часовой стрелке до тех пор, пока на нее не попадет еще один узел, принадлежащий $K_{0}$ . Мы нашли для нашего шаблона так называемую опорную прямую l, содержащую не менее двух узлов шаблона, такую, что все узлы шаблона лежат в одной полуплоскости L относительно прямой l. Теперь перенесем параллельно прямую l вместе с полуплоскостью L так, чтобы полуплоскость накрыла все изначально

Рис. 2

черные узлы (рис.2). При этом прямая l перешла в некоторую прямую m, параллельную прямой l. Докажем, что все изначально белые узлы, лежащие в противоположной полуплоскости относительно m, всегда будут оставаться белыми. Предположим противное и рассмотрим момент, когда первый такой узел A стал черным. Значит, он накрыт сдвигом K нашего шаблона. Проведем через A прямую a, параллельную прямой l. По одну сторону от a все узлы по-прежнему белые (так как A – единственный перекрашиваемый узел), значит, a – опорная прямая для K. Но тогда сдвиг, переводящий K в $K_{0}$ , переводит прямую a в l, следовательно, на прямой а помимо A лежит еще хотя бы один узел, принадлежащий K. Как мы видим, в момент перекраски узла A шаблон K накрывает хотя бы два белых узла. Получаем противоречие, завершающее решение задачи. Замечание. Как видим из решения, шаблон может быть произвольным, поэтому связность многоугольника M из условия задачи не важна. Также из решения задачи несложно вывести, что если шаблон не помещается ни в горизонтальный, ни в вертикальный ряд, то процесс перекраски будет конечным (т.е. в итоге на плоскости будет конечное число клеток). Отметим, что задача имеет естественное обобщение на пространственную решетку (в аналогичном процессе разрешается перекрасить два белых узла) или решетку конечномерного пространства. Д.Захаров

$M2537^{*}$ . На числовой оси отмечено бесконечно много точек с натуральными коор-

ЗАДАЧНИК

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

Разделим окружность колеса на n = 720 дуг величиной 0,5q и покрасим каждую дугу в свой цвет (концы дуг не красим). Прокатим колесо по прямой так, чтобы ноль соответствовал границе между 1-м и n-м цветами. Считаем, что каждая точка прямой окрашивается в цвет дуги, которая по точке проезжает. Тогда прямая разобьется на интервалы n разных цветов, соответствующих дугам. Нам надо найти такой радиус R, или такую длину колеса S 2 S R, чтобы для каждого из n цветов нашлась отмеченная точка этого цвета. Допустим, мы уже подобрали такое S, что для некоторого k < n выполнено следующее k-условие: для 1-го, 2-го, …, k-го цветов имеется отмеченная точка этого цвета. Для выполнения 1-условия возьмем такое достаточно большое S, чтобы первый отрезок 1-го цвета покрыл отмеченную точку. Покажем, что, сохраняя k-условие, можно немного изменить длину колеса так, чтобы некоторая отмеченная точка оказалась окрашенной в k 1 -й цвет, т.е. чтобы стало выполнено k 1 -условие. Повторяя эту процедуру, мы в конце концов добьемся выполнения n-условия, что нам и требуется. Итак, пусть для некоторой длины колеса S выполнено k-условие при некотором k < n. Зафиксируем по отмеченной точке каждого из цветов 1, 2, …, k. Небольшое изменение длины колеса соответствует гомотетии прямой с центром в точке 0 и коэффициентом, близким к 1. Понятно, что можно выбрать коэффициент гомотетии настолько близким к 1, что картина для наших зафиксированных k отмеченных точек не изменится: все они останутся внутри «растянутых» интервалов того же цвета. Итак,

«КВАНТА»

найдется такое H! 0, что при длине колеса, принадлежащей интервалу S; S 1 H для 1-го, 2-го, …, k-го цветов, по-прежнему найдется отмеченная точка этого цвета. Теперь рассмотрим «достаточно далекую» отмеченную точку Z, нам будет подходить Z! S 1 H H. Рассмотрим раскраску прямой после того, как прокатили колесо длины S. На интервале Z S; Z колесо сделало полный круг, поэтому на нем обязательно найдется точка T k 1 -го цвета. Теперь увеличим длину колеса в Z T раз. Если прокатить колесо новой длины ZS T, то точка Z станет k 1 -го цвета. Поскольку

1 Z T Z Z S

1 S Z S 1 H, k-условие сохранится. Этим завершается решение. Замечание. Как видно из решения, условие, что отмеченные точки имеют натуральные координаты, может быть ослаблено. Достаточно лишь, чтобы множество отмеченных точек было неограниченным сверху. И.Митрофанов, П.Кожевников

Ф2541. С вершины горизонтального цилиндра без начальной скорости скатывается небольшой обруч (отношение радиуса обруча к радиусу цилиндра – малая величина). Коэффициент трения между поверхностями цилиндра и обруча P = 1. При каком угле между вертикалью и линией, проходящей через центр обруча и ось цилиндра (рис.1), начнется проскаль- Рис. 1 зывание обруча по цилиндру? При каком угле между теми же линиями произойдет отрыв обруча от цилиндра?

Движение обруча разделяется на два этапа: без проскальзывания и с проскальзыванием, когда вращение обруча отстает от поступательного движения центра масс. Рассмотрим сначала первый этап движе-