Problem 1

We are given a positive integer

r

and a rectangular board divided into

20\times12

unit squares. A move from one square to another is permitted only when the distance between their centers is

\sqrt r

. Find a sequence of moves leading between two adjacent corners of the board that lie on the long side. (a) Show that this is impossible if

r

is divisible by

2

3

. (b) Prove that it is possible for

r=73

. (c) Can it be done for

r=97

Step 2 of 4: Rule out even divisibility

Previous step Next step

In plain words

Rule out even divisibility

r\equiv0\pmod2

Detailed analysis

If $2\mid r$ , then $u$ and $v$ have the same parity. Every move therefore preserves the chessboard color, whereas $(0,0)$ and $(19,0)$ have opposite colors. If $3\mid r$ , then squares modulo $3$ show $u\equiv v\equiv0\pmod3$ ; hence the $x$ -coordinate remains divisible by $3$ , so it cannot reach $19$ .