Maths Olympiad Prep

Library / /66 of 69

, 2011

Combinatorics Difficulty 6.9 National Olympiad Prove it South Africa

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

Solution

First, notice that player two can always ensure that A6A \le 6. The squares of the grid can be partially tiled with 2×12 \times 1 tiles, as shown below. Whenever a 11 is placed inside a tile, player two can ensure that it also contains a 00. As every 3×33 \times 3 square contains three complete tiles, it will have at least three zeros in it so, A6A \le 6.

Figure 1

12321
24642
36963
24642
12321

Label each individual cell with the number of 3×33 \times 3 squares that contain it. By going for the highest-placed numbers, player 11 can get a total of 4545, which spread across 99 squares gives exactly 55. Let player 11 start by placing a 11 in the middle, and wlog, player two plays in the left side of the board. By placing a 11 directly right of the middle (value 66), player two is forced to take the right-most cell in the middle row (else player 11 will, and there will exist a 3×33 \times 3 square with three 11s and 66 empty blocks). By taking the block directly below the middle (value 66), player one leaves the other stranded: if he does not place a 00 in the bottom-rightmost 3×33 \times 3 square, player 11 will get six 11s in it. If he does, player 11 will take the last square of value 66, and will finish with cell totals greater than 4545, which will give A6A \ge 6. Hence A=6A = 6.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.