Evoikinov 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 $4 \times 9$ table (cards of the same rank in one column, cards of the same suit in one row). 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 column. (Then Vasilisa can respond to a move with one card from the pair by playing 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 split into two good pairs.

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

Next, Vasilisa considers pairs of columns of type 1 and 3. Each such pair can also be split into four good pairs of cells (see the figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_ad217c05ea9ced24f8d2g-60.jpg?height=377&width=489&top_left_y=0&top_left_x=1)

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 $b$ columns of type 1, then $4a + b = 3b$, i.e., $b = 2a$. 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 the figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_ad217c05ea9ced24f8d2g-60.jpg?height=384&width=646&top_left_y=568&top_left_x=0)

Since $3a = a + b \leq 9$, there will be no more than three bad pairs left 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 rank. Then the game consists of Polina dividing this graph into two equal parts (by removing edges between vertices that end up in the same part), and Vasilisa finding the largest matching in it. The following theorem can help with this.

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