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 4 of 4: Rule out

97

Previous step Next step

In plain words

Rule out $97$

9^2+4^2=97

Detailed analysis

For $r=97$ , every move has absolute coordinate changes $9$ and $4$ . Call a move a toggle when its vertical change is $4$ . In the strip $4\le y\le7$ , a non-toggle move is impossible, while a toggle move enters or leaves the strip. Starting and ending outside the strip forces an even number of toggles. But each toggle changes the parity of $x$ and each non-toggle preserves it, while $x$ changes from even $0$ to odd $19$ ; this forces an odd number of toggles, a contradiction.