Alice has a deck of $36$ cards, $4$ suits of $9$ cards each. She picks any $18$ cards and gives the rest to Bob. Now each turn Alice picks any of her cards and lays it face-up onto the table, then Bob similarly picks any of his cards and lays it face-up onto the table. If this pair of cards has the same suit or the same value, Bob gains a point. What is the maximum number of points he can guarantee regardless of Alice’s actions? Mikhail Evdokimov
Problem
Source: Tournament of Towns, Junior A-Level Paper, Spring 2020 , p6
Tags: combinatorics, game
Pathological
10.06.2020 22:10
We claim the answer is $\boxed{15}.$ We can rephrase the problem as follows. Alice and Bob are playing a game on a $4 \times 9$ grids. Alice will select $18$ of the grid's cells to color black. Bob will then attempt to pair up as many pairs of squares which are differently colored and lie in the same row or column as possible. Find the maximum number of pairs that Bob can guarantee, regardless of which cells Alice colors. First we will see that Alice can prevent Bob from getting more than $15$ pairs. Indeed, if Alice simply colors the upper-left $3 \times 6$ grid black, Bob cannot pair the three squares in the lower-right $1 \times 3$ and hence can only get at most $15$ pairs. Now, we will show that Bob can always get at least $15$ pairs. For $0 \le i \le 4$, let $x_i$ be the number of columns with exactly $i$ black squares, so that $x_0 + x_1 + x_2 + x_3 + x_4 = 9.$ Note that Bob can pair up all the squares in a column with $2$ black squares. Also, Bob can always pair up all the squares in any two columns with a total of $4$ black squares (easy to check). In view of the above, if $x_0 = x_4$, then $x_1 = x_3$ and so we are done. From here, it's not hard to deduce that Bob can leave at most $6$ squares unpaired, and we're done. $\square$