Задача 088 — Задачи на Графы

У Пети есть колода из 36 карт ( 4 масти по 9 карт в каждой). Он выбирает из неё половину карт (какие хочет) и отдаёт Васе, а вторую половину оставляет себе. Далее каждым ходом игроки по очереди выкладывают на стол по одной карте (по своему выбору, в открытом виде); начинает Петя. Если в ответ на ход Пети Вася смог выложить карту той же масти или того же достоинства, Вася зарабатывает 1 очко. Какое наибольшее количество очков он может гарантированно заработать?

Подсказка

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

Решение

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

В терминах решения 1 объявим чёрные клетки юношами (при этом $n=18$ ), белые девушками, а знакомыми — клетки, находящиеся в одном ряду. Мы докажем, что для каждой группы из $k$ юношей ( $k=4,2, \ldots, 18$ ) имеется по крайней мере $k-3$ девушки, имеющих знакомых среди этой группы юношей. Добавив трёх виртуальных девушек, знакомых со всеми юношами, мы окажемся в условиях леммы Холла. Переженив всех юношей и отбросив не более чем троих, которым достались виртуальные девушки, получим не менее 15 хороших пар.

Пусть есть группа $X$ из $k$ юношей (чёрных клеток). Переставим столбцы, их содержащие, влево, а строки — вниз. Пересечение этих строк и столбцов — прямоугольник площади $S_{1}$ — содержит $X$ , а дополнение к их объединению — прямоугольник площади $S_{2}-$ содержит всех незнакомых с ними девушек. Значит, $k \leq \min \left(S_{1}, 18\right)$ , а количество знакомых с ними девушек не меньше $18-\min \left(S_{2}, 18\right)$ .

Нам достаточно доказать, что $18-\min \left(S_{2}, 18\right) \geq \min \left(S_{1}, 18\right)-3$ , т.е. что $\min \left(S_{1}, 18\right)+\min \left(S_{2}, 18\right) \leq 21$ .

Выражение $F=\min \left(S_{1}, 18\right)+\min \left(S_{2}, 18\right)$ симметрично, поэтому достаточно рассмотреть случай, когда общая вершина $A$ построенных прямоугольников лежит в верхней половине доски. Тогда $S_{2} \leq 18$ .

Отбросим очевидный случай, когда $A$ лежит на границе доски (тогда $S_{1}=0$ или $S_{2}=0$ ). Если $S_{1}<S_{2}$ , то можно сдвинуть $A$ вправо, чтобы стало $S_{1}=18$ (поскольку 18 делится как на 2 , так и на 3 ), при этом $F=S_{1}+S_{2}$ не уменьшится. Если $S_{1}>S_{2}$ , то можно сдвинуть $A$ влево, чтобы стало $S_{1}=18$ , при этом $F=18+S_{2}$ увеличится.

Остался единственный случай $S_{1}=18, S_{2}=3$ , а в нём неравенство выполнено.