Evdokimov M.A.

Petya has a deck of 36 cards (4 suits with 9 cards each). He chooses half of the cards (whichever he wants) and gives them to Vasya, while keeping the other half for himself. Each turn, the players take turns laying one card on the table (of their choice, face up); Petya goes first. If, in response to Petya's move, Vasya can lay a card of the same suit or rank, Vasya earns

1 point. What is the maximum number of points Vasya can guarantee to earn?
If Petya takes all the hearts, all the aces, kings, and queens, then Vasya will not be able to score points on the ace, king, and queen of hearts, i.e., he will score no more than 15 points.

Let's rephrase the problem. Consider a $4 \times 9$ board. Petya colors 18 cells black. We need to prove that Vasya can select at least 15 non-overlapping good pairs: in each pair, the two cells are of different colors and are in the same row or column.

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

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

Next, Vasya considers pairs of columns of type 1 and 3 (see figures). Each such pair can also be split into four good pairs of cells (see figures).
![](https://cdn.mathpix.com/cropped/2024_05_06_309dcf72bd08bf7391b4g-30.jpg?height=226&width=378&top_left_y=2151&top_left_x=840)

When the specified pairs of columns are exhausted, by symmetry, we can assume that only columns of types 4 and 1 remain unprocessed. 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 one column of type 4 and two columns of type 1, Vasya can select at least five good pairs of cells (see figures).
![](https://cdn.mathpix.com/cropped/2024_05_06_309dcf72bd08bf7391b4g-30.jpg?height=226&width=500&top_left_y=2585&top_left_x=778)

Since $3a = a + b \leq 9$, there will be no more than three non-good pairs on the entire board, i.e., Vasya will "lose" no more than 3 points.
$[\quad$ Sequences (miscellaneous).
Difficulty: 4
Problem