1996 IMO Problems/Problem 1

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

(c) Can the task be done when $r=97$ ?

Solution

First we define the rectangular board in the cartesian plane with centers of the unit squares as integer coordinates and the following coordinates for the squares at the corners of $A$ , $B$ , $C$ , $D$ , as follows: $A=(1,1)$ , $B=(20,1)$ , $C=(20,12)$ , $D=(1,12)$

Let $(x_i,y_i)$ be the coordinates of the piece after move $i$ with $(x_0,y_0)=A=(1,1)$ the initial position of the piece.

$1 \le x_i \le 20$ , and also $1 \le y_i \le 12$ .

Let $\Delta x_i = x_i-x_{i-1}$ , $\Delta y_i = y_i-y_{i-1}$

Then, for any given $r$ , we have $(\Delta x_i)^2+(\Delta y_i)^2=\left( \sqrt{r} \right)^2=r$ for all $i$

Part (a):

In order to find out the conditions for which $r$ is divisible by 2 we are going to look at the following three cases:

(1) When both $\Delta x_i$ and $\Delta y_i$ are divisible by $2$ .

(2) When both $\Delta x_i$ and $\Delta y_i$ are odd.

(3) When one of $\Delta x_i$ and $\Delta y_i$ is even and the other one is odd.

Case (1): Since $\Delta x_i \equiv 0\;(mod \; 2)$ and $\Delta y_i \equiv 0\;(mod \; 2)$ ,

then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 2)\equiv 0\;(mod \; 2)$ .

Thus, for $r\equiv 0\;(mod \; 2)$ , this case is a valid one.

Case (2): Since $\Delta x_i \equiv 1\;(mod \; 2)$ and $\Delta y_i \equiv 1\;(mod \; 2)$ ,

then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+1^2)\;(mod \; 2)\equiv 0\;(mod \; 2)$ .

Thus, for $r\equiv 0\;(mod \; 2)$ , this case is a valid one.

Case (3): Since $\Delta x_i \equiv 1\;(mod \; 2)$ and $\Delta y_i \equiv 0\;(mod \; 2)$ , or $\Delta x_i \equiv 0\;(mod \; 2)$ and $\Delta y_i \equiv 1\;(mod \; 2)$ ,

then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+0^2)\;(mod \; 2)\equiv 1\;(mod \; 2)\not\equiv 0\;(mod \; 2)$ .

Thus, for $r\equiv 0\;(mod \; 2)$ , this case is NOT a valid one.

Having proved that Case (1) and Case (2) are the only valid cases for $r\equiv 0\;(mod \; 2)$ we are going to see what happens for both cases when we start with a square where both coordinates are odd:

if $(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 2)$ ,

then for case (1): $(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+0,1+0) \;(mod \; 2) \equiv (1,1) \;(mod \; 2)$

and for case (2): $(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+1,1+1) \;(mod \; 2) \equiv (0,0) \;(mod \; 2)$

and $(x_{i-1}+2\Delta x_i,y_{i-1}+2\Delta y_i) \equiv (1+2,1+2) \;(mod \; 2) \equiv (1,1) \;(mod \; 2)$

This means that when $r$ is divisible by two, when starting at $(1,1)$ no matter how many moves you make all $(x_{i},y_{i})$ will either be $\equiv (0,0) \;(mod \; 2)$ or $\equiv (1,1) \;(mod \; 2)$ .

Since the ending coordinate is $(20,1) \equiv (0,1) \;(mod \; 2) \not\equiv (1,1) \;(mod \; 2)$ and $\not\equiv (0,0) \;(mod \; 2)$ , then the task cannot be done if $r$ is divisible by $2$ .

Now we look at the conditions for which $r$ is divisible by 3 by looking at the following three cases:

(4) When both $\Delta x_i$ and $\Delta y_i$ are divisible by $3$ .

(5) When one of them is not divisible by $3$ and the other one is.

(6) When neither $\Delta x_i$ nor $\Delta y_i$ is divisible by $3$ .

Case (4): Since $\Delta x_i \equiv 0\;(mod \; 3)$ and $\Delta y_i \equiv 0\;(mod \; 3)$ ,

then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 3)\equiv 0\;(mod \; 3)$ .

Thus, for $r\equiv 0\;(mod \; 3)$ , this case is a valid one.

Case (5): Since either $\Delta x_i$ or $\Delta y_i \equiv \pm 1\;(mod \; 3)$ and the other $\equiv 1\;(mod \; 3)$ ,

then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv ((\pm 1)^2+0^2)\;(mod \; 3)\equiv 1\;(mod \; 3)$ .

Thus, for $r\equiv 0\;(mod \; 3)$ , this case is NOT a valid one.

Case (6): Since $\Delta x_i \equiv \pm 1\;(mod \; 3)$ and $\Delta y_i \equiv \pm1 \;(mod \; 3)$ ,

then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv ((\pm 1)^2+(\pm 1)^2)\;(mod \; 3)\equiv 2\;(mod \; 3)\not\equiv 0\;(mod \; 3)$ .

Thus, for $r\equiv 0\;(mod \; 3)$ , this case is NOT a valid one.

Having proved that Case (4) is the only valid case for $r\equiv 0\;(mod \; 3)$ we are going to see what happens when we start with a square that is $\equiv (1,1)\;(mod \; 3)$

if $(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 3)$ , then $(x_{i-1}+\Delta x_i ,y_{i-1}+\Delta y_i) \equiv (1+0,1+0) \;(mod \; 3) \equiv (1,1) \;(mod \; 3)$ .

Therefore starting at any $(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 3)$ no matter how many moves the piece will always land at another square $\equiv (1,1) \;(mod \; 3)$ . Since we start at $(1,1)$ , then the piece will always land at squares that are $\equiv (1,1) \;(mod \; 3)$ .

Since final square is $(20,1) \equiv (2,1) \;(mod \; 3) \not\equiv (1,1) \;(mod \; 3)$ , then the task cannot be done if $r$ is divisible by $3$ .

In summary the task cannot be done if $r$ is divisible by $2$ or $r$ is divisible by $3$ .

Part (b):

When $r=73$ we have $8^2+3^2=73$

Therefore the moves can have the following values:

$(\Delta x_i, \Delta y_i)=\begin{cases} (\pm 8,\pm 3) \\ (\pm 8,\mp 3) \\ (\pm 3,\pm 8) \\ (\pm 3,\mp 8) \end{cases}$

Since we start at $(1,1)$ and we want to end at $(20,1)$ we can write the following $11$ valid moves:

$\begin{matrix} (1,1)&+&(3,8)&=&(4,9)\\ (4,9)&+&(8,-3)&=&(12,6)\\ (12,6)&+&(8,-3)&=&(20,3)\\ (20,3)&+&(-3,8)&=&(17,11)\\ (17,11)&+&(-8,-3)&=&(9,8)\\ (9,8)&+&(-8,-3)&=&(1,5)\\ (1,5)&+&(8,-3)&=&(9,2)\\ (9,2)&+&(3,8)&=&(12,10)\\ (12,10)&+&(-8,-3)&=&(4,7)\\ (4,7)&+&(8,-3)&=&(12,4)\\ (12,4)&+&(8,-3)&=&(20,1)\\ \end{matrix}$

Having shown that all moves comply with the possible values for $(\Delta x_i, \Delta y_i)$ and that all $(x_i, y_i)$ are inside the rectangular grid, then the task is possible when $r=73$ .

Part (c):

When $r=97$ we have $9^2+4^2=97$

Therefore the moves can have the following values:

$(\Delta x_i, \Delta y_i)=\begin{cases} (\pm 9,\pm 4) \\ (\pm 9,\mp 4) \\ (\pm 4,\pm 9) \\ (\pm 4,\mp 9) \end{cases}$

Let $S$ be a set of the squares of the rectangle with the condition $x_i \equiv \left\lceil \frac{y_i}{4} \right\rceil \;(mod \; 2)$ for $(x_i,y_i)$ . That is, the reminder of $x_i$ when divided by 2 is the same as the reminder of $\left\lceil \frac{y_i}{4} \right\rceil$ when divided by 2 where $\left\lceil k \right\rceil$ is the smallest integer that is not less than $k$ . If that condition is true, then $(x_i,y_i) \in S$

Now let's look at a case (c1) where $(x_i,y_i) \in S$ and $x_i \equiv 0 \;(mod \; 2)$ , thus $\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)$ :

c1 subcase 1 : $(x_{i+1},y_{i+1})=(x_i \pm 9,y_i \pm 4)$ :

$(x_i \pm 9) \equiv (0 \pm 9)\;(mod \; 2) \equiv 1 \;(mod \; 2)$

and $\left\lceil \frac{y_i \pm 4}{4} \right\rceil \equiv \left\lceil \frac{y_i}{4} \right\rceil \pm 1 \;(mod \; 2)\equiv (0 \pm 1) \;(mod \; 2)\equiv 1 \;(mod \; 2)$

since $x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil \;(mod \; 2)$ , then $(x_{i+1},y_{i+1}) \in S$ for this subcase.

c1 subcase 2 : $(x_{i+1},y_{i+1})=(x_i \pm 4,y_i \pm 9)$ :

This move is not allowed because the only values of $1 \le y_i \le 12$ such that $\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)$ are $5,6,7,8$ . Adding or subtracting 9 from any of these numbers will either make $y_{i+1}<0$ or $y_{i+1}>12$ and will put the piece outside of the board.

In summary, for case (c1), $(x_{i+1},y_{i+1}) \in S$

Now let's look at a case (c2) where $(x_i,y_i) \in S$ and $x_i \equiv 1 \;(mod \; 2)$ , thus $\left\lceil \frac{y_i}{4} \right\rceil \equiv 1 \;(mod \; 2)$ :

c2 subcase 1 : $(x_{i+1},y_{i+1})=(x_i \pm 9,y_i \pm 4)$ :

$(x_i \pm 9) \equiv (1 \pm 9)\;(mod \; 2) \equiv 0 \;(mod \; 2)$

and $\left\lceil \frac{y_i \pm 4}{4} \right\rceil \equiv \left\lceil \frac{y_i}{4} \right\rceil \pm 1 \;(mod \; 2)\equiv (1 \pm 1) \;(mod \; 2)\equiv 0 \;(mod \; 2)$

since $x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil \;(mod \; 2)$ , then $(x_{i+1},y_{i+1}) \in S$ for this subcase.

c2 subcase 2 : $(x_{i+1},y_{i+1})=(x_i \pm 4,y_i \pm 9)$ :

$(x_i \pm 4) \equiv (1 \pm 4)\;(mod \; 2) \equiv 1 \;(mod \; 2)$

Notice that the only values of $1 \le y_i \le 12$ such that $\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)$ are $1,2,3,4,9,10,11,12$ . Adding 9 to the values of 1,2, or 3 or subtracting 9 from the values of 10, 11, or 12, will result in $\left\lceil \frac{y_{i+1}}{4} \right\rceil \equiv 1 \;(mod \; 2)$ . However, subtracting 9 from the values of 1,2, or 3, or adding 9 for the values of 10,11, or 12 will put the piece outside the board and not a valid move. Furthermore, for the values of 4 and 9, adding or subtracting 9 from them will result in the piece being outside of the board and not a valid move. Therefore for all valid moves in this subcase which are 9 added to 1, 2, or 3 or 9 subtracted from 10, 11, or 12, the result will be $\left\lceil \frac{y_{i+1}}{4} \right\rceil \equiv 1 \;(mod \; 2)$

since $x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil \;(mod \; 2)$ , then $(x_{i+1},y_{i+1}) \in S$ for this subcase.

In summary, for case (c2), $(x_{i+1},y_{i+1}) \in S$

Therefore if $(x_{i},y_{i}) \in S$ then $(x_{i+1},y_{i+1}) \in S$

Now we look at the starting point: $(1,1)$ :

Since $1 \equiv 1\;(mod \; 2)$ and $\left\lceil \frac{1}{4} \right\rceil \equiv 1\;(mod \; 2)$ , then $(1,1) \in S$ and all subsequent squares after that $\in S$

Now let's look at the end point: $(20,1)$ :

Since $20 \equiv 0\;(mod \; 2)$ and $\left\lceil \frac{1}{4} \right\rceil \equiv 1\;(mod \; 2)$ , then $20 \not\equiv \left\lceil \frac{1}{4} \right\rceil \;(mod \; 2)$ and $(20,1) \not\in S$

Since $(20,1) \not\in S$ , then there are no valid moves starting from $(1,1)$ that will end in $(20,1)$

Therefore the task cannot be done when $r=97$ .

~Tomas Diaz. orders@tomasdiaz.com

Solution 2

Slightly different than the first solution, we identify the board with the cartersian plane with the center of the squares integer coordinates such that $A=(0,0), B=(19,0),C=(19,11),D=(0,11)$ .

Part (a): If $2|r$ and $x,y$ are the change in the $x$ coordinate and $y$ coordinate respectively for a move, one finds $x^2+y^2 = r$ hence both $x,y$ are even or both $x,y$ are odd. Hence, since we start at $(0,0)$ , for any sequence of moves of distance $\sqrt{r}$ , the current position $(a,b)$ will always have the same parity between $a$ and $b$ . On the other hand $B=(19,0)$ has a different parity between the first and second coordinate, so it is not possible to reach $B$ with $2|r$ .

If $3|r$ , defining $x,y$ the same one similarly finds $x^2+y^2 = r$ hence $x^2 + y^2 \equiv 0 \mod 3$ . Considering the possible values of $x,y$ mod $3$ , the only way this is possible is if both $x,y$ are divisible by $3$ . Hence, since we start at $(0,0)$ , for any sequence of moves of distance $\sqrt{r}$ , the current position $(a,b)$ will have both $(a,b)$ divisible by $3$ . On the other hand $B=(19,0)$ doesn't have both coordinates divisible by $3$ . So it is not possible to reach $B$ with $3|r$ .

Part (b): Note $8^2+3^2 = 73$ . The following sequence of moves have $r = 73$ and show it is possible. $\begin{align*} &(3,8),(6,0),(9,8),(1,5),(9,2),(12,10),(15,2), \\ &(18,10),(10,7),(18,4),(10,1),(13,9),(16,1),(19,9), \\ &(11,6),(3,3),(6,11),(9,3),(12,11),(15,3),(7,0), \\ &(10,8),(13,0),(16,8),(19,0). \end{align*}$

Part (c): Suppose by contradiction a sequence of moves reaches $(19,0)$ from $(0,0)$ . Let $m_1, m_2$ be the number of moves where the second coordinate increased/decreased by a distance of $4$ respectively, and $n_1,n_2$ be the number of moves where the second coordinate increased/decreased by a distance of $9$ respectively. Apparently $4(m_1-m_2) + 9(n_1-n_2) = 0.$ Let $m_1',m_2'$ be the number of moves where the first coordinate increased/decreased by a distance of $9$ respectively, and $n_1',n_2'$ be the number of moves where the first coordinate increased/decreased by $4$ respectively. Apparently $9(m_1'-m_2') + 4(n_1'-n_2') = 19$ If $m_1-m_2 = n_1-n_2 =0$ then since $m_1'+m_2' = m_1+m_2 = 2m_1$ and $n_1'+n_2' = n_1+n_2 = 2n_1$ one finds $m_1'-m_2' = 2m_1'-2m_1$ and $n_1'-n_2' = 2n_1'- 2n_1$ . In which case the above equation doesn't have an integer solution. Therefore $m_1-m_2$ and $n_1-n_2$ are not both zero.

Now, the second coordinate must start at $0$ and end at $0$ . If the sequence of moves simply adds values to the second coordinate and eventually subtracts those same values both $m_1-m_2$ and $n_1-n_2$ will be zero, contradicting the previous. (Or if it subtracts values and eventually adds those same values back).

At each step we may add $4$ , subtract $4$ , or add $9$ , or subtract $9$ to the second coordinate without leaving the game board. There are only two possible non-repeating sequences: $0,4,8$ and $0,9,5,1,10,6,2,11,7,3$ at which points there are no non-repeating moves possible since a $y$ coordinate value of $12$ is outside the game board. Thus in order to return to $0$ the sequence is forced to subtract the same values added (or add the same values subtracted), contradicting the previous. So it is not possible to find a solution with $r = 97$ .

~not_detriti

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1996 IMO (Problems) • Resources
Preceded by First Problem	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search

1996 IMO Problems/Problem 1

Contents

Problem

Solution

Solution 2

See Also