1999 USAMO Problems/Problem 5
Problem
The Y2K Game is played on a 
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 
through 
. The first player writes a letter in any square 
. The second player now selects any empty square 
such that 
, and fills in a S. The first player may again play anywhere, say 
. If the second player can now complete SOS, he does so; otherwise, if 
he fills an S in 
and if 
he fills an S in 
.
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 (Problems • Resources) | ||
| Preceded by Problem 4 |
Followed by Problem 6 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
