Maths Olympiad Prep

Library / /24 of 27

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it North Macedonia

Jeck and Lisa are playing a game on an m×nm \times n board, with m,n>2m, n > 2. Lisa starts by putting a knight onto the board. Then in turn Jeck and Lisa put a new piece onto the board according to the following rules:
1. Jeck puts a queen on an empty square that is two squares horizontally and one square vertically, or alternatively one square horizontally and two squares vertically, away from Lisa's last knight.
2. Lisa puts a knight on an empty square that is on the same row, column or diagonal as Jeck's last queen.
The one who is unable to put a piece on the board loses the game. For which pairs (m,n)(m,n) does Lisa have a winning strategy?

Solution

Lisa's winning strategy
Suppose the game is played on an m×nm \times n board with mm and nn both odd. Then Lisa puts her knight in a corner and partitions the remaining squares of the board into "dominoes". In each turn Jeck has to put a queen in one of these dominoes and Lisa puts a knight on the other square of the domino. As the board is finite, Jeck can't keep finding new dominoes and so Lisa will win.

Jeck's winning strategy
Suppose the game is played on an m×nm \times n board with mm or nn even. We shall that Jeck is able to partition the board into pairs of squares that are two squares horizontally and one square vertically, or alternatively one square horizontally and two squares vertically, away from each other. In each turn Lisa has to put a knight in one of these and Jeck puts a queen on the other square of the pair. As the board is finite, Lisa can't keep finding new pairs and so Jeck will win. Now we prove that Jeck can make the required partition.

Case 1. Suppose 4m4|m or 4n4|n. We know that any k×4lk \times 4l board (k2k \ge 2) can be divided into 2×42 \times 4 and 3×43 \times 4 boards (firstly divide k×4lk \times 4l board in ll boards of dimensions k×4k \times 4; after that every k×4k \times 4 board divide in k2\frac{k}{2} boards of dimensions 2×42 \times 4, or in k32\frac{k-3}{2} boards of dimensions 2×42 \times 4 and one 3×43 \times 4 board, dependently on parity of kk). The following diagrams show that every 2×42 \times 4 and every 3×43 \times 4 board allows a required partition.

Case 2. Suppose m,n1,2(mod4)m,n \equiv 1,2 \pmod 4. Any (5+4l)×(6+4l)(5+4l) \times (6+4l) board can be divided into a 5×65 \times 6 board, a 4k×l4k \times l board, a 5×4l5 \times 4l board and a 4k×4l4k \times 4l board. The following diagram shows that a 5×65 \times 6 board allows a required partition.
According to case 1 a 4k×64k \times 6 board, a 5×4l5 \times 4l board and a 4k×4l4k \times 4l board also allow a partition.

Case 3. Suppose m,n2,3(mod4)m,n \equiv 2,3 \pmod 4. Any (3+4k)×(6+4l)(3+4k) \times (6+4l) board can be divided into a 3×63 \times 6 board, a 4k×64k \times 6 board, a 3×4l3 \times 4l board and a 4k×4l4k \times 4l board. The following diagram shows that a 3×63 \times 6 board allows a required partition.
According to case 1 a 4k×64k \times 6 board, a 3×4l3 \times 4l board and a 4k×4l4k \times 4l board also allow a partition.

Case 4. Suppose m,n2(mod4)m,n \equiv 2 \pmod 4. Any (6+4k)×(6+4l)(6+4k) \times (6+4l) board can be divided into a 6×66 \times 6 board, a 4k×64k \times 6 board, a 6×4l6 \times 4l board and a 4k×4l4k \times 4l board. The 6×66 \times 6 board can be partitioned in two 3×63 \times 6 boards, which were already solved. According to case 1 a 4k×64k \times 6 board, a 6×4l6 \times 4l board and a 4k×4l4k \times 4l board also allow a partition.

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.