1999 USAMO Problems/Problem 5

Problem

The Y2K Game is played on a $1 \times 2000$ grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.

Solution

Label the squares $1$ through $2000$. The first player writes a letter in any square $k$. The second player now selects any empty square $l$ such that $\text{min}\,(|l-1|,|l-2000|,|l-k|) > 3$, and fills in a S. The first player may again play anywhere, say $m$. If the second player can now complete SOS, he does so; otherwise, if $l > m$ he fills an S in $l + 3$ and if $l < m$ he fills an S in $l-3$.

We thus have two Ss separated by two empty squares. Note that if any player plays any letter between the two Ss, the other player can always complete a SOS.

Now the second player repeats the following algorithm:

  • If he can complete SOS on his turn, he does so.
  • Otherwise, since there are an odd number of empty squares at the beginning of his turn, there must be either one empty square surrounded by two filled squares or one empty square surrounded by two empty squares. In both cases, the player places an O in that square. In both situations, it is easy to verify that the first player cannot win on the next turn.

Eventually, assuming the second player has not won yet (and since the first player does not have a winning opportunity yet), this algorithm must stop. It follows that all of the empty squares are now in pairs. Since there are an even number of empty squares, it is the first player's turn. If the first player plays on one of any pair of empty squares that does not have Ss on both its sides, then the second player plays any letter in the other square of the pair. Then, we will only have pairs of empty squares with Ss on both sides remaining (since from the first moves we have constructed at least one, and no one has played between them otherwise the game will have ended), and the first player will have to play between them, so that the second player will win.

See Also

1999 USAMO (ProblemsResources)
Preceded by
Problem 4
Followed by
Problem 6
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. AMC logo.png