Evdokimov M.A.

Polina has a deck of 36 cards (4 suits with 9 cards each). She chooses half of the cards she wants and gives them to Vasilisa, and keeps the other half for herself. Each turn, the players take turns opening one card of their choice (the opponent sees the suit and rank of the opened card), starting with Polina. If, in response to Polina's move, Vasilisa can place a card of the same suit or rank, Vasilisa earns one point. What is the maximum number of points Vasilisa can guarantee to earn?
If Polina takes all the hearts, all the aces, all the kings, and all the queens, then Vasilisa will not be able to score points on the ace, king, and queen of hearts, i.e., she will score no more than 15 points.

Now let's prove that for any choice of Polina, Vasilisa can earn at least 15 points. Lay out the cards in the cells of a table $\$ 4|t| t) s 9$ (in one column, cards of the same rank, in one row - cards of the same suit). We will prove that if Polina has colored 18 cells black, then Vasilisa can select at least 15 non-overlapping good pairs: in each pair, two cells of different colors are in the same row or the same column. (Then Vasilisa, on the move with one card from the pair, can respond with the move of the second card from this pair and earn 15 points.)

Let's call the type of a column the number of black cells in it. First, Vasilisa considers columns of type 2 (if they exist). Each of them, obviously, can be divided into two good pairs.

Next, Vasilisa considers pairs of columns of type 0 and 4. Each such pair, obviously, can be divided into four good pairs of cells.

Next, Vasilisa considers pairs of columns of type 1 and 3. Each such pair can also be divided into four good pairs of cells (see fig.).
![](https://cdn.mathpix.com/cropped/2024_05_06_9679ad1f313293fa9503g-23.jpg?height=376&width=462&top_left_y=1671&top_left_x=14)

When the specified pairs of columns are exhausted, by symmetry, we can assume that the "unprocessed" columns will be of types 4 and 1. If there are \$a\$ columns of type 4 and $\$ \mathrm{~b} \$$ columns of type 1, then $\$ 4 \mathrm{a}+\mathrm{b}=3 \mathrm{~b} \$$, i.e., $\$ \mathrm{~b}=2 \mathrm{a} \$$. In a triplet consisting of a column of type 4 and two columns of type 1, Vasilisa can select at least five good pairs of cells (see fig.).
![](https://cdn.mathpix.com/cropped/2024_05_06_9679ad1f313293fa9503g-23.jpg?height=380&width=638&top_left_y=2245&top_left_x=10)

Since $\$ 3 \mathrm{a}=\mathrm{a}+\mathrm{b} \backslash \mathrm{le}$ 9\$, there will be no more than three bad pairs on the entire board, i.e., Vasilisa will "lose" no more than 3 points.

## Comment.

Consider the following graph. The cards will be vertices, and edges will connect pairs of cards of the same suit or the same rank. Then the game consists of Polina dividing this graph into two equal parts (by removing edges between
the following theorem.

Theorem (Hall). If in a bipartite graph any $\$ \mathrm{k} \$$ vertices of one part are connected to at least $\$ k \$$ vertices of the other, then the graph can be divided into pairs.