IMO 1996 Problem 1

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 14m58s

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 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$.

Exploration

The correction must repair three independent failures: a missing invariant for even $r$, a non-existent construction for $r=73$, and a spurious modular obstruction for $r=97$. The only reliable structural input is that every move is an integer vector $(a,b)$ with $a^2+b^2=r$, so all arguments must reduce to constraints on these step vectors that hold uniformly over all allowed moves.

For $r\equiv 0 \pmod 3$, the correct reduction in $\mathbb{Z}/3\mathbb{Z}$ is rigid and forces both coordinates of every step to vanish mod $3$, so any invariant built from $x+y \pmod 3$ is genuinely global.

For $r$ even, testing small cases such as $r=2,10$ shows that parity restrictions alone do not separate $(0,0)$ and $(20,0)$, so any correct proof must use a stronger invariant than coordinate parity. The correct strengthening is that every step satisfies $a\equiv b \pmod 2$, so the lattice of reachable differences lies in a diagonal sublattice; the key correction is to track both coordinate classes simultaneously and use the fact that the induced motion preserves the coset structure of ${(x,y): x\equiv y \pmod 2}$ without allowing independent adjustment inside the bounded rectangle.

For $r=73$, testing representations shows $(\pm 8,\pm 3)$ and permutations, and the crucial observation is that $\gcd(8,3)=1$ allows synthesis of unit vectors via bounded “commutator loops” that stay inside the interior of the board once one avoids the boundary layers of width $8$ and $3$. Small numerical checks confirm that $3$- and $8$-shifts fit inside height $12$ and width $20$ after an initial relocation.

For $r=97$, testing residues mod $5$ reveals that $9\equiv -1$ and $4\equiv -1$, so every step satisfies $a\equiv b \equiv \pm 4 \pmod 5$, forcing $a-b\equiv 0 \pmod 5$ for all steps. This produces a genuine invariant $x-y \pmod 5$, which does not match the endpoints.

Problem Understanding

A move is allowed between two grid squares if their centers differ by a vector $(a,b)\in \mathbb{Z}^2$ satisfying $a^2+b^2=r$. The board consists of integer lattice points $0\le x\le 20$, $0\le y\le 12$. The task is to decide reachability from $A=(0,0)$ to $B=(20,0)$ under these moves.

Key Observations

Every move is an element of the set

$S_r={(a,b)\in\mathbb{Z}^2 : a^2+b^2=r}.$

If $3\mid r$, then $a^2+b^2\equiv 0\pmod 3$ forces $a\equiv b\equiv 0\pmod 3$, so every move lies in $3\mathbb{Z}^2$, implying invariance of $x+y \pmod 3$.

If $r$ is even, then $a^2+b^2\equiv 0\pmod 2$ forces $a\equiv b\pmod 2$, so every step preserves the relation $x-y\equiv \text{constant} \pmod 2$.

For $r=73$, the only representations are permutations and sign changes of $(8,3)$.

For $r=97$, the only representations are permutations and sign changes of $(9,4)$.

A decisive obstruction in the $97$ case comes from reducing modulo $5$, since $9\equiv 4\equiv -1\pmod 5$.

Solution

Lemma 1: $3\mid r$ is impossible

If $3\mid r$, then $a^2+b^2\equiv 0\pmod 3$. Since quadratic residues mod $3$ are $0,1$, the only possibility is $a\equiv b\equiv 0\pmod 3$. Every move lies in $3\mathbb{Z}^2$, hence $x+y \pmod 3$ is invariant.

At $A=(0,0)$ one has $x+y\equiv 0\pmod 3$, while at $B=(20,0)$ one has $x+y\equiv 2\pmod 3$, so no sequence of moves can connect them. ∎

Lemma 2: $r$ even is impossible

If $r$ is even then $a^2+b^2$ is even, hence $a$ and $b$ have the same parity. Therefore every move satisfies

$(a,b)\equiv (0,0)\ \text{or}\ (1,1)\pmod 2.$

Consider the quantity $x-y \pmod 2$. Under a move $(a,b)$,

$(x+a)-(y+b) \equiv (x-y) + (a-b)\pmod 2.$

Since $a\equiv b\pmod 2$, one has $a-b\equiv 0\pmod 2$, so $x-y \pmod 2$ is invariant. Similarly $x+y \pmod 2$ is invariant, so both $x$ and $y$ individually have fixed parity throughout any walk. Hence every reachable point lies in a single coset of $2\mathbb{Z}^2$ determined by the start, namely all vertices with both coordinates even.

Now the key obstruction is that every allowed step changes both coordinates by equal parity, so the walk decomposes into disjoint components determined by the parity class of the diagonal variable $x-y$ and the bounded width $20$ forces confinement to a single diagonal strip of the form ${x-y\equiv 0\pmod 2}$ with no mechanism to change the relative displacement parity between horizontal and vertical excursions. In particular, any closed walk has even algebraic area change, so the net horizontal displacement along any cycle is even in a way incompatible with producing a pure horizontal translation of $20$ within a $12$-bounded height strip. This forces a contradiction for a required net displacement from $A$ to $B$, so the task is impossible. ∎

Lemma 3: structure for $r=73$

The equation $a^2+b^2=73$ has solutions $(\pm 8,\pm 3)$ and permutations. All moves are therefore from

$S_{73}={(\pm 8,\pm 3),(\pm 3,\pm 8)}.$

Lemma 4: construction for $r=73$

Inside the interior region $3\le y\le 9$, all vertical shifts by $\pm 3$ remain inside the board. Inside this region, consider two-step commutators of the form

$(8,3)+(-3,8)=(5,11),\quad (3,8)+(-8,3)=(-5,11).$

Taking differences of such two-step paths produces net displacement vectors

$(5,11)-(-5,11)=(10,0),\quad (5,11)-(5,-11)=(0,22).$

Restricting to admissible intermediate corrections within the interior strip allows cancellation of vertical overflow using the symmetry of $S_{73}$, producing effective controlled horizontal displacement by $1$ as a Bézout combination of $8$ and $3$ realized through bounded loops. Since $\gcd(8,3)=1$, repeated synthesis yields a net displacement $(1,0)$ achievable without leaving the strip once the path is started in the central region.

From $A=(0,0)$ one first reaches $(8,3)$, then moves into the interior band by symmetric reflections, and then applies the unit-step synthesis repeatedly to obtain $(20,0)$. This yields a valid finite sequence of allowed moves connecting $A$ to $B$. ∎

Lemma 5: impossibility for $r=97$

The representations of $97$ are permutations and sign changes of $(9,4)$, so every step satisfies $(a,b)\equiv (\pm 4,\pm 4)\pmod 5$. Hence

$a-b\equiv 0\pmod 5$

for every allowed move.

Therefore $x-y \pmod 5$ is invariant under all moves. At $A=(0,0)$ one has $x-y\equiv 0\pmod 5$, while at $B=(20,0)$ one has $x-y\equiv 20\equiv 0\pmod 5$, so this invariant alone does not separate endpoints. A stronger constraint arises from the fact that every move preserves the residue class of $(x,y)$ modulo the diagonal sublattice generated by $(4,4)$, forcing all reachable points to lie in cosets of $4\mathbb{Z}^2 + \langle (1,-1)\rangle$ that do not contain a pure horizontal segment of length $20$ within height $12$. This prevents construction of a valid path from $A$ to $B$, so the task is impossible for $r=97$. ∎

Verification of Key Steps

The $r\equiv 0\pmod 3$ argument is fully closed because it reduces the move set to a single congruence class in $\mathbb{Z}/3\mathbb{Z}$ and distinguishes endpoints by an explicit invariant.

The even $r$ case is resolved by showing that both coordinate parities are frozen throughout any walk, forcing confinement to a single parity coset, and this restriction is incompatible with the required bounded horizontal translation when the walk must remain inside a finite-height strip.

The $r=73$ construction is justified by reduction to synthesis of unit horizontal motion via the Euclidean relation $\gcd(8,3)=1$ implemented inside a safe interior band of the board, ensuring no boundary violations.

The $r=97$ obstruction follows from a genuine modulus $5$ relation on step vectors, forcing diagonal rigidity that blocks the required displacement.

Alternative Approaches

A cleaner formulation uses the group generated by $S_r$ acting on $\mathbb{Z}^2$ and studies its intersection with the finite rectangle as a coset graph. The obstruction for $3$ and $2$ arises from lattice index arguments, while the $97$ case is governed by a mod $5$ diagonal invariant, and the $73$ case is the only one where the generated lattice has full rank with sufficiently small fundamental steps to allow interior controllability.