ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66555
Темы:    [ Числовые таблицы и их свойства ]
[ Теория графов (прочее) ]
Сложность: 6
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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

Решение

Если Полина возьмёт себе все черви, все тузы, всех королей и всех дам, то Василиса не сможет набрать очки на тузе, короле и даме червей, т.е. наберёт не больше 15 очков.

Теперь докажем, что при любом выборе Полины Василиса может заработать не меньше 15 очков. Выложим карты в клетки таблицы $4\times9$ (в одном столбце карты одного достоинства, в одной строке — карты одной масти). Докажем, что если Полина закрасила черным 18 клеток, то Василиса может выделить не менее 15 непересекающихся хороших пар: в каждой паре две клетки разного цвета, находящиеся в одной строке или одном столбце. (Тогда Василиса на ход одной картой из пары сможет отвечать ходом второй карты из этой пары и заработать 15 очков.)

Назовём типом столбца количество чёрных клеток в нём. Сначала Василиса рассматривает столбцы типа 2 (если они есть). Каждый из них, очевидно, разбивается на две хорошие пары.

Далее Василиса рассматривает пары столбцов типа 0 и 4. Каждая такая пара, очевидно, разбивается на четыре хорошие пары клеток.

Далее Василиса рассматривает пары столбцов типа 1 и 3. Каждая такая пара тоже разбивается на четыре хорошие пары клеток (см. рис.).

Когда указанные пары столбцов закончатся, в силу симметрии можно считать, что «необработанными» останутся только столбцы типов 4 и 1. Если это $a$ столбцов типа 4 и $b$ столбцов типа 1, то $4a + b = 3b$, т.е. $b = 2a$. В тройке из столбца типа 4 и двух столбцов типа 1 Василиса сможет выделить не менее пяти хороших пар клеток (см. рис.).

Так как $3a = a + b\le 9$, то на всей доске останется не более трёх нехороших пар, т.е. Василиса «потеряет» не больше 3 очков.

Комментарий.

Рассмотрим следующий граф. Карты будут вершинами, а ребрами соединим пары карт одной масти или одного достоинства. Тогда игра заключается в том, что Полина делит этот граф на две равные доли (удаляя рёбра между вершинами, попавшими в одну долю), а Василиса ищет в нём наибольшее паросочетание. Помочь в этом может следующая теорема.

Теорема (Холл). Если в двудольном графе для любого натурального $k$ любые $k$ вершин одной из долей связаны по крайней мере с $k$ вершинами другой, то граф разбивается на пары.

Задача Василисы — найти наибольший подграф, для которого условия теоремы Холла выполняются. Это можно сделать следующим образом. В одной из долей найдём наибольшую группу из $k$ вершин, для которой нарушаются условия теоремы Холла, то есть эта группа связана менее чем с $k$ вершинами из другой доли. Для этого необходимо, чтобы в другую долю попало не более $k-1$ карточек, у которых масть или достоинство совпадает с какой-то карточкой из этой группы. Тогда при условии, что $k \le 9$, всего карточек, у которых совпадает масть или достоинство, не менее $9 + 3k$, из них в первой доле должно быть не менее $9 + 3k - (k-1) = 10 + 2k$ карточек. Из неравенства $10 + 2k \le 18$ получаем, что $k \le 4$. Если $k \le 3$, то эту группу вершин выкинем из графа. Для оставшегося графа выполняются условия теоремы Холла. Если $k = 4$, то из такой группы (в силу того же неравенства) хотя бы одна вершина связана с вершиной из другой доли. Её и оставим, а оставшиеся три выкинем, и опять для оставшегося графа выполняются условия теоремы Холла. А если $k > 9$, то достаточно проделать всё то же самое для другой доли. Можно доказать, что там соответствующая группа будет содержать не более $9$ вершин.

Ответ

15.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 83
Год 2020
класс
Класс 8
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .