|
|
 |
Условие
У Пети есть колода из 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 \leqslant 9$, то на всей доске останется не более трёх нехороших пар, т.е. Вася "потеряет" не больше 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 баллов
