IMO 1996 SL C1

Origin: FIN | Category: Combinatorics

Problem

We are given a positive integer $r$ and a rectangular board $ABCD$ with dimensions $|AB| = 20$, $|BC| = 12$. The rectangle is divided into a grid of $20 \times 12$ unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is $\sqrt{r}$. The task is to find a sequence of moves leading from the square corresponding to vertex $A$ to the square corresponding to vertex $B$.

(a) Show that the task cannot be done if $r$ is divisible by $2$ or $3$.

(b) Prove that the task is possible when $r = 73$.

(c) Is there a solution when $r = 97$?

Solution

We shall work on the array of lattice points defined by

$A = {(x, y) \in \mathbb{Z}^2 \mid 0 \leq x \leq 19,, 0 \leq y \leq 11}.$

Our task is to move from $(0,0)$ to $(19,0)$ via the points of $A$ so that each move has the form

$(x, y) \to (x + a, y + b),$

where $a, b \in \mathbb{Z}$ and $a^2 + b^2 = r$.

(a) If $r$ is even, then $a + b$ is even whenever $a^2 + b^2 = r$ ($a, b \in \mathbb{Z}$). Thus the parity of $x + y$ does not change after each move, so we cannot reach $(19,0)$ from $(0,0)$.

If $3 \mid r$, then both $a$ and $b$ are divisible by $3$, so if a point $(x, y)$ can be reached from $(0,0)$, we must have $3 \mid x$. Since $3 \nmid 19$, we cannot get to $(19,0)$.

(b) We have $r = 73 = 8^2 + 3^2$, so each move is either

$(x, y) \to (x \pm 8, y \pm 3) \quad \text{or} \quad (x, y) \to (x \pm 3, y \pm 8).$

One possible solution is shown in (Figure: 1).

(c) We have $97 = 9^2 + 4^2$. Let us partition $A$ as $B \cup C$, where

$B = {(x, y) \in A \mid 4 \leq y \leq 7}.$

It is easily seen that moves of the type $(x, y) \to (x \pm 9, y \pm 4)$ always take us from the set $B$ to $C$ and vice versa, while the moves $(x, y) \to (x \pm 4, y \pm 9)$ always take us from $C$ to $C$. Furthermore, each move of the type $(x, y) \to (x \pm 9, y \pm 4)$ changes the parity of $x$, so to get from $(0,0)$ to $(19,0)$ we must have an odd number of such moves. On the other hand, with an odd number of such moves, starting from $C$ we can end up only in $B$, although the point $(19,0)$ is not in $B$. Hence, the answer is no.

Remark. Part (c) can also be solved by examining all cells that can be reached from $(0,0)$. All these cells are marked in (Figure: 2).