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
(→‎Sidenote)
 
(7 intermediate revisions by 7 users not shown)
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 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}}
+
{{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 12:51, 22 July 2020

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.

Sidenote

If we express all the $c_i$ in terms of $N$, we have \[24c_1=5N+23\] \[24c_2=N+19\] \[124c_3=117N+51\] \[124c_4=73N+35\] \[124c_5=89N+7\]

It turns out that there exists such an array satisfying the problem conditions if and only if \[N\equiv 149 \pmod{744}\]


In addition, the first two equation can be written $n = 5mod24$, and chasing variables in the last three equation gives us $89n + 7 = 124e$. With these two equations you may skip a lot of rewriting and testing. $\boxed{149}$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_11&oldid=128873"