Olympiad Maths Prep

Track / Stage 9 / 20 of 80 #1900 of 2000

Problem 1900

IMO P2/P5; hard shortlist
Combinatorics Difficulty 9.2 Prove it USA IMO · United States

Alice and Bob play a game on a 66 by 66 grid. On his or her turn, a player chooses a rational number not yet appearing in the grid and writes it in an empty square of the grid. Alice goes first and then the players alternate. When all squares have numbers written in them, in each row, the square with the greatest number in that row is colored black. Alice wins if she can then draw a line from the top of the grid to the bottom of the grid that stays in black squares, and Bob wins if she can't. (If two squares share a vertex, Alice can draw a line from one to the other that stays in those two squares.) Find, with proof, a winning strategy for one of the players.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

First Solution: Bob can win as follows.
After each of his moves, Bob can insure that the maximum number in each row is a square in ABA \cup B, where AA and BB are the sets of squares marked with A's and B's in the following diagram, respectively.
Figure 1
Proof: Bob pairs each square of ABA \cup B with a square in the same row that is not in ABA \cup B, so that each square of the grid is in exactly one pair. Whenever Alice plays in one square of a pair, Bob will play in the other square of the pair on his next turn. If Alice moves with xx in ABA \cup B, Bob writes yy with y<xy < x in the paired square. If Alice moves with xx not in ABA \cup B, Bob writes zz with z>xz > x in the paired square in ABA \cup B. So after Bob's turn, the maximum of each pair is in ABA \cup B, and thus the maximum of each row is in ABA \cup B. ■
So when all the numbers are written, the maximum square in row 11 is in BB and the maximum square in row 66 is in AA. Since there is no path from BB to AA that stays in ABA \cup B, Bob wins.

Second Solution: (By Tiankai Liu) Let PP be the property that the following conditions are met:
(a) Row 11, column cc is empty if and only if row 22, column c+3c+3 is (taken modulo 66).
(b) If any numbers have been written in the first or second rows, let cic_i be the index of the column with the largest number in row ii; we require that c1c2=3|c_1 - c_2| = 3.
The initial configuration of the grid (empty) clearly satisfies PP, and Bob can preserve PP by executing the following strategy after each of Alice's moves:
**Case 1: Alice moves somewhere in the lower 44 rows.**
Bob should pick a random square somewhere in the bottom four rows, and write any rational number that has not yet been chosen. This is always possible because the number of squares in the bottom four rows is 2424, and if Bob follows this strategy, there will always be an odd number of empty squares (i.e. nonzero) in this section every time Alice's move puts him into this case.
Case 2: Alice moves somewhere in the top two rows.
Suppose that she chose the square in row rr, column cc. If the number she wrote is now the largest number in row rr, then Bob should choose a number larger than every number written on the board, and write it in the square at row 3r3-r, column c+3c+3 (taken modulo 66). On the other hand, if Alice's new number is not the largest number in row rr, then Bob should choose a number smaller than every number written on the board, and write it in row 3r3-r, column c+3c+3 (taken modulo 66).
It is clear that by the end of Bob's move, PP is preserved in both cases. Yet this implies that at the end of the game, c1c2=3|c_1 - c_2| = 3, which means that the black squares in the first two rows don't touch anywhere. Therefore, there is no way Alice can connect the top and bottom of the grid with a continuous path, because the blackened region will be disconnected.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.