Who's Game? Topic: Logic. Level: Olympiad.

Problem: (1999 USAMO - #5) 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.

Strong: Let _ denote an open space.

We will show that the second player can always create an arrangement of squares such that the first player is forced to play a losing move. This arrangement is S _ _ S. If the first player plays an S, the second player can win with O. If the first player plays an O, the second player can win with S.

We claim that the second player can create the arrangement and not lose before the rest of the board is filled up, leaving on S _ _ S, which we established as a losing position for the first player. The second player may do this because there are en even number of total squares, so only the first player can face two empty squares.

Clearly if either player is faced with S O _, _ O S, or S _ S he wins; these are the winning positions. If the first player plays an O, the second player can play an O adjacent to it. This can never be a winning position for the first player because the winning positions require the O be have a _ and an S on both sides of it. If the first player plays an S, the second player may play an S adjacent to it unless it is one of the following arrangements:

S _ O _ or _ O _ S.

In either case, the second player simply plays an O between the existing S and O to leave no winning position.

The second player must make the first move far from the first player's first move, so as to leave open space to create the S _ _ S arrangement. Once that is done, assuming the first player does not give a winning position to the second player immediately, the first player will have two letters down, not enough to win. Hence the second player may play according to the above strategy until the only remaining spaces are the S _ _ S, which leaves the second player as the winner. QED.

--------------------

Comment: Game theory is a popular topic on the USAMO; mostly because it does not require in-depth techniques, but simply logic and proof-writing skills. It's also easy to overlook cases, so it weeds out the less rigorous competitors (which may be the case in my own proof...). We see that the 2000 is irrelevant here except that it is a large even number, important for the first move and the parity of turns.

--------------------

Practice Problem: (2004 USAMO - #4) 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.