The first example is of a game. We will see how to apply the invariance principle.
Example 1: On a chessboard A and B play by turns to place black and white knights, respectively. Either player loses when he places a knight on a square attacked by a knight of the other colour or there are no free squares to place the knight on. If A starts, who has a winning strategy?
Solution: For those chess noobs like me, remark that a knight can only attack the squares shown in the figure below:
Intuitively, if each player can place a knight such that the squares that can be attacked by both knights do not overlap, then since a chessboard has an even number of cells, Player B can win, by in what people call, mirroring the first player.
Clearly a knight on a black square can only attack a knight on a white square and vice versa. So the colours of the squares that the knight attacks is invariant. Recall that a chessboard is a , so if we "fold" the board along the middle, the "flaps" would be of opposing colour. For instance, let be the colour of the cell in the row and column of the chessboard. Then we have that .
The above observation is key for us to see that the strategy for B is to do the same thing as A but symmetric to the center of the board. Basically, notice that if A can place a knight without being attacked by B's knights, the B can always place a "symmetric" knight without being attacked by A's knight due to the colour argument. Now given the way that knights attack, A can never place a knight that attacks the square where B played. Thus A loses in the end. □
To further train the skills of the reader in solving game-like problems (because we would soon be moving to colouring and other invariance, and I would select the IMO problems for demonstration), we will attempt one more example, this problem was in my training notes, and according to our trainer, was from Bulgaria 2001.
Example 2 Alice and Bob play by turns to write ones and zeroes in a list, from left to right. The game ends when each has written 2001 numbers. When the game ends the sequence of is interpreted in base . Alice wins if that number can be written as a sum of two perfect squares and if otherwise, Bob wins. Who has a winning strategy?
Solution: We want a invariant that somehow involves squares. Well, preliminarily, just plain squares would remind me of . So ultimately one should think of Fermat's Christmas Theorem. Let's see how this property translates to a winning strategy.
Now suppose the number is where there is an even number of , what can you observe? (Hint: consider ) Yup, exactly! Since can be written as a sum of squares iff can, we can perfectly well ignore the zeroes at the end. And notice that in base cannot be written as a sum of squares, so B wins! Generalising this argument, at any moment A writes a , B just copies move. In this way, if we ignore the zeores, the final number would end in which is congruent to which by Fermat's Christmas Theorem, cannot be written as a sum of squares, so B wins.
Now, remember that is smart. She wants to avoid losing to in this way.
Can you complete the argument? Post your completed proof in the comments.
Announcement: I am extremely sorry but since I will be going overseas and the wifi there is unsteady, I will not be posting any more of these daily instalments until Friday, Singapore time.