Difference between revisions of "2021 AIME I Problems/Problem 10"
MRENTHUSIASM (talk | contribs) m (→Solution 2 (Euclidean Algorithm and Generalization)) |
MRENTHUSIASM (talk | contribs) m (Use \ldots instead of \cdots for lists.) |
||
Line 8: | Line 8: | ||
==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> | 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> | ||
Line 23: | Line 23: | ||
<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] |
Revision as of 17:39, 8 September 2021
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
or
divides
, so 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
.
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 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.