Difference between revisions of "2001 AIME I Problems/Problem 11"
I_like_pie (talk | contribs) |
Jackshi2006 (talk | contribs) (→Sidenote) |
||
(8 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | In a [[rectangle|rectangular]] array of points, with 5 rows and <math>N</math> columns, the points are numbered consecutively from left to right beginning with the top row. Thus the top row is numbered 1 through <math>N,</math> the second row is numbered <math>N + 1</math> through <math>2N,</math> and so forth. Five points, <math>P_1, P_2, P_3, P_4,</math> and <math>P_5,</math> are selected so that each <math>P_i</math> is in row <math>i.</math> Let <math>x_i</math> be the number associated with <math>P_i.</math> Now renumber the array consecutively from top to bottom, beginning with the first column. Let <math>y_i</math> be the number associated with <math>P_i</math> after the renumbering. It is found that <math>x_1 = y_2,</math> <math>x_2 = y_1,</math> <math>x_3 = y_4,</math> <math>x_4 = y_5,</math> and <math>x_5 = y_3.</math> Find the smallest possible value of <math>N.</math> | ||
== Solution == | == Solution == | ||
+ | |||
+ | Let each point <math>P_i</math> be in column <math>c_i</math>. The numberings for <math>P_i</math> can now be defined as follows. | ||
+ | <cmath>\begin{align*}x_i &= (i - 1)N + c_i\\ | ||
+ | y_i &= (c_i - 1)5 + i | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | We can now convert the five given equalities. | ||
+ | <cmath>\begin{align}x_1&=y_2 & \Longrightarrow & & c_1 &= 5 c_2-3\\ | ||
+ | x_2&=y_1 & \Longrightarrow & & N+c_2 &= 5 c_1-4\\ | ||
+ | x_3&=y_4 & \Longrightarrow & & 2 N+c_3 &= 5 c_4-1\\ | ||
+ | x_4&=y_5 & \Longrightarrow & & 3 N+c_4 &= 5 c_5\\ | ||
+ | x_5&=y_3 & \Longrightarrow & & 4 N+c_5 &= 5 c_3-2 | ||
+ | \end{align}</cmath> | ||
+ | Equations <math>(1)</math> and <math>(2)</math> combine to form | ||
+ | <cmath>N = 24c_2 - 19</cmath> | ||
+ | Similarly equations <math>(3)</math>, <math>(4)</math>, and <math>(5)</math> combine to form | ||
+ | <cmath>117N +51 = 124c_3</cmath> | ||
+ | Take this equation modulo 31 | ||
+ | <cmath>24N+20\equiv 0 \pmod{31}</cmath> | ||
+ | And substitute for N | ||
+ | <cmath>24 \cdot 24 c_2 - 24 \cdot 19 +20\equiv 0 \pmod{31}</cmath> | ||
+ | <cmath>18 c_2 \equiv 2 \pmod{31}</cmath> | ||
+ | |||
+ | Thus the smallest <math>c_2</math> might be is <math>7</math> and by substitution <math>N = 24 \cdot 7 - 19 = 149</math> | ||
+ | |||
+ | The column values can also easily be found by substitution | ||
+ | <cmath>\begin{align*}c_1&=32\\ | ||
+ | c_2&=7\\ | ||
+ | c_3&=141\\ | ||
+ | c_4&=88\\ | ||
+ | c_5&=107 | ||
+ | \end{align*}</cmath> | ||
+ | As these are all positive and less than <math>N</math>, <math>\boxed{149}</math> is the solution. | ||
+ | |||
+ | == Sidenote == | ||
+ | If we express all the <math>c_i</math> in terms of <math>N</math>, we have | ||
+ | <cmath>24c_1=5N+23</cmath> | ||
+ | <cmath>24c_2=N+19</cmath> | ||
+ | <cmath>124c_3=117N+51</cmath> | ||
+ | <cmath>124c_4=73N+35</cmath> | ||
+ | <cmath>124c_5=89N+7</cmath> | ||
+ | |||
+ | It turns out that there exists such an array satisfying the problem conditions if and only if | ||
+ | <cmath>N\equiv 149 \pmod{744}</cmath> | ||
+ | |||
+ | |||
+ | |||
+ | In addition, the first two equation can be written <math>n = 5mod24</math>, and chasing variables in the last three equation gives us <math>89n + 7 = 124e</math>. With these two equations you may skip a lot of rewriting and testing. <math>\boxed{149}</math> still appears as our answer. | ||
+ | |||
+ | |||
+ | -jackshi2006 | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=2001|n=I|num-b=10|num-a=12|t=384200}} | |
− | |||
− | |||
− | + | [[Category:Intermediate Number Theory Problems]] | |
+ | {{MAA Notice}} |
Latest revision as of 13:51, 22 July 2020
Contents
Problem
In a rectangular array of points, with 5 rows and columns, the points are numbered consecutively from left to right beginning with the top row. Thus the top row is numbered 1 through
the second row is numbered
through
and so forth. Five points,
and
are selected so that each
is in row
Let
be the number associated with
Now renumber the array consecutively from top to bottom, beginning with the first column. Let
be the number associated with
after the renumbering. It is found that
and
Find the smallest possible value of
Solution
Let each point be in column
. The numberings for
can now be defined as follows.
We can now convert the five given equalities.
Equations
and
combine to form
Similarly equations
,
, and
combine to form
Take this equation modulo 31
And substitute for N
Thus the smallest might be is
and by substitution
The column values can also easily be found by substitution
As these are all positive and less than
,
is the solution.
Sidenote
If we express all the in terms of
, we have
It turns out that there exists such an array satisfying the problem conditions if and only if
In addition, the first two equation can be written , and chasing variables in the last three equation gives us
. With these two equations you may skip a lot of rewriting and testing.
still appears as our answer.
-jackshi2006
See also
2001 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.