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 "2021 AIME I Problems/Problem 10"

m (→‎Solution 2 (Euclidean Algorithm and Generalization): "is" -> "must be" for emphasis purpose.)
(→‎Video Solution)
 
(29 intermediate revisions by 8 users not shown)
Line 5: Line 5:
  
 
==Solution 1==
 
==Solution 1==
−
We know that <math>a_{1}=\tfrac{t}{t+1}</math> when <math>t=2020</math> so <math>1</math> is a possible value of <math>j</math>. Note also that <math>a_{2}=\tfrac{2038}{2040}=\tfrac{1019}{1020}=\tfrac{t}{t+1}</math> for <math>t=1019</math>. Then <math>a_{2+q}=\tfrac{1019+18q}{1020+19q}</math> unless <math>1019+18q</math> and <math>1020+19q</math> are not relatively prime which happens when <math>q+1</math> divides <math>18q+1019</math> or <math>q+1</math> divides <math>1001</math>, so the least value of <math>q</math> is <math>6</math> and <math>j=2+6=8</math>. We know <math>a_{8}=\tfrac{1019+108}{1020+114}=\tfrac{1127}{1134}=\tfrac{161}{162}</math>. Now <math>a_{8+q}=\tfrac{161+18q}{162+19q}</math> unless <math>18q+161</math> and <math>19q+162</math> are not relatively prime which happens the first time <math>q+1</math> divides <math>18q+161</math> or <math>q+1</math> divides <math>143</math> or <math>q=10</math>, and <math>j=8+10=18</math>. We have <math>a_{18}=\tfrac{161+180}{162+190}=\tfrac{341}{352}=\tfrac{31}{32}</math>. Now <math>a_{18+q}=\tfrac{31+18q}{32+19q}</math> unless <math>18q+31</math> and <math>19q+32</math> are not relatively prime. This happens the first time <math>q+1</math> divides <math>18q+31</math> implying <math>q+1</math> divides <math>13</math>, which is prime so <math>q=12</math> and <math>j=18+12=30</math>. We have <math>a_{30}=\tfrac{31+216}{32+228}=\tfrac{247}{260}=\tfrac{19}{20}</math>. We have <math>a_{30+q}=\tfrac{18q+19}{19q+20}</math>, which is always reduced by EA, so the sum of all <math>j</math> is <math>1+2+8+18+30=\boxed{059}</math>.
+
We know that <math>a_{1}=\tfrac{t}{t+1}</math> when <math>t=2020</math> so <math>1</math> is a possible value of <math>j</math>. Note also that <math>a_{2}=\tfrac{2038}{2040}=\tfrac{1019}{1020}=\tfrac{t}{t+1}</math> for <math>t=1019</math>. Then <math>a_{2+q}=\tfrac{1019+18q}{1020+19q}</math> unless <math>1019+18q</math> and <math>1020+19q</math> are not relatively prime which happens when <math>q+1</math> divides <math>18q+1019</math> (by the Euclidean Algorithm), or <math>q+1</math> divides <math>1001</math>. Thus, the least value of <math>q</math> is <math>6</math> and <math>j=2+6=8</math>. We know <math>a_{8}=\tfrac{1019+108}{1020+114}=\tfrac{1127}{1134}=\tfrac{161}{162}</math>. Now <math>a_{8+q}=\tfrac{161+18q}{162+19q}</math> unless <math>18q+161</math> and <math>19q+162</math> are not relatively prime which happens the first time <math>q+1</math> divides <math>18q+161</math> or <math>q+1</math> divides <math>143</math> or <math>q=10</math>, and <math>j=8+10=18</math>. We have <math>a_{18}=\tfrac{161+180}{162+190}=\tfrac{341}{352}=\tfrac{31}{32}</math>. Now <math>a_{18+q}=\tfrac{31+18q}{32+19q}</math> unless <math>18q+31</math> and <math>19q+32</math> are not relatively prime. This happens the first time <math>q+1</math> divides <math>18q+31</math> implying <math>q+1</math> divides <math>13</math>, which is prime so <math>q=12</math> and <math>j=18+12=30</math>. We have <math>a_{30}=\tfrac{31+216}{32+228}=\tfrac{247}{260}=\tfrac{19}{20}</math>. We have <math>a_{30+q}=\tfrac{18q+19}{19q+20}</math>, which is always reduced by EA, so the sum of all <math>j</math> is <math>1+2+8+18+30=\boxed{059}</math>.
 +
 
 +
~sugar_rush
 +
 
 +
<b><u>Remark</u></b>
 +
 
 +
Whenever a fraction is in the form <math>\frac{t}{t+1}</math> in lowest terms, the difference between the numerator and the denominator in the original fraction will always divide the numerator. We can model <math>a_j</math> as <math>\frac{m+18k}{m+19k+1}</math> (not necessarily simplified) if <math>a_{j-k}=\frac{m}{m+1}</math> for integers <math>j</math> and <math>k</math>. We want the least <math>k</math> such that <math>\gcd(k+1,{m+18k})\neq1</math>. Let <math>d</math> be a divisor of both <math>k+1</math> and <math>m+18k</math>, then <math>d\mid18k+18</math>, so <math>d\mid{m-18}</math>. This follows from the Euclidean Algorithm.
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Magnetoninja Magnetoninja]
  
 
==Solution 2 (Euclidean Algorithm and Generalization)==
 
==Solution 2 (Euclidean Algorithm and Generalization)==
−
Let <math>a_{j_1}, a_{j_2}, a_{j_3}, \cdots, a_{j_u}</math> be all terms in the form <math>\frac{t}{t+1},</math> where <math>j_1<j_2<j_3<\cdots<j_u,</math> and <math>t</math> is some positive integer. We wish to find <math>\sum_{i=1}^{u}{j_i}.</math> Suppose <math>a_{j_i}=\frac{m}{m+1}</math> for some positive integer <math>m.</math>  
+
Let <math>a_{j_1}, a_{j_2}, a_{j_3}, \ldots, a_{j_u}</math> be all terms in the form <math>\frac{t}{t+1},</math> where <math>j_1<j_2<j_3<\cdots<j_u,</math> and <math>t</math> is some positive integer.
 +
 
 +
We wish to find <math>\sum_{i=1}^{u}{j_i}.</math> Suppose <math>a_{j_i}=\frac{m}{m+1}</math> for some positive integer <math>m.</math>  
  
 
<i><b>To find <math>\boldsymbol{a_{j_{i+1}},}</math> we look for the smallest positive integer <math>\boldsymbol{k'}</math> for which <cmath>\boldsymbol{a_{j_{i+1}}=a_{j_i+k'}=\frac{m+18k'}{m+1+19k'}}</cmath> is reducible:</b></i>
 
<i><b>To find <math>\boldsymbol{a_{j_{i+1}},}</math> we look for the smallest positive integer <math>\boldsymbol{k'}</math> for which <cmath>\boldsymbol{a_{j_{i+1}}=a_{j_i+k'}=\frac{m+18k'}{m+1+19k'}}</cmath> is reducible:</b></i>
  
−
If <math>\frac{m+18k'}{m+1+19k'}</math> is reducible, then there exists a common factor <math>d>1</math> for <math>m+18k'</math> and <math>m+1+19k'.</math> By the Euclidean Algorithm, we have
+
If <math>\frac{m+18k'}{m+1+19k'}</math> is reducible, then there exists a common factor <math>d>1</math> for <math>m+18k'</math> and <math>m+1+19k'.</math> By the [[Euclidean algorithm|Euclidean Algorithm]], we have
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
−
d|m+18k' \text{ and } d|m+1+19k' &\Longrightarrow d|k'+1 \text{ and } d|m+18k' \\
+
d\mid m+18k' \text{ and } d\mid m+1+19k' &\implies d\mid m+18k' \text{ and } d\mid k'+1 \\
−
&\Longrightarrow d|m-18 \text{ and } d|k'+1.
+
&\implies d\mid m-18 \text{ and } d\mid k'+1.
 
\end{align*}</cmath>
 
\end{align*}</cmath>
 
Since <math>m-18</math> and <math>k'+1</math> are not relatively prime, and <math>m</math> is fixed, the smallest value of <math>k'</math> such that <math>\frac{m+18k'}{m+1+19k'}</math> is reducible occurs when <math>k'+1</math> is the smallest prime factor of <math>m-18.</math>
 
Since <math>m-18</math> and <math>k'+1</math> are not relatively prime, and <math>m</math> is fixed, the smallest value of <math>k'</math> such that <math>\frac{m+18k'}{m+1+19k'}</math> is reducible occurs when <math>k'+1</math> is the smallest prime factor of <math>m-18.</math>
  
−
<i><b>We will prove that for such value of <math>\boldsymbol{k',}</math> the number <math>\boldsymbol{a_{j_{i+1}}}</math> can be written in the form <math>\boldsymbol{\frac{t}{t+1}:}</math></b></i> <cmath>a_{j_{i+1}}=a_{j_i+k'}=\frac{m+18k'}{m+1+19k'}=\frac{(m-18)+18(k'+1)}{(m-18)+19(k'+1)}=\frac{\frac{m-18}{k'+1}+18}{\frac{m-18}{k'+1}+19}, \ \ (*)</cmath> where <math>t=\frac{m-18}{k'+1}+18</math> must be a positive integer.
+
<i><b>We will prove that for such value of <math>\boldsymbol{k',}</math> the number <math>\boldsymbol{a_{j_{i+1}}}</math> can be written in the form <math>\boldsymbol{\frac{t}{t+1}:}</math></b></i> <cmath>a_{j_{i+1}}=a_{j_i+k'}=\frac{m+18k'}{m+1+19k'}=\frac{(m-18)+18(k'+1)}{(m-18)+19(k'+1)}=\frac{\frac{m-18}{k'+1}+18}{\frac{m-18}{k'+1}+19}, \hspace{10mm} (*)</cmath> where <math>t=\frac{m-18}{k'+1}+18</math> must be a positive integer.
  
−
We start with <math>m=2020</math> and <math>a_{j_1}=a_1=\frac{2020}{2021},</math> then find <math>a_{j_2}, a_{j_3}, \cdots, a_{j_u}</math> by filling out the table below recursively:
+
We start with <math>m=2020</math> and <math>a_{j_1}=a_1=\frac{2020}{2021},</math> then find <math>a_{j_2}, a_{j_3}, \ldots, a_{j_u}</math> by filling out the table below recursively:
−
<cmath>\begin{array}{c|c|c|c|c|l}  
+
<cmath>\begin{array}{c|c|c|c|c|c}  
 
& & & & & \\ [-2ex]
 
& & & & & \\ [-2ex]
 
\boldsymbol{i} & \boldsymbol{m} & \boldsymbol{m-18} & \boldsymbol{k'+1} & \boldsymbol{k'} & \boldsymbol{a_{j_{i+1}} \left(\textbf{by } (*)\right)} \\ [0.5ex]  
 
\boldsymbol{i} & \boldsymbol{m} & \boldsymbol{m-18} & \boldsymbol{k'+1} & \boldsymbol{k'} & \boldsymbol{a_{j_{i+1}} \left(\textbf{by } (*)\right)} \\ [0.5ex]  
−
\hline\hline   
+
\hline   
 
& & & & & \\ [-1.5ex]  
 
& & & & & \\ [-1.5ex]  
−
1 & 2020 & 2002 & 2 & 1 & \ \ \ \ a_2 = \frac{1019}{1020} \\ [1ex]     
+
1 & 2020 & 2002 & 2 & 1 & \hspace{4.25mm} a_2 = \frac{1019}{1020} \\ [1ex]     
−
2 & 1019 & 1001 & 7 & 6 & \ \ \ \ a_8 = \frac{161}{162} \\ [1ex]     
+
2 & 1019 & 1001 & 7 & 6 & \hspace{2.75mm} a_8 = \frac{161}{162} \\ [1ex]     
−
3 & 161 & 143 & 11 & 10 & \ \ \ a_{18} = \frac{31}{32} \\ [1ex]
+
3 & 161 & 143 & 11 & 10 & a_{18} = \frac{31}{32} \\ [1ex]
−
4 & 31 & 13 & 13 & 12 & \ \ \ a_{30} = \frac{19}{20} \\ [1ex]
+
4 & 31 & 13 & 13 & 12 & a_{30} = \frac{19}{20} \\ [1ex]
−
5 & 19 & 1 & \text{N/A} & \text{N/A} & \ \ \ \ \ \ \ \text{N/A} \\ [1ex]
+
5 & 19 & 1 & \text{N/A} & \text{N/A} & \text{N/A} \\ [1ex]
 
\end{array}</cmath>
 
\end{array}</cmath>
 
As <math>\left(j_1,j_2,j_3,j_4,j_5\right)=(1,2,8,18,30),</math> the answer is <math>\sum_{i=1}^{5}{j_i}=\boxed{059}.</math>
 
As <math>\left(j_1,j_2,j_3,j_4,j_5\right)=(1,2,8,18,30),</math> the answer is <math>\sum_{i=1}^{5}{j_i}=\boxed{059}.</math>
Line 42: Line 52:
  
 
~MRENTHUSIASM
 
~MRENTHUSIASM
 +
 +
==Video Solution==
 +
https://youtu.be/oiUcYn1uYMM
 +
 +
~Math Problem Solving Skills
  
 
==Video Solution by Punxsutawney Phil==
 
==Video Solution by Punxsutawney Phil==
 
https://youtube.com/watch?v=LIjTty3rVso
 
https://youtube.com/watch?v=LIjTty3rVso
  
−
==See also==
+
==See Also==
 
{{AIME box|year=2021|n=I|num-b=9|num-a=11}}
 
{{AIME box|year=2021|n=I|num-b=9|num-a=11}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 04:28, 14 November 2024

Problem

Consider the sequence $(a_k)_{k\ge 1}$ of positive rational numbers defined by $a_1 = \frac{2020}{2021}$ and for $k\ge 1$, if $a_k = \frac{m}{n}$ for relatively prime positive integers $m$ and $n$, then

\[a_{k+1} = \frac{m + 18}{n+19}.\]Determine the sum of all positive integers $j$ such that the rational number $a_j$ can be written in the form $\frac{t}{t+1}$ for some positive integer $t$.

Solution 1

We know that $a_{1}=\tfrac{t}{t+1}$ when $t=2020$ so $1$ is a possible value of $j$. Note also that $a_{2}=\tfrac{2038}{2040}=\tfrac{1019}{1020}=\tfrac{t}{t+1}$ for $t=1019$. Then $a_{2+q}=\tfrac{1019+18q}{1020+19q}$ unless $1019+18q$ and $1020+19q$ are not relatively prime which happens when $q+1$ divides $18q+1019$ (by the Euclidean Algorithm), or $q+1$ divides $1001$. Thus, the least value of $q$ is $6$ and $j=2+6=8$. We know $a_{8}=\tfrac{1019+108}{1020+114}=\tfrac{1127}{1134}=\tfrac{161}{162}$. Now $a_{8+q}=\tfrac{161+18q}{162+19q}$ unless $18q+161$ and $19q+162$ are not relatively prime which happens the first time $q+1$ divides $18q+161$ or $q+1$ divides $143$ or $q=10$, and $j=8+10=18$. We have $a_{18}=\tfrac{161+180}{162+190}=\tfrac{341}{352}=\tfrac{31}{32}$. Now $a_{18+q}=\tfrac{31+18q}{32+19q}$ unless $18q+31$ and $19q+32$ are not relatively prime. This happens the first time $q+1$ divides $18q+31$ implying $q+1$ divides $13$, which is prime so $q=12$ and $j=18+12=30$. We have $a_{30}=\tfrac{31+216}{32+228}=\tfrac{247}{260}=\tfrac{19}{20}$. We have $a_{30+q}=\tfrac{18q+19}{19q+20}$, which is always reduced by EA, so the sum of all $j$ is $1+2+8+18+30=\boxed{059}$.

~sugar_rush

Remark

Whenever a fraction is in the form $\frac{t}{t+1}$ in lowest terms, the difference between the numerator and the denominator in the original fraction will always divide the numerator. We can model $a_j$ as $\frac{m+18k}{m+19k+1}$ (not necessarily simplified) if $a_{j-k}=\frac{m}{m+1}$ for integers $j$ and $k$. We want the least $k$ such that $\gcd(k+1,{m+18k})\neq1$. Let $d$ be a divisor of both $k+1$ and $m+18k$, then $d\mid18k+18$, so $d\mid{m-18}$. This follows from the Euclidean Algorithm.

~Magnetoninja

Solution 2 (Euclidean Algorithm and Generalization)

Let $a_{j_1}, a_{j_2}, a_{j_3}, \ldots, a_{j_u}$ be all terms in the form $\frac{t}{t+1},$ where $j_1<j_2<j_3<\cdots<j_u,$ and $t$ is some positive integer.

We wish to find $\sum_{i=1}^{u}{j_i}.$ Suppose $a_{j_i}=\frac{m}{m+1}$ for some positive integer $m.$

To find $\boldsymbol{a_{j_{i+1}},}$ we look for the smallest positive integer $\boldsymbol{k'}$ for which \[\boldsymbol{a_{j_{i+1}}=a_{j_i+k'}=\frac{m+18k'}{m+1+19k'}}\] is reducible:

If $\frac{m+18k'}{m+1+19k'}$ is reducible, then there exists a common factor $d>1$ for $m+18k'$ and $m+1+19k'.$ By the Euclidean Algorithm, we have \begin{align*} d\mid m+18k' \text{ and } d\mid m+1+19k' &\implies d\mid m+18k' \text{ and } d\mid k'+1 \\ &\implies d\mid m-18 \text{ and } d\mid k'+1. \end{align*} Since $m-18$ and $k'+1$ are not relatively prime, and $m$ is fixed, the smallest value of $k'$ such that $\frac{m+18k'}{m+1+19k'}$ is reducible occurs when $k'+1$ is the smallest prime factor of $m-18.$

We will prove that for such value of $\boldsymbol{k',}$ the number $\boldsymbol{a_{j_{i+1}}}$ can be written in the form $\boldsymbol{\frac{t}{t+1}:}$ \[a_{j_{i+1}}=a_{j_i+k'}=\frac{m+18k'}{m+1+19k'}=\frac{(m-18)+18(k'+1)}{(m-18)+19(k'+1)}=\frac{\frac{m-18}{k'+1}+18}{\frac{m-18}{k'+1}+19}, \hspace{10mm} (*)\] where $t=\frac{m-18}{k'+1}+18$ must be a positive integer.

We start with $m=2020$ and $a_{j_1}=a_1=\frac{2020}{2021},$ then find $a_{j_2}, a_{j_3}, \ldots, a_{j_u}$ by filling out the table below recursively: \[\begin{array}{c|c|c|c|c|c} & & & & & \\ [-2ex] \boldsymbol{i} & \boldsymbol{m} & \boldsymbol{m-18} & \boldsymbol{k'+1} & \boldsymbol{k'} & \boldsymbol{a_{j_{i+1}} \left(\textbf{by } (*)\right)} \\ [0.5ex] \hline & & & & & \\ [-1.5ex] 1 & 2020 & 2002 & 2 & 1 & \hspace{4.25mm} a_2 = \frac{1019}{1020} \\ [1ex] 2 & 1019 & 1001 & 7 & 6 & \hspace{2.75mm} a_8 = \frac{161}{162} \\ [1ex] 3 & 161 & 143 & 11 & 10 & a_{18} = \frac{31}{32} \\ [1ex] 4 & 31 & 13 & 13 & 12 & a_{30} = \frac{19}{20} \\ [1ex] 5 & 19 & 1 & \text{N/A} & \text{N/A} & \text{N/A} \\ [1ex] \end{array}\] As $\left(j_1,j_2,j_3,j_4,j_5\right)=(1,2,8,18,30),$ the answer is $\sum_{i=1}^{5}{j_i}=\boxed{059}.$

Remark

Alternatively, from $(*)$ we can set \[\frac{m+18k'}{m+1+19k'}=\frac{t}{t+1}.\] We cross-multiply, rearrange, and apply Simon's Favorite Factoring Trick to get \[\left(k'+1\right)(t-18)=m-18.\] Since $k'+1\geq2,$ to find the smallest $k',$ we need $k'+1$ to be the smallest prime factor of $m-18.$ Now we continue with the last two paragraphs of the solution above.

~MRENTHUSIASM

Video Solution

https://youtu.be/oiUcYn1uYMM

~Math Problem Solving Skills

Video Solution by Punxsutawney Phil

https://youtube.com/watch?v=LIjTty3rVso

See Also

2021 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
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=2021_AIME_I_Problems/Problem_10&oldid=233789"