Difference between revisions of "2001 AIME I Problems/Problem 11"

Revision as of 14:25, 8 May 2014

Problem

In a rectangular array of points, with 5 rows and $N$ columns, the points are numbered consecutively from left to right beginning with the top row. Thus the top row is numbered 1 through $N,$ the second row is numbered $N + 1$ through $2N,$ and so forth. Five points, $P_1, P_2, P_3, P_4,$ and $P_5,$ are selected so that each $P_i$ is in row $i.$ Let $x_i$ be the number associated with $P_i.$ Now renumber the array consecutively from top to bottom, beginning with the first column. Let $y_i$ be the number associated with $P_i$ after the renumbering. It is found that $x_1 = y_2,$ $x_2 = y_1,$ $x_3 = y_4,$ $x_4 = y_5,$ and $x_5 = y_3.$ Find the smallest possible value of $N.$

Solution

Let each point $P_i$ be in column $c_i$ . The numberings for $P_i$ can now be defined as follows. $\begin{align*}x_i &= (i - 1)N + c_i\\ y_i &= (c_i - 1)5 + i \end{align*}$

We can now convert the five given equalities. $\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}$ Equations $(1)$ and $(2)$ combine to form $N = 24c_2 - 19$ Similarly equations $(3)$ , $(4)$ , and $(5)$ combine to form $117N +51 = 124c_3$ Take this equation modulo 31 $24N+20\equiv 0 \pmod{31}$ And substitute for N $24 \cdot 24 c_2 - 24 \cdot 19 +20\equiv 0 \pmod{31}$ $18 c_2 \equiv 2 \pmod{31}$

Thus the smallest $c_2$ might be is $7$ and by substitution $N = 24 \cdot 7 - 19 = 149$

The column values can also easily be found by substitution $\begin{align*}c_1&=32\\ c_2&=7\\ c_3&=141\\ c_4&=88\\ c_5&=107 \end{align*}$ As these are all positive and less than $N$ , $\boxed{149}$ is the solution.

@@ Line 3: / Line 3: @@
 == 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.
 == 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

Page

Toolbox

Search

Difference between revisions of "2001 AIME I Problems/Problem 11"

Revision as of 14:25, 8 May 2014

Problem

Solution

See also