Комбинаторика на ММО: графы, турниры, логика, конструктивы

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

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

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

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

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

Когда указанные пары столбцов закончатся, в силу симметрии можно считать, что “необработанными” останутся только столбцы типов и Если это столбцов типа и столбцов типа то т. е. В тройке из столбца типа и двух столбцов типа Василиса сможет выделить не менее пяти хороших пар клеток (см. рисунок справа).

Так как то на всей доске останется не более трёх нехороших пар, т. е. Василиса «потеряет» не больше очков.