Estonian Mathematical Olympiad

Question

Let n 3 be an integer. In an n n grid there are three invisible monsters: one in the upper right corner square and one in each of its neighboring squares. In a 2 2 area in the opposite corner of the grid some frogs are placed. A square may contain more than one frog. The frogs and the monsters take turns making the following moves. On the frogs' turn, each frog makes a knight move, jumping either two squares up and one to the right or one square up and two to the right. On the monsters' turn, they may make up to a total of 3 knight moves, jumping either two squares down and one to the left or one square down and two to the left. The frogs start. If a frog and a monster ever land on the same square, the monster will eat the frog. Find the least number of frogs needed to ensure that at leas…

Accepted Answer

We color the square in 3 colors by descending diagonals (in Fig. 16 the colors are denoted by A, B, C and X, Y, Z, which are still the same colors, but their order depends on the value of

n

). Notice that both frogs and monsters can only jump on squares of the same color as the one they started from. As the monsters cover only two colors of squares, but a

2 \times 2

area contains squares of all three colors, it is sufficient to place one frog on a square of the color not covered by the monsters. In this case, no matter the moves, the frog will be safe.

Fig. 16