Alice and Bob play a game on a by 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.
Problem 1900
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 , where and are the sets of squares marked with A's and B's in the following diagram, respectively.
Proof: Bob pairs each square of with a square in the same row that is not in , 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 in , Bob writes with in the paired square. If Alice moves with not in , Bob writes with in the paired square in . So after Bob's turn, the maximum of each pair is in , and thus the maximum of each row is in . ■
So when all the numbers are written, the maximum square in row is in and the maximum square in row is in . Since there is no path from to that stays in , Bob wins.
Second Solution: (By Tiankai Liu) Let be the property that the following conditions are met:
(a) Row , column is empty if and only if row , column is (taken modulo ).
(b) If any numbers have been written in the first or second rows, let be the index of the column with the largest number in row ; we require that .
The initial configuration of the grid (empty) clearly satisfies , and Bob can preserve by executing the following strategy after each of Alice's moves:
**Case 1: Alice moves somewhere in the lower 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 , 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 , column . If the number she wrote is now the largest number in row , then Bob should choose a number larger than every number written on the board, and write it in the square at row , column (taken modulo ). On the other hand, if Alice's new number is not the largest number in row , then Bob should choose a number smaller than every number written on the board, and write it in row , column (taken modulo ).
It is clear that by the end of Bob's move, is preserved in both cases. Yet this implies that at the end of the game, , 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.