Difference between revisions of "1996 IMO Problems/Problem 1"
(22 intermediate revisions by the same user not shown) | |||
Line 14: | Line 14: | ||
Let <math>(x_i,y_i)</math> be the coordinates of the piece after move <math>i</math> with <math>(x_0,y_0)=A=(1,1)</math> the initial position of the piece. | Let <math>(x_i,y_i)</math> be the coordinates of the piece after move <math>i</math> with <math>(x_0,y_0)=A=(1,1)</math> the initial position of the piece. | ||
+ | |||
+ | <math>1 \le x_i \le 20</math>, and also <math>1 \le y_i \le 12</math>. | ||
Let <math>\Delta x_i = x_i-x_{i-1}</math>, <math>\Delta y_i = y_i-y_{i-1}</math> | Let <math>\Delta x_i = x_i-x_{i-1}</math>, <math>\Delta y_i = y_i-y_{i-1}</math> | ||
Line 21: | Line 23: | ||
− | + | '''Part (a):''' | |
− | In order to find out the conditions for which <math>r</math> is divisible by | + | In order to find out the conditions for which <math>r</math> is divisible by '''2''' we are going to look at the following three cases: |
− | (1) When both <math>\Delta x_i</math> and <math>\Delta y_i</math> are divisible by <math>2</math>. | + | ''(1)'' When both <math>\Delta x_i</math> and <math>\Delta y_i</math> are divisible by <math>2</math>. |
− | (2) When both <math>\Delta x_i</math> and <math>\Delta y_i</math> are odd. | + | ''(2)'' When both <math>\Delta x_i</math> and <math>\Delta y_i</math> are odd. |
− | (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>, | + | ''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>. | then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 2)\equiv 0\;(mod \; 2)</math>. | ||
Line 37: | Line 39: | ||
Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is 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>, | + | ''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>. | then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+1^2)\;(mod \; 2)\equiv 0\;(mod \; 2)</math>. | ||
Line 43: | Line 45: | ||
Thus, for <math>r\equiv 0\;(mod \; 2)</math>, this case is a valid one. | 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>, | + | ''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>. | 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 '''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: |
if <math>(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 2)</math>, | if <math>(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 2)</math>, | ||
− | then for case (1): <math>(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+0,1+0) \;(mod \; 2) \equiv (1,1) \;(mod \; 2)</math> | + | then for ''case (1)'': <math>(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+0,1+0) \;(mod \; 2) \equiv (1,1) \;(mod \; 2)</math> |
− | and for case (2): <math>(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+1,1+1) \;(mod \; 2) \equiv (0,0) \;(mod \; 2)</math> | + | and for ''case (2)'': <math>(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+1,1+1) \;(mod \; 2) \equiv (0,0) \;(mod \; 2)</math> |
and <math>(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)</math> | and <math>(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)</math> | ||
Line 64: | Line 66: | ||
− | Now we look at the conditions for which <math>r</math> is divisible by | + | Now we look at the conditions for which <math>r</math> is divisible by '''3''' by looking at the following three cases: |
− | (4) When both <math>\Delta x_i</math> and <math>\Delta y_i</math> are divisible by <math>3</math>. | + | ''(4)'' When both <math>\Delta x_i</math> and <math>\Delta y_i</math> are divisible by <math>3</math>. |
− | (5) When one of them is not divisible by <math>3</math> and the other one is. | + | ''(5)'' When one of them is not divisible by <math>3</math> and the other one is. |
− | (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>, | + | ''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>. | then <math>(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 3)\equiv 0\;(mod \; 3)</math>. | ||
Line 78: | Line 80: | ||
Thus, for <math>r\equiv 0\;(mod \; 3)</math>, this case is a valid one. | 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>, | + | ''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>. | 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. | + | 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 (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>. | 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. |
− | Having proved that Case (4) is the only valid case for <math>r\equiv 0\;(mod \; 3)</math> we are going to see what happens when we start with a square that is <math>\equiv (1,1)\;(mod \; 3)</math> | + | Having proved that ''Case (4)'' is the only valid case for <math>r\equiv 0\;(mod \; 3)</math> we are going to see what happens when we start with a square that is <math>\equiv (1,1)\;(mod \; 3)</math> |
if <math>(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 3)</math>, then <math>(x_{i-1}+\Delta x_i ,y_{i-1}+\Delta y_i) \equiv (1+0,1+0) \;(mod \; 3) \equiv (1,1) \;(mod \; 3)</math>. | if <math>(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 3)</math>, then <math>(x_{i-1}+\Delta x_i ,y_{i-1}+\Delta y_i) \equiv (1+0,1+0) \;(mod \; 3) \equiv (1,1) \;(mod \; 3)</math>. | ||
Line 97: | Line 99: | ||
Since final square is <math>(20,1) \equiv (2,1) \;(mod \; 3) \not\equiv (1,1) \;(mod \; 3)</math>, then the task cannot be done if <math>r</math> is divisible by <math>3</math>. | Since final square is <math>(20,1) \equiv (2,1) \;(mod \; 3) \not\equiv (1,1) \;(mod \; 3)</math>, then the task cannot be done if <math>r</math> is divisible by <math>3</math>. | ||
+ | |||
+ | In summary the task cannot be done if <math>r</math> is divisible by <math>2</math> or <math>r</math> is divisible by <math>3</math>. | ||
− | + | '''Part (b):''' | |
When <math>r=73</math> we have <math>8^2+3^2=73</math> | When <math>r=73</math> we have <math>8^2+3^2=73</math> | ||
Line 128: | Line 132: | ||
− | + | '''Part (c):''' | |
When <math>r=97</math> we have <math>9^2+4^2=97</math> | When <math>r=97</math> we have <math>9^2+4^2=97</math> | ||
Line 138: | Line 142: | ||
Let <math>S</math> be a set of the squares of the rectangle with the condition <math>x_i \equiv \left\lceil \frac{y_i}{4} \right\rceil \;(mod \; 2)</math> for <math>(x_i,y_i)</math>. That is, the reminder of <math>x_i</math> when divided by 2 is the same as the reminder of <math>\left\lceil \frac{y_i}{4} \right\rceil</math> when divided by 2 where <math>\left\lceil k \right\rceil</math> is the smallest integer that is not less than <math>k</math>. If that condition is true, then <math>(x_i,y_i) \in S</math> | Let <math>S</math> be a set of the squares of the rectangle with the condition <math>x_i \equiv \left\lceil \frac{y_i}{4} \right\rceil \;(mod \; 2)</math> for <math>(x_i,y_i)</math>. That is, the reminder of <math>x_i</math> when divided by 2 is the same as the reminder of <math>\left\lceil \frac{y_i}{4} \right\rceil</math> when divided by 2 where <math>\left\lceil k \right\rceil</math> is the smallest integer that is not less than <math>k</math>. If that condition is true, then <math>(x_i,y_i) \in S</math> | ||
− | |||
− | subcase: <math>(x_{i+1},y_{i+1})=(x_i \pm 9,y_{i+1} \pm 4)</math>: | + | Now let's look at a ''case (c1)'' where <math>(x_i,y_i) \in S</math> and <math>x_i \equiv 0 \;(mod \; 2)</math>, thus <math>\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)</math>: |
+ | |||
+ | ''c1 subcase 1'' : <math>(x_{i+1},y_{i+1})=(x_i \pm 9,y_i \pm 4)</math>: | ||
+ | |||
+ | <math>(x_i \pm 9) \equiv (0 \pm 9)\;(mod \; 2) \equiv 1 \;(mod \; 2)</math> | ||
+ | |||
+ | and <math>\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)</math> | ||
+ | |||
+ | since <math>x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil \;(mod \; 2)</math>, then <math>(x_{i+1},y_{i+1}) \in S</math> for this subcase. | ||
+ | |||
+ | ''c1 subcase 2'' : <math>(x_{i+1},y_{i+1})=(x_i \pm 4,y_i \pm 9)</math>: | ||
+ | |||
+ | This move is not allowed because the only values of <math>1 \le y_i \le 12</math> such that <math>\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)</math> are <math>5,6,7,8</math>. Adding or subtracting 9 from any of these numbers will either make <math>y_{i+1}<0</math> or <math>y_{i+1}>12</math> and will put the piece outside of the board. | ||
+ | |||
+ | In summary, for ''case (c1)'', <math>(x_{i+1},y_{i+1}) \in S</math> | ||
+ | |||
+ | |||
+ | Now let's look at a ''case (c2)'' where <math>(x_i,y_i) \in S</math> and <math>x_i \equiv 1 \;(mod \; 2)</math>, thus <math>\left\lceil \frac{y_i}{4} \right\rceil \equiv 1 \;(mod \; 2)</math>: | ||
+ | |||
+ | ''c2 subcase 1'' : <math>(x_{i+1},y_{i+1})=(x_i \pm 9,y_i \pm 4)</math>: | ||
+ | |||
+ | <math>(x_i \pm 9) \equiv (1 \pm 9)\;(mod \; 2) \equiv 0 \;(mod \; 2)</math> | ||
+ | |||
+ | and <math>\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)</math> | ||
+ | |||
+ | since <math>x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil \;(mod \; 2)</math>, then <math>(x_{i+1},y_{i+1}) \in S</math> for this subcase. | ||
+ | |||
+ | ''c2 subcase 2'' : <math>(x_{i+1},y_{i+1})=(x_i \pm 4,y_i \pm 9)</math>: | ||
+ | |||
+ | <math>(x_i \pm 4) \equiv (1 \pm 4)\;(mod \; 2) \equiv 1 \;(mod \; 2)</math> | ||
+ | |||
+ | Notice that the only values of <math>1 \le y_i \le 12</math> such that <math>\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)</math> are <math>1,2,3,4,9,10,11,12</math>. Adding 9 to the values of 1,2, or 3 or subtracting 9 from the values of 10, 11, or 12, will result in <math>\left\lceil \frac{y_{i+1}}{4} \right\rceil \equiv 1 \;(mod \; 2)</math>. 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 <math>\left\lceil \frac{y_{i+1}}{4} \right\rceil \equiv 1 \;(mod \; 2)</math> | ||
+ | |||
+ | since <math>x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil \;(mod \; 2)</math>, then <math>(x_{i+1},y_{i+1}) \in S</math> for this subcase. | ||
+ | |||
+ | In summary, for ''case (c2)'', <math>(x_{i+1},y_{i+1}) \in S</math> | ||
+ | |||
+ | Therefore if <math>(x_{i},y_{i}) \in S</math> then <math>(x_{i+1},y_{i+1}) \in S</math> | ||
+ | |||
+ | Now we look at the starting point: <math>(1,1)</math>: | ||
+ | |||
+ | Since <math>1 \equiv 1\;(mod \; 2)</math> and <math>\left\lceil \frac{1}{4} \right\rceil \equiv 1\;(mod \; 2)</math>, then <math>(1,1) \in S</math> and all subsequent squares after that <math>\in S</math> | ||
+ | |||
+ | Now let's look at the end point: <math>(20,1)</math>: | ||
+ | |||
+ | Since <math>20 \equiv 0\;(mod \; 2)</math> and <math>\left\lceil \frac{1}{4} \right\rceil \equiv 1\;(mod \; 2)</math>, then <math>20 \not\equiv \left\lceil \frac{1}{4} \right\rceil \;(mod \; 2)</math> and <math>(20,1) \not\in S</math> | ||
+ | |||
+ | Since <math>(20,1) \not\in S</math>, then there are no valid moves starting from <math>(1,1)</math> that will end in <math>(20,1)</math> | ||
+ | |||
+ | Therefore the task cannot be done when <math>r=97</math>. | ||
+ | |||
+ | ~Tomas Diaz. orders@tomasdiaz.com | ||
{{alternate solutions}} | {{alternate solutions}} |
Latest revision as of 09:37, 21 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.
, and also .
Let ,
Then, for any given , we have for all
Part (a):
In order to find out the conditions for which is divisible by 2 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):
and for case (2):
and
This means that when is divisible by two, when starting at no matter how many moves you make all will either be or .
Since the ending coordinate is and , then the task cannot be done if is divisible by .
Now we look at the conditions for which is divisible by 3 by looking at the following three cases:
(4) When both and are divisible by .
(5) When one of them is not divisible by and the other one is.
(6) When neither nor is divisible by .
Case (4): Since and ,
then .
Thus, for , this case is a valid one.
Case (5): Since either or and the other ,
then .
Thus, for , this case is NOT a valid one.
Case (6): Since and ,
then .
Thus, for , this case is NOT a valid one.
Having proved that Case (4) is the only valid case for we are going to see what happens when we start with a square that is
if , then .
Therefore starting at any no matter how many moves the piece will always land at another square . Since we start at , then the piece will always land at squares that are .
Since final square is , then the task cannot be done if is divisible by .
In summary the task cannot be done if is divisible by or is divisible by .
Part (b):
When we have
Therefore the moves can have the following values:
Since we start at and we want to end at we can write the following valid moves:
Having shown that all moves comply with the possible values for and that all are inside the rectangular grid, then the task is possible when .
Part (c):
When we have
Therefore the moves can have the following values:
Let be a set of the squares of the rectangle with the condition for . That is, the reminder of when divided by 2 is the same as the reminder of when divided by 2 where is the smallest integer that is not less than . If that condition is true, then
Now let's look at a case (c1) where and , thus :
c1 subcase 1 : :
and
since , then for this subcase.
c1 subcase 2 : :
This move is not allowed because the only values of such that are . Adding or subtracting 9 from any of these numbers will either make or and will put the piece outside of the board.
In summary, for case (c1),
Now let's look at a case (c2) where and , thus :
c2 subcase 1 : :
and
since , then for this subcase.
c2 subcase 2 : :
Notice that the only values of such that are . Adding 9 to the values of 1,2, or 3 or subtracting 9 from the values of 10, 11, or 12, will result in . 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
since , then for this subcase.
In summary, for case (c2),
Therefore if then
Now we look at the starting point: :
Since and , then and all subsequent squares after that
Now let's look at the end point: :
Since and , then and
Since , then there are no valid moves starting from that will end in
Therefore the task cannot be done when .
~Tomas Diaz. orders@tomasdiaz.com
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 |