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
The main insight is that a construct of the form (here the is blank) will kill any player which plays inside it. We call this a trap accordingly. Claim - The second player can force a trap to exist; in this case the game will never end in a draw. Claim - The second player always has a move which prevents her from losing. Together these two claims finish the problem. Remark. Actually, one can show that the "only" way to lose is to be forced to play inside a trap. Indeed, suppose playing in a certain cell loses. If we wrote , that means is bordered by exactly one , with a blank cell on the neighbor. But we could also write ; checking cases we find is part of a trap. Thus a player can lose only if all blank cells are in traps; ergo, the number of blank cells is even. This never happens for the second player. Thus this gives an alternative solution, and moreover a reason to believe that all correct solutions must involve traps.