Maths Olympiad Prep

Library / /270 of 299

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Iran

Two intelligent players play a game on a 1403×14031403 \times 1403 grid consists of 140321403^2 unit squares, taking turns. On their turn, the first player chooses one of the unchosen cells and draws a unit line segment from the midpoint of its top side to the midpoint of its bottom side. In their turn, the second player chooses one of the free cells and draws a unit line segment from the midpoint of its right side to the midpoint of its left side. After 140321403^2 steps, the game ends. The first player scores points equal to the length of the longest connected vertical line segment they have formed. The second player also scores points equal to the length of the longest connected horizontal line segment they have formed. At the end of the game, the player with the higher score wins; if scores are equal, there would be a draw. What will be the outcome of the game? Justify your answer.

Solution

The first player draws their first vertical line in the red-colored cell of the table shown. Then, they consider the cell above and below it (the blue ones) as a pair, and pairs up the other cells in that column two by two (the green dominoes). The rest of the table, which is a 1403×14021403 \times 1402 grid, is also partitioned into horizontal dominoes, indicated in the figure by yellow and orange colors. In this case, it is easily proven that they prevent their opponent from creating a line segment of length 33. Also, they will clearly draw one of the line segments in one of the blue cells, which, when placed next to the line drawn in the first step, achieves a line segment of length 22. Thus, the first player has a non-losing strategy.

Now, we also present a non-losing strategy for the second player. This strategy is as follows: After the first player's move, if the cell above it is empty, draw a horizontal line in that cell. If its upper cell is full, draw a horizontal line in the cell below it. If that is also full, draw a horizontal line in any other cell in the same column. And if such an action is also not possible (i.e., when that column becomes full), draw a horizontal line in a "good" cell (which will be specified later). In this case, it becomes clear that they prevent their opponent from achieving a vertical line of length 33. Now we proceed to prove that with the above strategy, the second player can achieve a line segment of length 22. For this purpose, consider the first time a column becomes completely full (we call it column CC). It is clear that at such a stage, it is the second player's turn (because the 14031403-rd cell of a column has been filled, and 14031403 is odd).

Now, the second player makes their move in a cell of an adjacent column to column CC, in the same row as a cell in column CC where player two has drawn a horizontal line, thus forming a horizontal line of length 22. If no such cell exists, it means that all 701701 possible cells in this adjacent column were previously occupied by the first player with vertical lines. Since every move by the second player so far has been in the same column as the first player's, another 701701 cells in this adjacent column have been filled with horizontal lines by the second player. Thus, these columns adjacent to column CC have 14021402 filled cells (we call columns with 14021402 filled cells "almost full columns"). Now, if second player again looks to the columns adjacent to these two columns for a suitable cell to draw a horizontal line to form a line of length 22, either they succeed, or those columns will also be in an almost full state. In this way, successively, all columns (except CC) become 'almost full'. In this case, second player draws a horizontal line in one of the 'almost full' columns whose two adjacent columns are also in this state. It is clear that in their next turn, second player can also draw a horizontal line in one of its two adjacent 'almost full' columns. This results in two consecutive columns, say XX and YY, where column XX has all its 14031403 cells filled (701701 vertical by first player, 702702 horizontal by second player) and column YY also has all its 14031403 cells filled (701701 vertical by first player, 702702 horizontal by second player). So, second player has placed 702702 horizontal lines in column XX and 702702 horizontal lines in column YY. And since 1403<7022=14041403 < 7022 = 1404, Consider the 14031403 rows, by the Pigeonhole Principle, there must be at least one row where second player has placed a horizontal line in column XX and also in column YY. This creates a horizontal line of length 22 for second player. Thus, the second player also has a non-losing strategy, and the game will result in a draw if both players play intelligently. ■

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.