USAMO-2004

Alice and Bob play a game on a 6 x 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 of the 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 path from the top of the grid to the bottom of the grid that stays in the black squares, and Bob wins if she can’t.(A path is a sequence of squares such that any two consecutive squares in the path share a vertex). Find, with proof, a winning strategy for one of the players.

The intuition here is that any path from top to bottom can be broken with a diagonal that does not comprise of black squares. Since there are only two such diagonals and they are symmetric, the winning strategy is simply the one that can maintain a diagonal of non-black squares. To form such a diagonal the opponent must be forced into the adjacent corners from each diagonal tip. In other words the black squares occupy the vicinity of two corners opposite from each other without meeting in the center where the diagonal of non-black runs through. How does Bob force the opponent into these two corners and maintain his winning strategy ? For any given row, Alice can either choose a small number in which case it cannot be a black or a big number in which case it will be a black. Since Alice is picking a square with her number, we can choose the opposite -  a big number for her small or a small number for her big forcing her number or ours to be a black and determining the position of the black in the row. Given that we already have mapped where the blacks should fall, we can play this kind of moves for all rows, thereby clustering the blacks around two corners without meeting each other in the center where the diagonal runs through.

Let us try a different problem now.
Saint Petersburg 1997 The number N is the product of k different primes (k ≥ 3). A and B take turns writing composite divisors of N on a board, according to the following rules. One may not write N. Also, there may never appear two coprime numbers or two numbers, one of which divides the other. The first player unable to move loses. If A starts,who has the winning strategy?
Solution: since we want to determine the win, we only have to split the number N into two prime factors p and q and write down pq.  This way we can reserve one move at the end for the person starting the game which is A. Then as the other player writes a number qm, A can write qn in a move that copies the attempt of B. Finally A has one move left.