# Problem 8. (4 points)

Hansel and Gretel are playing a game, with Hansel going first. They take turns placing tokens on a $7 \times 8$ grid (7 rows and 8 columns). Each time Gretel places a token, she earns 4 points for each token already in the same row and 3 points for each token already in the same column.

Only one token can be placed on each cell. The game ends when all cells on the board are filled.

What is the maximum number of points Gretel can score regardless of Hansel's actions?
# Answer: 700

## Solution:

Let's say that Hansel also earns points according to the same principle as Gretel. In this case, each pair of cells in the same row will ultimately give one of the players 4 points, and each pair of cells in the same column will give 3 points. In one row, there are $\frac{8 \cdot 7}{2}=28$ pairs of cells, and in one column, there are $-\frac{7 \cdot 6}{2}=21$ pairs. The total score accumulated by both players at the end of the game will be $7 \cdot 28 \cdot 4 + 8 \cdot 21 \cdot 3 = 1288$.

We can present a strategy for Gretel that allows her to gain 4 more points with each move than Hansel did before. For this, we can divide each row into 8 rectangles of $1 \times 2$. As soon as Hansel places a token in one of the cells of a rectangle, Gretel immediately occupies the second one. The columns in which these cells are located are identical due to Gretel's strategy, and in the row, by the time of her move, there is one more token—exactly the one placed by Hansel.

On the other hand, if Hansel always chooses the cell that yields the maximum number of points, Gretel can, with her next move, score at most 4 more points, since adding one token by Hansel increases the "value" of each of the remaining cells by no more than 4.

Each player will make 28 moves, and with the correct play, Gretel will score 112 more points. Knowing the sum and difference of two numbers, it is easy to find the numbers themselves, which are 700 and 588.

In all other scenarios, the second player always scores more points per token in a row of even length, so the described strategy for the second player always works.