Maths Olympiad Prep

Library / /94 of 101

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Estonia

Mari and Jüri play the following game on an infinite grid: They take turns with Mari starting, Mari colours one uncolored square red in each of her turns, Jüri colours one uncolored square blue in each of his turns. If the centers of any four squares of the same colour form the corners of some square, then this player wins. Does either player have a winning strategy? If so, what is the least number of turns to guarantee a victory?

Solution

We will first prove that Mari can win in 5 turns. We will denote squares in the grid by the coordinates of their centers, taking Mari's first square to be (0,0)(0,0). W.l.o.g., let Jüri's first turn be (1,0)(1,0), allowing him to also color squares with fractional coordinates in future turns (Fig. 7). Mari will color (2,0)(2,0) on her second move (Fig. 8). W.l.o.g., assume that the yy-coordinate of Jüri's second move is nonpositive.
The only option for him to color three vertices of some square together with (1,0)(1,0) and (0,2)(0,2) is by choosing (1,1)(-1,-1) (Fig. 9). The only option for him to color three vertices of some square together with (1,0)(1,0) and (2,2)(2,2) is by
Figure 1
Fig. 8
Figure 2
Fig. 9
Figure 3
Fig. 10
---
choosing (3,1)(3, -1) (Fig. 10). Thus we consider three cases.

* If Jüri colors (1,1)(-1, -1) or (3,1)(3, -1) on his second turn, let it be (1,1)(-1, -1) without loss of generality (due to symmetry). Then Mari will color (0,2)(0, 2) (Fig. 11), after which Jüri is forced to color (2,2)(2, 2) to avoid immediate defeat. Then Mari can color (2,0)(-2, 0) (Fig. 12), threatening to win by (2,2)(-2, 2) or (0,2)(0, -2). Jüri cannot block both squares at once or win himself, so Mari will win on the next move.

* If Jüri colors (2,0)(-2, 0), (0,2)(0, -2), (2,2)(2, -2) or (4,0)(4, 0), then assume without loss of generality that the xx-coordinate of this move is greater than 11. Mari will color (0,2)(0, 2) again, after which Jüri is forced to color (2,2)(2, 2) to avoid immediate defeat (the two possible positions are shown in Figures 13 and 14). As (2,2)(-2, 2), (2,0)(-2, 0) and (0,2)(0, -2) are all uncolored, Mari can win exactly like in the previous case.

* If Jüri colors any other square on his second turn, then Mari can color (0,2)(0, 2) and win just like in the other cases.

Figure 4
Figure 5
Figure 6
Figure 7
Fig. 11
Fig. 12
Fig. 13
Fig. 14

We finally note that Mari cannot win in 4 moves, as after her 3rd move there exists at most 1 square which would yield an immediate victory for her, so Jüri can just block it.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.