Problem:
Alice and Bob play a game on a 6 by 6 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.
Solution:
Bob can win as follows.
Claim 1. After each of his moves, Bob can insure that in that maximum number in each row is a square in , where
and
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 6 is in and the maximum square in row 1 is in . Since there is no path from to that stays in , Bob wins.
Problem originally by Melanie Wood.
The problems on this page are the property of the MAA's American Mathematics Competitions