2004 USAMO Problems/Problem 4

Problem

(Melanie Wood) 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 on 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 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 on to the other that stays in those two squares.) Find, with proof, a winning strategy for one of the players.

Solutions

Solution 1

Before the game, Bob may select three useless squares per row. He may then move according to the following rules:

• If Alice writes a number in a useless square, then Bob writes a higher number in a non-useless square in the same row on his next turn.
• If Alice writes a number in a non-useless square, then Bob writes a lower number in a useless square in the same row.

Bob can always do this because there are an even number of squares in each row.

In this way, Bob can prevent any useless square from being colored black at the end. Then it will be sufficient for Bob to make the squares (1,1), (2,1), (2,2), (3,2), (3,3), (4,3), (4,4), (5,4), (5,5), (6,5), (6,6) useless, where is the square in the th column and th row. Thus Bob can always win.

Note that it is not necessary for Bob to move first; even if he moves second, he will always be able to ensure that at least two squares per row of his choosing are not colored black.

Solution 2

Bob may move according to the following rules:

• If Alice writes a number in rows 3, 4, 5, or 6, then Bob also writes a number in row 3, 4, 5, or 6.
• If Alice writes a number in row , column , then Bob writes a number in row , column (mod 6). If Alice's number is the highest in its row, then so is Bob's; if it is not, then neither is Bob's.

In this way, there will be 2 columns in between the black squares in rows 1 and 2, so they cannot possibly touch, which means that Bob will win.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

2004 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.