Maths Olympiad Prep

Library / /42 of 144

Combinatorics Difficulty 7.9 National olympiad, round 2 Find the answer

Two players play alternately on a 5×5 5 \times 5 board. The first player always enters a 1 1 into an empty square and the second player always enters a 0 0 into an empty square. When the board is full, the sum of the numbers in each of the nine 3×3 3 \times 3 squares is calculated and the first player's score is the largest such sum. What is the largest score the first player can make, regardless of the responses of the second player?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine the largest score the first player can achieve, we must analyze how the scores are calculated and devise a strategy for maximizing the score in any 3×33 \times 3 square.

The board is a 5×55 \times 5 grid, so we have several overlapping 3×33 \times 3 squares to consider. When full, there are exactly nine 3×33 \times 3 squares on the board. The score of the first player is the maximum sum of numbers within any of these 3×33 \times 3 squares.

Consider the first player, who places a 11 in a cell, while the second player places a 00. The first player needs to maximize the number of 11s in a specific 3×33 \times 3 square. To achieve the maximum score, the first player should attempt to make the arrangement of 11s dense in one area to maximize the overlap in 3×33 \times 3 grids.

To strategize, note that the first player plays first, allowing them to control the initial placement of 11s. One potential optimal strategy is:

- Fill the central 3×33 \times 3 square completely with 11s.

After filling out the entire board, count the sums in each 3×33 \times 3 square. If the first player manages to place 11s strategically, maximizing a 3×33 \times 3 square's sum means achieving as many 11s as possible within it, while the rest are filled with 00s.

One example is placing:
- 11s in a 2×32 \times 3 or 3×23 \times 2 block, ensuring the largest strategic overlap achieving maximum in any 3×33 \times 3 sub-square.

In the best-case scenario (optimal placement), determining areas where all overlaps within a sub-square are maximized allows the first player to ensure six 11s in some 3×33 \times 3 square, irrespective of the opponent's placements. Each of these placements ensures substantial control over the game within limited directions and maximizes the sub-square's potential score.

Thus, the largest score the first player can ensure is:

6 \boxed{6}

This score of 66 represents the maximum achievable sum of 11s within any valid 3×33 \times 3 square, accounting for strategic placements irrespective of the opponent’s moves.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.