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"

(I think the old one was #7 not #10; please let me know if I'm wrong.)
(Undo revision 190907 by Pappustheorem (talk) This was #7.)
(Tag: Undo)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
Find the number of pairs <math>(m,n)</math> of positive integers with <math>1\le m<n\le 30</math> such that there exists a real number <math>x</math> satisfying <cmath>\sin(mx)+\sin(nx)=2.</cmath>
+
Consider the sequence <math>(a_k)_{k\ge 1}</math> of positive rational numbers defined by <math>a_1 = \frac{2020}{2021}</math> and for <math>k\ge 1</math>, if <math>a_k = \frac{m}{n}</math> for relatively prime positive integers <math>m</math> and <math>n</math>, then
 +
 
 +
<cmath>a_{k+1} = \frac{m + 18}{n+19}.</cmath>Determine the sum of all positive integers <math>j</math> such that the rational number <math>a_j</math> can be written in the form <math>\frac{t}{t+1}</math> for some positive integer <math>t</math>.
  
 
==Solution 1==
 
==Solution 1==
−
The maximum value of <math>\sin \theta</math> is <math>1</math>, which is achieved at <math>\theta = \frac{\pi}{2}+2k\pi</math> for some integer <math>k</math>. This is left as an exercise to the reader.
+
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>.
−
 
 
−
This implies that <math>\sin(mx) = \sin(nx) = 1</math>, and that <math>mx = \frac{\pi}{2}+2a\pi</math> and <math>nx = \frac{\pi}{2}+2b\pi</math>, for integers <math>a, b</math>.
 
−
 
 
−
Taking their ratio, we have <cmath>\frac{mx}{nx} = \frac{\frac{\pi}{2}+2a\pi}{\frac{\pi}{2}+2b\pi} \implies \frac{m}{n} = \frac{4a + 1}{4b + 1} \implies \frac{m}{4a + 1} = \frac{n}{4b + 1} = k.</cmath>
 
−
It remains to find all <math>m, n</math> that satisfy this equation.
 
−
 
 
−
If <math>k = 1</math>, then <math>m \equiv n \equiv 1 \pmod 4</math>. This corresponds to choosing two elements from the set <math>\{1, 5, 9, 13, 17, 21, 25, 29\}</math>. There are <math>\binom 82</math> ways to do so.
 
−
 
 
−
If <math>k < 1</math>, by multiplying <math>m</math> and <math>n</math> by the same constant <math>c = \frac{1}{k}</math>, we have that <math>mc \equiv nc \equiv 1 \pmod 4</math>. Then either <math>m \equiv n \equiv 1 \pmod 4</math>, or <math>m \equiv n \equiv 3 \pmod 4</math>. But the first case was already counted, so we don't need to consider that case. The other case corresponds to choosing two numbers from the set <math>\{3, 7, 11, 15, 19, 23, 27\}</math>. There are <math>\binom 72</math> ways here.
 
−
 
 
−
Finally, if <math>k > 1</math>, note that <math>k</math> must be an integer. This means that <math>m, n</math> belong to the set <math>\{k, 5k, 9k, \dots\}</math>, or <math>\{3k, 7k, 11k, \dots\}</math>. Taking casework on <math>k</math>, we get the sets <math>\{2, 10, 18, 26\}, \{6, 14, 22, 30\}, \{4, 20\}, \{12, 28\}</math>. Some sets have been omitted; this is because they were counted in the other cases already. This sums to <math>\binom 42 + \binom 42 + \binom 22 + \binom 22</math>.
 
−
 
 
−
In total, there are <math>\binom 82 + \binom 72 + \binom 42 + \binom 42 + \binom 22 + \binom 22 = \boxed{63}</math> pairs of <math>(m, n)</math>.
 
−
 
 
−
This solution was brought to you by ~Leonard_my_dude~
 
−
 
 
−
==Solution 2==
 
−
In order for <math>\sin(mx) + \sin(nx) = 2</math>, <math>\sin(mx) = \sin(nx) = 1</math>.
 
−
 
 
−
This happens when
 
−
<math>mx \equiv nx \equiv \frac{\pi}{2} (</math>mod <math>2\pi).</math>
 
−
 
 
−
This means that <math>mx = \frac{\pi}{2} + 2\pi\alpha</math> and <math>nx = \frac{\pi}{2} + 2\pi\beta</math> for any integers <math>\alpha</math> and <math>\beta</math>.
 
−
 
 
−
As in Solution 1, take the ratio of the two equations:
 
−
<cmath>\frac{mx}{nx} = \frac{\frac{\pi}{2}+2\pi\alpha}{\frac{\pi}{2}+2\pi\beta} \implies \frac{m}{n} = \frac{\frac{1}{2}+2\alpha}{\frac{1}{2}+2\beta} \implies \frac{m}{n} = \frac{4\alpha+1}{4\beta+1}</cmath>
 
−
 
 
−
Now notice that the numerator and denominator of <math>\frac{4\alpha+1}{4\beta+1}</math> are both odd, which means that <math>m</math> and <math>n</math> have the same power of two (the powers of 2 cancel out).
 
−
 
 
−
Let the common power be <math>p</math>: then <math>m = 2^p\cdot a</math>, and <math>n = 2^p\cdot b</math> where <math>a</math> and <math>b</math> are integers between 1 and 30.
 
−
 
 
−
We can now rewrite the equation:
 
−
<cmath>\frac{2^p\cdot a}{2^p\cdot b} = \frac{4\alpha+1}{4\beta+1} \implies \frac{a}{b} = \frac{4\alpha+1}{4\beta+1}</cmath>
 
  
−
Now it is easy to tell that <math>a \equiv 1 (</math>mod <math>4)</math> and <math>b \equiv 1 (</math>mod <math>4)</math>. However, there is another case: that
+
==Solution 2 (Euclidean Algorithm and Generalization)==
 +
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.
  
−
<math>a \equiv 3 (</math>mod <math>4)</math> and <math>b \equiv 3 (</math>mod <math>4)</math>. This is because multiplying both <math>4\alpha+1</math> and <math>4\beta+1</math> by <math>-1</math> will not change the fraction, but each congruence will be changed to <math>-1 (</math>mod <math>4) \equiv 3 (</math>mod <math>4)</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>  
  
−
From the first set of congruences, we find that <math>a</math> and <math>b</math> can be two of
+
<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>
−
<math>\{1, 5, 9, \ldots, 29\}</math>.
 
  
−
From the second set of congruences, we find that <math>a</math> and <math>b</math> can be two of  
+
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
−
<math>\{3, 7, 11, \ldots, 27\}</math>.
+
<cmath>\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*}</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>
  
−
Now all we have to do is multiply by <math>2^p</math> to get back to <math>m</math> and <math>n</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}, \hspace{10mm} (*)</cmath> where <math>t=\frac{m-18}{k'+1}+18</math> must be a positive integer.
−
Let’s organize the solutions in order of increasing values of <math>p</math>, keeping in mind that <math>m</math> and <math>n</math> are bounded between 1 and 30.
 
  
−
For <math>p = 0</math> we get <math>\{1, 5, 9, \ldots, 29\}, \{3, 7, 11, \ldots, 27\}</math>.
+
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}
 +
& & & & & \\ [-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}</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>
  
−
For <math>p = 1</math> we get <math>\{2, 10, 18, 26\}, \{6, 14, 22, 30\}</math>
+
<b><u>Remark</u></b>
  
−
For <math>p = 2</math> we get <math>\{4, 20\}, \{12, 28\}</math>
+
Alternatively, from <math>(*)</math> we can set <cmath>\frac{m+18k'}{m+1+19k'}=\frac{t}{t+1}.</cmath>
 +
We cross-multiply, rearrange, and apply Simon's Favorite Factoring Trick to get <cmath>\left(k'+1\right)(t-18)=m-18.</cmath>
 +
Since <math>k'+1\geq2,</math> to find the smallest <math>k',</math> we need <math>k'+1</math> to be the smallest prime factor of <math>m-18.</math> Now we continue with the last two paragraphs of the solution above.
  
−
If we increase the value of <math>p</math> more, there will be less than two integers in our sets, so we are done there.
+
~MRENTHUSIASM
  
−
There are 8 numbers in the first set, 7 in the second, 4 in the third, 4 in the fourth, 2 in the fifth, and 2 in the sixth.
 
−
 
−
In each of these sets we can choose 2 numbers to be <math>m</math> and <math>n</math> and then assign them in increasing order. Thus there are:
 
−
 
−
<cmath>\dbinom{8}{2}+\dbinom{7}{2}+\dbinom{4}{2}+\dbinom{4}{2}+\dbinom{2}{2}+\dbinom{2}{2} = 28+21+6+6+1+1 = \boxed{63}</cmath> possible pairs <math>(m,n)</math> that satisfy the conditions.
 
−
 
−
-KingRavi
 
−
 
−
==Solution 3==
 
−
We know that the range of sine is between <math>-1</math> and <math>1</math>, inclusive.
 
−
 
−
Thus, the only way for the sum to be <math>2</math> is for <math>\sin(mx)=\sin(nx)=1</math>.
 
−
 
−
Note that <math>\sin(90+360k)=1</math>.
 
−
 
−
Assuming <math>mx</math> and <math>nx</math> are both positive, <math>m</math> and <math>n</math> could be <math>1,5,9,13,17,21,25,29</math>. There are <math>8</math> ways, so <math>\dbinom{8}{2}</math>.
 
−
 
−
If both are negative, <math>m</math> and <math>n</math> could be <math>3,7,11,15,19,23,27</math>. There are <math>7</math> ways, so <math>\dbinom{7}{2}</math>.
 
−
 
−
However, the pair <math>(1,5)</math> could also be <math>(2, 10)</math> and so on. The same goes for some other pairs.
 
−
 
−
In total there are <math>14</math> of these extra pairs.
 
−
 
−
The answer is <math>28+21+14 = \boxed{063}</math>.
 
−
 
−
==Remark==
 
−
The graphs of <math>r\leq\sin(m\theta)+\sin(n\theta)</math> and <math>r=2</math> are shown here in Desmos: https://www.desmos.com/calculator/busxadywja
 
−
 
−
Move the sliders around for <math>1\leq m \leq 29</math> and <math>2\leq m+1\leq n\leq30</math> to observe the geometric representation generated by each pair <math>(m,n).</math>
 
−
 
−
~MRENTHUSIASM (inspired by TheAMCHub)
 
  
 
==Video Solution==
 
==Video Solution==
−
https://youtu.be/O84aJ5OTZ2E
+
https://youtu.be/oiUcYn1uYMM ~Math Problem Solving Skills
  
−
~mathproblemsolvingskills
 
  
−
==Video Solution==
+
==Video Solution by Punxsutawney Phil==
−
https://www.youtube.com/watch?v=LUkQ7R1DqKo
+
https://youtube.com/watch?v=LIjTty3rVso
−
 
 
−
~Mathematical Dexterity
 
  
 
==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]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 13:54, 13 March 2023

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$ or $q+1$ divides $1001$, so 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}$.

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=190913"