Difference between revisions of "1996 IMO Problems/Problem 1"
Line 35: | Line 35: | ||
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. | 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: |
+ | |||
+ | if <math>(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 2)</math>, 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)& | ||
+ | |||
Revision as of 22:33, 20 November 2023
Problem
We are given a positive integer and a rectangular board with dimensions , . The rectangle is divided into a grid of 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 . The task is to find a sequence of moves leading from the square with as a vertex to the square with as a vertex.
(a) Show that the task cannot be done if is divisible by or .
(b) Prove that the task is possible when .
(c) Can the task be done when ?
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 , , , , as follows: , , ,
Let be the coordinates of the piece after move with the initial position of the piece.
Let ,
Then, for any given , we have for all
part (a):
In order to find out the conditions for which is divisible by two we are going to look at the following three cases:
(1) When both and are divisible by .
(2) When both and are odd.
(3) When one of and is even and the other one is odd.
Case (1): Since and , then . Thus, for , this case is a valid one.
Case (2): Since and , then . Thus, for , this case is a valid one.
Case (3): Since and , or and , then . Thus, for , this case is NOT a valid one.
Having proved that Case (1) and Case (2) are the only valid cases for we are going to see what happens for both cases when we start with a square where both coordinates are odd:
if , 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)&
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 |