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 1 of 4: Encode a move

Previous step Next step

In plain words

Encode a move

u^2+v^2=r

Detailed analysis

Write the displacement of a move as $(\pm u,\pm v)$ after possibly interchanging the coordinates, so $u^2+v^2=r$ . Color the board as a chessboard and use square-center coordinates $0\le x\le19$ , $0\le y\le11$ ; the required endpoints are $(0,0)$ and $(19,0)$ .