IMO 1996 · Problem 1

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 with \(A\) as a vertex to the square with \(B\) as a vertex.

(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) Can the task be done when \(r = 97\)?

Official text of the problem. Official problem paper (PDF)

Answer

(a) Impossible. (b) Possible. (c) No, the task is impossible when \(r=97\).

Solution

Label the squares by integer coordinates \((x,y)\), where \[ 0\le x\le19,\qquad 0\le y\le11, \] so that the starting and target squares are \((0,0)\) and \((19,0)\). A move with coordinate differences \((u,v)\) is permitted precisely when \[ u^2+v^2=r. \]

(a) Suppose first that \(2\mid r\). Since \(t^2\equiv t\pmod2\) for every integer \(t\), every move satisfies \[ u+v\equiv u^2+v^2\equiv0\pmod2. \] Thus the parity of \(x+y\) is unchanged. Its values at the starting and target squares have opposite parity, so the task is impossible.

If \(3\mid r\), each of \(u^2,v^2\) is congruent to \(0\) or \(1\pmod3\). Their sum can be divisible by \(3\) only if both are divisible by \(3\). Hence \(3\mid u\) and \(3\mid v\). In particular, every reachable square has \(x\equiv0\pmod3\), whereas \(19\equiv1\pmod3\). Again the task is impossible.

(b) Since \(73=8^2+3^2\), the following is a valid route: \[ \begin{aligned} (0,0)&\to(3,8)\to(11,5)\to(3,2)\\ &\to(0,10)\to(8,7)\to(0,4)\to(8,1)\\ &\to(11,9)\to(3,6)\to(11,3)\to(19,0). \end{aligned} \] Every listed square lies on the board, and every step changes the coordinates by absolute amounts \(3\) and \(8\), in some order. Thus every step has length \(\sqrt{73}\), proving possibility.

(c) First, the only possible absolute coordinate differences for a move of length \(\sqrt{97}\) are \(4\) and \(9\), in some order. Indeed, because \(97\) is odd, exactly one coordinate difference is even. Its absolute value must be \(0,2,4,6,\) or \(8\). The corresponding squares of the other coordinate difference are \[ 97,\ 93,\ 81,\ 61,\ 33, \] respectively, and only \(81\) is a square.

Assign to each square the value \[ C(x,y)=x+\left\lfloor\frac y4\right\rfloor\pmod2. \] We show that every permitted move preserves this value.

  • If \(|u|=9\) and \(|v|=4\), then \(x\) changes by an odd integer, and \(\lfloor y/4\rfloor\) changes by \(1\) or \(-1\). Their sum therefore retains its parity.
  • If \(|u|=4\) and \(|v|=9\), the smaller of the two row coordinates must belong to \(\{0,1,2\}\), and the larger to \(\{9,10,11\}\). Thus \(\lfloor y/4\rfloor\) changes between \(0\) and \(2\), while \(x\) changes by an even integer. Again the value is preserved.

However, \[ C(0,0)=0,\qquad C(19,0)=1. \] Consequently no sequence of permitted moves connects the two squares.

The solution was checked against John Scholes' IMO solution archive (Kalva).