European Mathematical Cup

Lisa's winning strategy Suppose the game is played on an $m\times n$ board with $m$ and $n$ 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\times n$ board with $m$ or $n$ 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 $4|m$ or $4|n$. We know that any $k\times 4l$ board ($k\ge 2$) can be divided into $2\times 4$ and $3\times 4$ boards (firstly divide $k\times 4l$ board in $l$ boards of dimensions $k\times 4$; after that every $k\times 4$ board divide in $\frac{k}{2}$ boards of dimensions $2\times 4$, or in $\frac{k-3}{2}$ boards of dimensions $2\times 4$ and one $3\times 4$ board, dependently on parity of $k$). The following diagrams show that every $2\times 4$ and every $3\times 4$ board allows a required partition.

Case 2. Suppose $m,n\equiv 1,2(\mathrm{mod}4)$. Any $(5+4l)\times (6+4l)$ board can be divided into a $5\times 6$ board, a $4k\times l$ board, a $5\times 4l$ board and a $4k\times 4l$ board. The following diagram shows that a $5\times 6$ board allows a required partition. According to case 1 a $4k\times 6$ board, a $5\times 4l$ board and a $4k\times 4l$ board also allow a partition.

Case 3. Suppose $m,n\equiv 2,3(\mathrm{mod}4)$. Any $(3+4k)\times (6+4l)$ board can be divided into a $3\times 6$ board, a $4k\times 6$ board, a $3\times 4l$ board and a $4k\times 4l$ board. The following diagram shows that a $3\times 6$ board allows a required partition. According to case 1 a $4k\times 6$ board, a $3\times 4l$ board and a $4k\times 4l$ board also allow a partition.

Case 4. Suppose $m,n\equiv 2(\mathrm{mod}4)$. Any $(6+4k)\times (6+4l)$ board can be divided into a $6\times 6$ board, a $4k\times 6$ board, a $6\times 4l$ board and a $4k\times 4l$ board. The $6\times 6$ board can be partitioned in two $3\times 6$ boards, which were already solved. According to case 1 a $4k\times 6$ board, a $6\times 4l$ board and a $4k\times 4l$ board also allow a partition.