
Problem 5. There is an empty table with $2^{100}$ rows and 100 columns. Alice and Eva take turns filling the empty cells of the first row of the table, Alice plays first. In each move, Alice chooses an empty cell and puts a cross in it; Eva in each move chooses an empty cell and puts a zero. When no empty cells remain in the first row, the players move on to the second row, and so on (in each new row Alice plays first).

The game ends when all the rows are filled. Alice wants to make as many different rows in the table as possible, while Eva wants to make as few as possible. How many different rows will be there in the table if both follow their best strategies?

(Denis Afrizonov)

Answer: $2^{50}$.


Solution. First, we prove that Eva can achieve there to be no more than $2^{50}$ different rows. Eva can divide every row into 50 "domino" rectangles $1 \times 2$. When Alice puts a cross in one cell of a domino, Eva puts a zero in another cell of the same domino. Upon the completion of each row
every domino will be one of two types (cross-zero or zero-cross), so there will be no more than $2^{50}$ different rows.

Next, let us prove that Alice can achieve at least $2^{50}$ different rows. It is sufficient to show that as long as there are less than $2^{50}$ already filled rows, Alice can make the next row different from all the previous ones.

Consider the next ("new") row that the players fill out. Let's call toxic those rows among the previously filled ones that match the new row by the symbols that are already filled in it. (Thus, before Alice's first move in the new row, all the previously filled rows will be toxic.) Let us prove that with each of her moves, Alice can reduce the number of toxic rows by half. If initially this number was less than $2^{50}$, then at the end it will be less than 1 , that is, the new row will not match any of the previous ones.

Suppose that Alice and Eve have each made $i$ moves in the new row. Let us denote the current number of toxic rows by $T$. Each of them matches a new row by $i$ crosses; hence, $50-i$ crosses in a toxic row are located above empty cells of the new row. Then there are exactly $(50-i) T$ crosses in toxic rows over these empty cells. There are $100-2 i$ empty cells; by the pigeonhole principle, there is an empty cell over which there are at most $\frac{1}{2} T$ crosses. This is the cell in which Alice should put a cross with her $(i+1)$-th move.

## Marking scheme

The sum of the following points is taken:

5 p. for proving that Alice can achieve $\geq 2^{50}$ different rows.

2 p. for proving that Eva can achieve $\leq 2^{50}$ different rows.

The following advancement is not awarded with points:

$0 \mathrm{p}$. for the correct answer without further reasoning.
