IMO 1994 SL C1

Origin: UKR | Category: Combinatorics

Problem

On a 5 \times 5 board, two players alternately mark numbers on empty cells. The first player always marks 1’s, the second 0’s. One number is marked per turn, until the board is filled. For each of the nine 3 \times 3 squares the sum of the nine numbers on its cells is computed. Denote by A the maximum of these sums. How large can the first player make A, regardless of the responses of the second player?

Solution

Call the first and second player M and N respectively. N can keep A \leq6. Indeed, let 10 dominoes be placed as shown in the picture, and when- ever M marks a 1 in a cell of some domino, let N mark 0 in the other cell of that domino if it is still empty. Since any 3 \times 3 square con- tains at least three complete domi- a b c d e 1 2 3 4 5 noes, there are at least three 0’s inside. Hence A \leq6. We now show that M can make A = 6. Let him start by marking 1 in c3. By symmetry, we may assume that N’s response is made in row 4 or 5. Then M marks 1 in c2. If N puts 0 in c1, then M can always mark two 1’s in b \times {1, 2, 3} as well as three 1’s in {a, d} \times {1, 2, 3}. Thus either {a, b, c} \times {1, 2, 3} or {b, c, d} \times {1, 2, 3} will contain six 1’s. However, if N does not play his second move in c1, then M plays there, and thus he can easily achieve to have six 1’s either in {a, b, c} \times {1, 2, 3} or {c, d, e} \times {1, 2, 3}.