Imagine a row of 2000 squares. 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.
Source: (USAMO ’99)
Observations:
1) The 2nd player desires to create a situation where he can win no matter what the 1st player does
2) It is always safe to play an O next to another O, as the letter just added can never be part of an SOS
3) So the only spaces into which one never play safely are bounded by S's.
4) Specifically, it is never safe to make a play between two S's that are separated by two spaces, i.e. S _ _ S. No matter what play is made, the other player can make an SOS on the next turn.
5) Call the two spaces in the middle of S _ _ S "losing spaces"
6) S _ _ S is the only arrangement that has losing spaces. Thus, there are always an even number of losing spaces.
7) If the 2nd player can create any losing spaces, and if the number of starting blocks is even, then the 2nd player can force a win, because (based on parity) the first player must be the first to play in a losing space.
The second player can force a win if the starting blocks are even and greater or equal to 14, as follows:
a) At his first turn, find a span of 7 empty spaces and play an S in the middle.
b) At is 2nd turn, if an immediate win is not available, create losing spaces by placing an S three spaces away, with two blank intervening spaces.
c) Thereafter, take any immediate win that is available. If none is available, make a safe play. The 1st player will eventually need to play in a losing space.
Final answer.
I notice that the 2nd player can force an earlier win by creating additional losing spaces, but this is not necessary. An interesting question (to me) is how long the game will last if the first player tries to prolong it and the 2nd player tries to end it more quickly by creating as many "losing spaces" as possible. Perhaps I will submit this as a new problem. The answer is not immediately obvious.