Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1996 IMO Problems/Problem 1"
Line 29: Line 29:
 
(3) When one of <math>\Delta x_i</math> and <math>\Delta y_i</math> is even and the other one is odd.
 
(3) When one of <math>\Delta x_i</math> and <math>\Delta y_i</math> is even and the other one is odd.
  
−
Case (1): Since <math>\Delta x_i \equiv 0\;(mod \; 2)</math> and <math>\Delta y_i \equiv 0\;(mod \; 2)</math>, then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 2)\equiv 0\;(mod \; 2)</math>. Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is a valid one.
+
Case (1): Since <math>\Delta x_i \equiv 0\;(mod \; 2)</math> and <math>\Delta y_i \equiv 0\;(mod \; 2)</math>,  
  
−
Case (2): Since <math>\Delta x_i \equiv 1\;(mod \; 2)</math> and <math>\Delta y_i \equiv 1\;(mod \; 2)</math>, then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+1^2)\;(mod \; 2)\equiv 0\;(mod \; 2)</math>. Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is a valid one.
+
then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 2)\equiv 0\;(mod \; 2)</math>.
  
−
Case (3): Since <math>\Delta x_i \equiv 1\;(mod \; 2)</math> and <math>\Delta y_i \equiv 0\;(mod \; 2)</math>, or <math>\Delta x_i \equiv 0\;(mod \; 2)</math> and <math>\Delta y_i \equiv 1\;(mod \; 2)</math>, then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+0^2)\;(mod \; 2)\equiv 1\;(mod \; 2)\not\equiv 0\;(mod \; 2)</math>. Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is NOT a valid one.
+
Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is a valid one.
 +
 
 +
Case (2): Since <math>\Delta x_i \equiv 1\;(mod \; 2)</math> and <math>\Delta y_i \equiv 1\;(mod \; 2)</math>,
 +
 
 +
then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+1^2)\;(mod \; 2)\equiv 0\;(mod \; 2)</math>.
 +
 
 +
Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is a valid one.
 +
 
 +
Case (3): Since <math>\Delta x_i \equiv 1\;(mod \; 2)</math> and <math>\Delta y_i \equiv 0\;(mod \; 2)</math>, or <math>\Delta x_i \equiv 0\;(mod \; 2)</math> and <math>\Delta y_i \equiv 1\;(mod \; 2)</math>,  
 +
 
 +
then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+0^2)\;(mod \; 2)\equiv 1\;(mod \; 2)\not\equiv 0\;(mod \; 2)</math>.  
 +
 
 +
Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is NOT a valid one.
  
 
Having proved that Case (1) and Case (2) are the only valid cases for <math>r\equiv 0\;(mod \; 2)</math> we are going to see what happens for both cases when we start with a square where both coordinates are odd:
 
Having proved that Case (1) and Case (2) are the only valid cases for <math>r\equiv 0\;(mod \; 2)</math> we are going to see what happens for both cases when we start with a square where both coordinates are odd:
Line 57: Line 69:
 
(6) When neither <math>\Delta x_i</math> nor <math>\Delta y_i</math> is divisible by <math>3</math>.
 
(6) When neither <math>\Delta x_i</math> nor <math>\Delta y_i</math> is divisible by <math>3</math>.
  
−
Case (4): Since <math>\Delta x_i \equiv 0\;(mod \; 3)</math> and <math>\Delta y_i \equiv 0\;(mod \; 3)</math>, then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 3)\equiv 0\;(mod \; 3)</math>. Thus, for <math>r\equiv 0\;(mod \; 3)</math>, this case is a valid one.
+
Case (4): Since <math>\Delta x_i \equiv 0\;(mod \; 3)</math> and <math>\Delta y_i \equiv 0\;(mod \; 3)</math>,
 +
 
 +
then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 3)\equiv 0\;(mod \; 3)</math>.  
 +
 
 +
Thus, for <math>r\equiv 0\;(mod \; 3)</math>, this case is a valid one.
 +
 
 +
Case (5): Since either <math>\Delta x_i</math> or <math>\Delta y_i \equiv \pm 1\;(mod \; 3)</math> and the other <math>\equiv 1\;(mod \; 3)</math>,
 +
 
 +
then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv ((\pm 1)^2+0^2)\;(mod \; 3)\equiv 1\;(mod \; 3)</math>.
 +
 
 +
Thus, for <math>r\equiv 0\;(mod \; 3)</math>, this case is NOT a valid one.
 +
 
 +
Case (6): Since <math>\Delta x_i \equiv \pm 1\;(mod \; 3)</math> and <math>\Delta y_i \equiv \pm1 \;(mod \; 3)</math>,
  
−
Case (5): Since either <math>\Delta x_i</math> or <math>\Delta y_i \equiv \pm 1\;(mod \; 3)</math> and the other <math>\equiv 1\;(mod \; 3)</math>, then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv ((\pm 1)^2+0^2)\;(mod \; 3)\equiv 1\;(mod \; 3)</math>. Thus, for <math>r\equiv 0\;(mod \; 3)</math>, this case is NOT a valid one.
+
then <math>(\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)</math>.  
  
−
Case (6): Since <math>\Delta x_i \equiv \pm 1\;(mod \; 3)</math> and <math>\Delta y_i \equiv \pm1 \;(mod \; 3)</math>, then <math>(\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)</math>. Thus, for <math>r\equiv 0\;(mod \; 3)</math>, this case is NOT a valid one.
+
Thus, for <math>r\equiv 0\;(mod \; 3)</math>, this case is NOT a valid one.
  
  

Revision as of 22:52, 20 November 2023

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.

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 two 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 that the task cannot be done if $r$ is divisible by $2$.

Now we look at the conditions for which $r$ is divisible by three 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.


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

See Also

1996 IMO (Problems) • Resources
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_IMO_Problems/Problem_1&oldid=205000"