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"
(Added in Solution 2)
Line 4: Line 4:
 
<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>.
 
<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==
+
==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> 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>.
 +
 +
==Solution 2 (Simon's Favorite Factoring Trick and Generalization)==
 +
<b>I am saving progress as I type this solution (to prevent work loss). Will finish up very soon. Please do not edit this solution. A million thanks.</b>
 +
 +
~MRENTHUSIASM
  
 
==Video Solution by Punxsutawney Phil==
 
==Video Solution by Punxsutawney Phil==

Revision as of 12:15, 17 March 2021

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 (Simon's Favorite Factoring Trick and Generalization)

I am saving progress as I type this solution (to prevent work loss). Will finish up very soon. Please do not edit this solution. A million thanks.

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_10&oldid=149654"