Difference between revisions of "2021 AIME I Problems/Problem 10"
MRENTHUSIASM (talk | contribs) m (→Solution 2 (Euclidean Algorithm and Generalization)) |
Adam zheng (talk | contribs) (→Solution 1) |
||
(22 intermediate revisions by 7 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>, | + | 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}, \ | + | 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 | + | d\mid m+18k' \text{ and } d\mid m+1+19k' &\implies d\mid m+18k' \text{ and } d\mid k'+1 \\ |
− | &\implies d | + | &\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> | ||
Line 21: | Line 31: | ||
<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. | <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}, \ | + | 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|c} | <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 | |
& & & & & \\ [-1.5ex] | & & & & & \\ [-1.5ex] | ||
1 & 2020 & 2002 & 2 & 1 & \hspace{4.25mm} a_2 = \frac{1019}{1020} \\ [1ex] | 1 & 2020 & 2002 & 2 & 1 & \hspace{4.25mm} a_2 = \frac{1019}{1020} \\ [1ex] | ||
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 | + | ==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 16:30, 26 January 2024
Contents
Problem
Consider the sequence of positive rational numbers defined by
and for
, if
for relatively prime positive integers
and
, then
Determine the sum of all positive integers
such that the rational number
can be written in the form
for some positive integer
.
Solution 1
We know that when
so
is a possible value of
. Note also that
for
. Then
unless
and
are not relatively prime which happens when
divides
(by the Euclidean Algorithm), or
divides
. Thus, the least value of
is
and
. We know
. Now
unless
and
are not relatively prime which happens the first time
divides
or
divides
or
, and
. We have
. Now
unless
and
are not relatively prime. This happens the first time
divides
implying
divides
, which is prime so
and
. We have
. We have
, which is always reduced by EA, so the sum of all
is
.
~sugar_rush
Remark
Whenever a fraction is in the form in lowest terms, the difference between the numerator and the denominator in the original fraction will always divide the numerator. We can model
as
(not necessarily simplified) if
for integers
and
. We want the least
such that
. Let
be a divisor of both
and
, then
, so
. This follows from the Euclidean Algorithm.
Solution 2 (Euclidean Algorithm and Generalization)
Let be all terms in the form
where
and
is some positive integer.
We wish to find Suppose
for some positive integer
To find we look for the smallest positive integer
for which
is reducible:
If is reducible, then there exists a common factor
for
and
By the Euclidean Algorithm, we have
Since
and
are not relatively prime, and
is fixed, the smallest value of
such that
is reducible occurs when
is the smallest prime factor of
We will prove that for such value of the number
can be written in the form
where
must be a positive integer.
We start with and
then find
by filling out the table below recursively:
As
the answer is
Remark
Alternatively, from we can set
We cross-multiply, rearrange, and apply Simon's Favorite Factoring Trick to get
Since
to find the smallest
we need
to be the smallest prime factor of
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.