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 "2001 AIME I Problems/Problem 11"

m
(solution by chess64)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
In a 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>
+
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 ==
−
{{solution}}
+
Let <math>P_{i} = (i,a_{i})</math>, where the first coordinate represents the row number and <math>a_i</math> represents the column number. Then <math>x_{1} = a_{1}</math>, <math>x_{2} = N + a_{2}</math>, <math>x_{3} = 2N + a_{3}</math>, etc. and <math>y_{1} = 5(a_{1} - 1) + 1</math>, <math>y_{2} = 5(a_{2} - 1) + 2</math>, etc. Now we get the system of equations:
 +
<cmath>
 +
\par \begin{align}a_{1} & = 5(a_{2} - 1) + 2 \\
 +
N + a_{2} & = 5(a_{1} - 1) + 1 \\
 +
2N + a_{3} & = 5(a_{4} - 1) + 4 \\
 +
3N + a_{4} & = 5(a_{5} - 1) + 5 \\
 +
4N + a_{5} & = 5(a_{3} - 1) + 3 \end{align}
 +
</cmath>
 +
We solve the system (the first two equations, and then the latter three) to get
 +
<cmath>
 +
\left(a_{1},a_{2},a_{3},a_{4},a_{5}\right) = \left(\frac {23 + 5N}{24},\frac {19 + N}{24},\frac {51 + 117N}{124},\frac {5 + 73N}{124},\frac {7 + 89N}{124}\right).
 +
</cmath>
 +
<math>a_{1},a_{2}</math> will be integers iff <math>N\equiv 5\pmod{24}</math> and <math>a_{3},a_{4},a_{5}</math> will be integers iff <math>N\equiv 25\pmod{124}</math>. Solving these [[Congruent (modular arithmetic)|congruence]]s simultaneously by standard methods gives <math>N\equiv \boxed{149}\pmod{744}</math>.
  
 
== See also ==
 
== See also ==
−
{{AIME box|year=2001|n=I|num-b=10|num-a=12}}
+
{{AIME box|year=2001|n=I|num-b=10|num-a=12|t=384200}}
 +
 
 +
[[Category:Intermediate Number Theory Problems]]

Revision as of 11:29, 15 June 2008

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 $P_{i} = (i,a_{i})$, where the first coordinate represents the row number and $a_i$ represents the column number. Then $x_{1} = a_{1}$, $x_{2} = N + a_{2}$, $x_{3} = 2N + a_{3}$, etc. and $y_{1} = 5(a_{1} - 1) + 1$, $y_{2} = 5(a_{2} - 1) + 2$, etc. Now we get the system of equations: \par \begin{align}a_{1} & = 5(a_{2} - 1) + 2 \\ N + a_{2} & = 5(a_{1} - 1) + 1 \\ 2N + a_{3} & = 5(a_{4} - 1) + 4 \\ 3N + a_{4} & = 5(a_{5} - 1) + 5 \\ 4N + a_{5} & = 5(a_{3} - 1) + 3 \end{align} We solve the system (the first two equations, and then the latter three) to get \[\left(a_{1},a_{2},a_{3},a_{4},a_{5}\right) = \left(\frac {23 + 5N}{24},\frac {19 + N}{24},\frac {51 + 117N}{124},\frac {5 + 73N}{124},\frac {7 + 89N}{124}\right).\] $a_{1},a_{2}$ will be integers iff $N\equiv 5\pmod{24}$ and $a_{3},a_{4},a_{5}$ will be integers iff $N\equiv 25\pmod{124}$. Solving these congruences simultaneously by standard methods gives $N\equiv \boxed{149}\pmod{744}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_11&oldid=26552"