All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Save our souls (Posted on 2016-06-03)
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)

Comments: ( Back to comment list | You must be logged in to post comments.)
 For the win (spoiler) Comment 2 of 2 |
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.

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.

 Posted by Steve Herman on 2016-06-03 20:49:03

 Search: Search body:
Forums (0)