|
|
 |
Условие
У Пети есть колода из 36 карт (4 масти по 9 карт в каждой). Он выбирает из неё половину карт (какие хочет) и отдаёт Васе, а вторую половину оставляет себе.
Далее каждым ходом игроки по очереди выкладывают на стол по одной карте (по своему выбору, в открытом виде); начинает Петя. Если в ответ на ход Пети Вася смог выложить карту той же масти или того же достоинства, Вася зарабатывает
1 очко. Какое наибольшее количество очков он может гарантированно заработать?
Решение 1
Если Петя возьмёт себе все черви, все тузы, короли и дамы, то Вася не сможет набрать очки на тузе, короле и даме червей, т.е. наберёт не больше 15 очков.
Переформулируем задачу. Рассмотрим доску 4×9. Петя закрашивает чёрным 18 клеток. Докажем, что Вася сможет выделить не менее 15 непересекающихся хороших пар: в каждой паре две клетки разного цвета, находящиеся в одной строке или одном столбце.
Назовём весом столбца количество чёрных клеток в нём. Сначала Вася рассматривает столбцы типа 2 (если они есть). Каждый из них, очевидно, разбивается на две хорошие пары.
Далее Вася рассматривает пары столбцов типа 0 и 4. Каждая такая пара, очевидно, разбивается на четыре хорошие пары клеток.
Далее Вася рассматривает пары столбцов типа 1 и 3 (см. рисунки).
Каждая такая пара тоже разбивается на четыре хорошие пары клеток (см. рисунки).
Когда указанные пары столбцов закончатся, в силу симметрии можно считать, что "необработанными" останутся только столбцы типов 4 и 1. Если это a столбцов типа 4 и b столбцов типа 1, то 4a+b=3b, то есть b=2a. В тройке из столбца типа 4 и двух столбцов типа 1 Вася сможет выделить не менее пяти хороших пар клеток (см. рисунки).
Так как 3a=a+b⩽, то на всей доске останется не более трёх нехороших пар, т.е. Вася "потеряет" не больше 3 очков.
Решение 2
Воспользуемся известной леммой Холла о сватовстве (см. решение задачи 98160).
В терминах решения 1 объявим чёрные клетки юношами, белые – девушками, а знакомыми – клетки, находящиеся в одном ряду.
Докажем, что для каждой группы из k юношей (k = 1, 2, ..., 18) имеется по крайней мере k - 3 девушки, имеющих знакомых среди этой группы юношей. Добавив трёх виртуальных девушек, знакомых со всеми юношами, мы окажемся в условиях леммы Холла. Переженив всех юношей и отбросив не более чем троих, которым достались виртуальные девушки, получим не менее 15 хороших пар.
Пусть есть группа X из k юношей (чёрных клеток). Переставим столбцы, их содержащие, влево, а строки – вниз. Пересечение этих строк и столбцов – прямоугольник площади S_{1} – содержит X,
а дополнение к их объединению – прямоугольник площади S_{2} – содержит всех незнакомых с ними девушек. Значит, k \leqslant \min(S_{1}, 18), а количество знакомых с ними девушек не меньше 18 - \min (S_{2}, 18). Достаточно доказать, что 18 - \min(S_{2}, 18) \geqslant \min(S_{1}, 18) - 3, т.е. что \min(S_{1}, 18) + \min(S_{2}, 18) ≤ 21.
Выражение F = \min(S_{1}, 18) + \min(S_{2}, 18) симметрично, поэтому достаточно рассмотреть случай, когда общая вершина A построенных прямоугольников лежит в верхней половине доски. Тогда S_{2} \leqslant 18.
Отбросим очевидный случай, когда A лежит на границе доски (тогда S_{1} = 0 или S_{2} = 0). Если S_{1} < 18, можно сдвинуть A вправо, чтобы стало S_{1} = 18 (поскольку 18 делится как на 2,
так и на 3), при этом F = S_{1} + S_{2} не уменьшится. Если S_{1} > 18, можно сдвинуть A влево, чтобы стало S_{1} = 18, при этом F = 18 + S_{2} увеличится.
Остался единственный случай S_{1} = 18, S_{2} = 3, а в нём неравенство выполнено.
Ответ
15 очков.
Замечания
9 баллов
