Maths Olympiad Prep

Library / /410 of 520

Combinatorics Difficulty 7.0 National olympiad Prove it

The Y2K Game is played on a 1×20001 \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.

Solution

The main insight is that a construct of the form SS S \square \square S (here the \square 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 cc loses. If we wrote OO, that means cc is bordered by exactly one SS, with a blank cell on the neighbor. But we could also write SS; checking cases we find cc 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.