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 "2018 AMC 12A Problems/Problem 19"

m
(→‎Solution 2)
 
(21 intermediate revisions by 4 users not shown)
Line 3: Line 3:
 
Let <math>A</math> be the set of positive integers that have no prime factors other than <math>2</math>, <math>3</math>, or <math>5</math>. The infinite sum <cmath>\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} + \frac{1}{12} + \frac{1}{15} + \frac{1}{16} + \frac{1}{18} + \frac{1}{20} + \cdots</cmath>of the reciprocals of the elements of <math>A</math> can be expressed as <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. What is <math>m+n</math>?
 
Let <math>A</math> be the set of positive integers that have no prime factors other than <math>2</math>, <math>3</math>, or <math>5</math>. The infinite sum <cmath>\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} + \frac{1}{12} + \frac{1}{15} + \frac{1}{16} + \frac{1}{18} + \frac{1}{20} + \cdots</cmath>of the reciprocals of the elements of <math>A</math> can be expressed as <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. What is <math>m+n</math>?
  
−
<math>\textbf{(A)} \text{ 16} \qquad \textbf{(B)} \text{ 17} \qquad \textbf{(C)} \text{ 19} \qquad \textbf{(D)} \text{ 23} \qquad \textbf{(E)} \text{ 36}</math>
+
<math>\textbf{(A) } 16 \qquad \textbf{(B) } 17 \qquad \textbf{(C) } 19 \qquad \textbf{(D) } 23 \qquad \textbf{(E) } 36</math>
  
−
== Solution 1==
+
== Solution 1 ==
−
The terms of the infinite sum and the fractions of the form <math>\frac{1}{2^a3^b5^c}</math> (for some nonnegative integers <math>a,b,</math> and <math>c</math>) have one-to-one correspondence.
+
Note that the fractions of the form <math>\frac{1}{2^a3^b5^c},</math> where <math>a,b,</math> and <math>c</math> are nonnegative integers, span all terms of the infinite sum.
  
−
The infinite sum is
+
Therefore, the infinite sum becomes
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
−
\sum_{a=0}^{\infty}\sum_{b=0}^{\infty}\sum_{c=0}^{\infty}
+
\sum_{a=0}^{\infty}\sum_{b=0}^{\infty}\sum_{c=0}^{\infty}\frac{1}{2^a3^b5^c} &= \left(\sum_{a=0}^{\infty}\frac{1}{2^a}\right)\cdot\left(\sum_{b=0}^{\infty}\frac{1}{3^b}\right)\cdot\left(\sum_{c=0}^{\infty}\frac{1}{5^c}\right) \\
 +
&= \frac{1}{1-\frac12}\cdot\frac{1}{1-\frac13}\cdot\frac{1}{1-\frac15} \\
 +
&= 2\cdot\frac32\cdot\frac54 \\
 +
&= \frac{15}{4}
 
\end{align*}</cmath>
 
\end{align*}</cmath>
−
by a product of geometric series.
+
by a product of geometric series, from which the answer is <math>15+4=\boxed{\textbf{(C) } 19}.</math>
  
−
<b>EMERGENCY ... WILL FINISH OFF SOON.</b>
+
~athens2016 ~MRENTHUSIASM
  
−
~athens2016 (Solution)
+
== Solution 2 ==
 +
This solution is the same as Solution 1 but potentially clearer.
  
−
~MRENTHUSIASM (Revision)
+
Clearly this is just summing over the reciprocals of the numbers of the form <math>2^i3^j5^k</math>, where <math>i,j,k\in [0,\infty)</math>. So our desired sum is <math>\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}\sum_{i=0}^{\infty}\frac{1}{2^i3^j5^k}</math>. By the infinite geometric series formula, <math>\sum_{i=0}^{\infty}\frac{1}{2^i3^j5^k}</math> is just <math>\frac{\frac{1}{3^j5^k}}{1-\frac{1}{2}}=\frac{2}{3^j5^k}</math>. Applying the infinite geometric series formula again gives that <math>\sum_{j=0}^{\infty}\frac{2}{3^j5^k}=\frac{\frac{2}{5^k}}{1-\frac{1}{3}}=\frac{3}{5^k}</math>. Applying the infinite geometric series formula again yields <math>\sum_{k=0}^{\infty}\frac{3}{5^k}=\frac{3}{1-\frac{1}{5}}=\frac{15}{4}</math>. Hence our final answer is <math>15+4=\boxed{\textbf{(C) } 19}</math>.
  
−
== Solution 2 ==
+
~vsamc
−
Separate into 7 separate infinite series's so we can calculate each and find the original sum:  
+
 
 +
== Solution 3 ==
 +
Separate into <math>7</math> separate infinite series's so we can calculate each and find the original sum:  
  
−
The first infinite sequence shall be all the reciprocals of the powers of <math>2</math>, the second shall be reciprocals of the powers of <math>3</math>, and the third will consist of reciprocals of the powers of 5. We can easily calculate these to be <math>1, \frac{1}{2}, \frac{1}{4}</math> respectively.  
+
The first infinite sequence shall be all the reciprocals of the powers of <math>2</math>, the second shall be reciprocals of the powers of <math>3</math>, and the third will consist of reciprocals of the powers of <math>5</math>. We can easily calculate these to be <math>1, \frac{1}{2}, \frac{1}{4}</math> respectively.  
  
−
The fourth infinite series shall be all real numbers in the form <math> \frac{1}{2^a3^b}</math>, where <math>a</math> and <math>b</math> are greater than or equal to 1.  
+
The fourth infinite series shall be all real numbers in the form <math> \frac{1}{2^a3^b}</math>, where <math>a,b\geq1</math>.
  
−
The fifth is all real numbers in the form <math> \frac{1}{2^a5^b}</math>, where <math>a</math> and <math>b</math> are greater than or equal to 1.  
+
The fifth is all real numbers in the form <math> \frac{1}{2^a5^b}</math>, where <math>a,b\geq1</math>.  
  
−
The sixth is all real numbers in the form <math> \frac{1}{3^a5^b}</math>, where <math>a</math> and <math>b</math> are greater than or equal to 1.  
+
The sixth is all real numbers in the form <math> \frac{1}{3^a5^b}</math>, where <math>a,b\geq1</math>.  
  
−
The seventh infinite series is all real numbers in the form <math> \frac{1}{2^a3^b5^c}</math>, where <math>a</math> and <math>b</math> and <math>c</math> are greater than or equal to 1.  
+
The seventh infinite series is all real numbers in the form <math> \frac{1}{2^a3^b5^c}</math>, where <math>a,b,c\geq1</math>.  
  
 
Let us denote the first sequence as <math>a_{1}</math>, the second as <math>a_{2}</math>, etc. We know <math>a_{1}=1</math>, <math>a_{2}=\frac{1}{2}</math>, <math>a_{3}=\frac{1}{4}</math>, let us find <math>a_{4}</math>. factoring out <math>\frac{1}{6}</math> from the terms in this subsequence, we would get <math>a_{4}=\frac{1}{6}(1+a_{1}+a_{2}+a_{4})</math>.  
 
Let us denote the first sequence as <math>a_{1}</math>, the second as <math>a_{2}</math>, etc. We know <math>a_{1}=1</math>, <math>a_{2}=\frac{1}{2}</math>, <math>a_{3}=\frac{1}{4}</math>, let us find <math>a_{4}</math>. factoring out <math>\frac{1}{6}</math> from the terms in this subsequence, we would get <math>a_{4}=\frac{1}{6}(1+a_{1}+a_{2}+a_{4})</math>.  
Line 37: Line 43:
 
Knowing <math>a_{1}</math> and <math>a_{2}</math>, we can substitute and solve for <math>a_{4}</math>, and we get <math>\frac{1}{2}</math>. If we do similar procedures for the fifth and sixth sequences, we can solve for them too, and we get after solving them <math>\frac{1}{4}</math> and <math>\frac{1}{8}</math>.  
 
Knowing <math>a_{1}</math> and <math>a_{2}</math>, we can substitute and solve for <math>a_{4}</math>, and we get <math>\frac{1}{2}</math>. If we do similar procedures for the fifth and sixth sequences, we can solve for them too, and we get after solving them <math>\frac{1}{4}</math> and <math>\frac{1}{8}</math>.  
  
−
Finally, for the seventh sequence, we see <math>a_{7}=\frac{a_{8}}{30}</math>, where <math>a_{8}</math>  is the infinite series the problem is asking us to solve for. The sum of all seven subsequences will equal the one we are looking for, so solving, we get <math>1+\frac{1}{2}+\frac{1}{4}+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{a_{8}}{30}=a_{8}</math>, but when we separated the sequence into its parts, we ignored the <math>1/1</math>, so adding in the <math>1</math>, we get <math>1+1+\frac{1}{2}+\frac{1}{4}+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{a_{8}}{30}=a_{8}</math>, which when we solve for, we get <math>\frac{29}{8}=\frac{29a_{8}}{30}</math>, <math>\frac{1}{8}=\frac{a_{8}}{30}</math>, <math>\frac{30}{8}=(a_{8})</math>, <math>\frac{15}{4}=(a_{8})</math>. So our answer is <math>\frac{15}{4}</math>, but we are asked to add the numerator and denominator, which sums up to <math>19</math>, which is the answer.
+
Finally, for the seventh sequence, we see <math>a_{7}=\frac{a_{8}}{30}</math>, where <math>a_{8}</math>  is the infinite series the problem is asking us to solve for. The sum of all seven subsequences will equal the one we are looking for, and we need to add the <math>\frac11</math> term back: <math>1+1+\frac{1}{2}+\frac{1}{4}+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{a_{8}}{30}=a_{8}</math>. We solve this to get <math>\frac{29}{8}=\frac{29a_{8}}{30}</math>, or <math>\frac{15}{4}=a_{8}</math>. So our answer is <math>\frac{15}{4}</math>, but we are asked to add the numerator and denominator, which sums up to <math>\boxed{\textbf{(C) } 19}</math>.
  
 
~~Edited by mprincess0229~~
 
~~Edited by mprincess0229~~
  
−
== Solution 3 ==
+
==Solution 4(clear but takes time)==
−
Clearly this is just summing over the reciprocals of the numbers of the form <math>2^i3^j5^k</math>, where <math>i,j,k\in [0,\infty)</math>. SO our desired sum is <math>\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}\sum_{i=0}^{\infty}\frac{1}{2^i3^j5^k}</math>. By the infinite geometric series formula, <math>\sum_{i=0}^{\infty}\frac{1}{2^i3^j5^k}</math> is just <math>\frac{\frac{1}{3^j5^k}}{1-\frac{1}{2}}=\frac{2}{3^j5^k}</math>. Applying the infinite geometric series formula again gives that <math>\sum_{j=0}^{\infty}\frac{2}{3^j5^k}=\frac{\frac{2}{5^k}}{1-\frac{1}{3}}=\frac{3}{5^k}</math>. Applying the infinite geometric series formula again yields <math>\sum_{k=0}^{\infty}\frac{3}{5^k}=\frac{3}{1-\frac{1}{5}}=\frac{15}{4}</math>. Hence our final answer is <math>15+4=\boxed{19}</math>.
+
 
 +
First of all, we need to find some geometric sequences hidden in here.
 +
 
 +
The first sequence is just <math>\frac{1}{1}</math>. We can just leave this 1 by itself.
 +
 
 +
The second sequence contains all numbers in the form of <math>\frac{1}{2^p}</math>. This is just 1/2+1/4+...=1.
 +
 
 +
The third sequence contains all numbers in the form of <math>\frac{1}{2^p\cdot 3}</math>. These add to <math>\frac{\frac13}{\frac12}</math>.
 +
 
 +
The fourth sequence contains all numbers in the form of <math>\frac{1}{2^p\cdot 5}</math>. These add to <math>\frac{\frac15}{\frac12}</math>.
 +
 
 +
Essentially, every number is contained in a sequence that starts with the term that is the reciprocal of the result when the number is repeatedly divided by 2 until the number is odd.
 +
 
 +
These will add up to <math>1+1+\frac{\frac{1}{3}+\frac{1}{5}+\frac{1}{9}+\frac{1}{15}+\frac{1}{25}+\frac{1}{27}+\cdots}{\frac{1}{2}}</math>. Note that the numerator of that fraction is the sum of the reciprocals of every number with only 3 or 5 in its prime factorization. Let's call that numerator <math>x</math>.
 +
 
 +
So now, we find <math>x</math>. That strategy worked out pretty well. Let's use it again.
 +
 
 +
The first sequence contains all numbers in the form of <math>\frac{1}{3^p}</math>. These add to <math>\frac{\frac13}{\frac23}</math>. The second sequence contains all numbers in the form of <math>\frac{1}{3^p\cdot5}</math>. These add to <math>\frac{\frac15}{\frac23}</math>. The third sequence contains all numbers in the form of <math>\frac{1}{3^p\cdot 5^2}</math>. These add to <math>\frac{\frac{1}{25}}{\frac{2}{3}}</math>
 +
 
 +
Essentially, every number is contained in a sequence that starts with the term that is the reciprocal of the result when the number is repeatedly divided by 3 until the number is not divisible by 3.
 +
 
 +
The total sum for <math>x</math> is <math>\frac{1}{2}+\frac{\text{a geometric sequence}}{\frac{2}{3}}</math>, and that geometric sequence evaluates to <math>\frac{\frac{1}{5}}{1-\frac{1}{5}}=\frac{1}{4}</math>. Then we just need to do the computation.
 +
 
 +
<math>x</math> is <math>\frac{\frac14}{\frac23}+\frac12=\frac78</math>. Recalling our answer is <math>\frac{x}{\frac12}+2</math>, we can plug in <math>x</math> to get a final answer of <math>\frac{7}{4}+2=\frac{15}{4}</math>.  
 +
 
 +
Finally, we can add <math>15+4=\boxed{\textbf{(C) } 19}</math>.
 +
 
 +
~yrock
 +
 
 +
What's up with the LaTeX rendering? Someone help...
  
−
-vsamc
+
I fixed it, dw it just an extra dollar sign
  
 
== Video Solution by LetsSolveMathProblems ==
 
== Video Solution by LetsSolveMathProblems ==

Latest revision as of 19:27, 3 July 2024

Problem

Let $A$ be the set of positive integers that have no prime factors other than $2$, $3$, or $5$. The infinite sum \[\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} + \frac{1}{12} + \frac{1}{15} + \frac{1}{16} + \frac{1}{18} + \frac{1}{20} + \cdots\]of the reciprocals of the elements of $A$ can be expressed as $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. What is $m+n$?

$\textbf{(A) } 16 \qquad \textbf{(B) } 17 \qquad \textbf{(C) } 19 \qquad \textbf{(D) } 23 \qquad \textbf{(E) } 36$

Solution 1

Note that the fractions of the form $\frac{1}{2^a3^b5^c},$ where $a,b,$ and $c$ are nonnegative integers, span all terms of the infinite sum.

Therefore, the infinite sum becomes \begin{align*} \sum_{a=0}^{\infty}\sum_{b=0}^{\infty}\sum_{c=0}^{\infty}\frac{1}{2^a3^b5^c} &= \left(\sum_{a=0}^{\infty}\frac{1}{2^a}\right)\cdot\left(\sum_{b=0}^{\infty}\frac{1}{3^b}\right)\cdot\left(\sum_{c=0}^{\infty}\frac{1}{5^c}\right) \\ &= \frac{1}{1-\frac12}\cdot\frac{1}{1-\frac13}\cdot\frac{1}{1-\frac15} \\ &= 2\cdot\frac32\cdot\frac54 \\ &= \frac{15}{4} \end{align*} by a product of geometric series, from which the answer is $15+4=\boxed{\textbf{(C) } 19}.$

~athens2016 ~MRENTHUSIASM

Solution 2

This solution is the same as Solution 1 but potentially clearer.

Clearly this is just summing over the reciprocals of the numbers of the form $2^i3^j5^k$, where $i,j,k\in [0,\infty)$. So our desired sum is $\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}\sum_{i=0}^{\infty}\frac{1}{2^i3^j5^k}$. By the infinite geometric series formula, $\sum_{i=0}^{\infty}\frac{1}{2^i3^j5^k}$ is just $\frac{\frac{1}{3^j5^k}}{1-\frac{1}{2}}=\frac{2}{3^j5^k}$. Applying the infinite geometric series formula again gives that $\sum_{j=0}^{\infty}\frac{2}{3^j5^k}=\frac{\frac{2}{5^k}}{1-\frac{1}{3}}=\frac{3}{5^k}$. Applying the infinite geometric series formula again yields $\sum_{k=0}^{\infty}\frac{3}{5^k}=\frac{3}{1-\frac{1}{5}}=\frac{15}{4}$. Hence our final answer is $15+4=\boxed{\textbf{(C) } 19}$.

~vsamc

Solution 3

Separate into $7$ separate infinite series's so we can calculate each and find the original sum:

The first infinite sequence shall be all the reciprocals of the powers of $2$, the second shall be reciprocals of the powers of $3$, and the third will consist of reciprocals of the powers of $5$. We can easily calculate these to be $1, \frac{1}{2}, \frac{1}{4}$ respectively.

The fourth infinite series shall be all real numbers in the form $\frac{1}{2^a3^b}$, where $a,b\geq1$.

The fifth is all real numbers in the form $\frac{1}{2^a5^b}$, where $a,b\geq1$.

The sixth is all real numbers in the form $\frac{1}{3^a5^b}$, where $a,b\geq1$.

The seventh infinite series is all real numbers in the form $\frac{1}{2^a3^b5^c}$, where $a,b,c\geq1$.

Let us denote the first sequence as $a_{1}$, the second as $a_{2}$, etc. We know $a_{1}=1$, $a_{2}=\frac{1}{2}$, $a_{3}=\frac{1}{4}$, let us find $a_{4}$. factoring out $\frac{1}{6}$ from the terms in this subsequence, we would get $a_{4}=\frac{1}{6}(1+a_{1}+a_{2}+a_{4})$.

Knowing $a_{1}$ and $a_{2}$, we can substitute and solve for $a_{4}$, and we get $\frac{1}{2}$. If we do similar procedures for the fifth and sixth sequences, we can solve for them too, and we get after solving them $\frac{1}{4}$ and $\frac{1}{8}$.

Finally, for the seventh sequence, we see $a_{7}=\frac{a_{8}}{30}$, where $a_{8}$ is the infinite series the problem is asking us to solve for. The sum of all seven subsequences will equal the one we are looking for, and we need to add the $\frac11$ term back: $1+1+\frac{1}{2}+\frac{1}{4}+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{a_{8}}{30}=a_{8}$. We solve this to get $\frac{29}{8}=\frac{29a_{8}}{30}$, or $\frac{15}{4}=a_{8}$. So our answer is $\frac{15}{4}$, but we are asked to add the numerator and denominator, which sums up to $\boxed{\textbf{(C) } 19}$.

~~Edited by mprincess0229~~

Solution 4(clear but takes time)

First of all, we need to find some geometric sequences hidden in here.

The first sequence is just $\frac{1}{1}$. We can just leave this 1 by itself.

The second sequence contains all numbers in the form of $\frac{1}{2^p}$. This is just 1/2+1/4+...=1.

The third sequence contains all numbers in the form of $\frac{1}{2^p\cdot 3}$. These add to $\frac{\frac13}{\frac12}$.

The fourth sequence contains all numbers in the form of $\frac{1}{2^p\cdot 5}$. These add to $\frac{\frac15}{\frac12}$.

Essentially, every number is contained in a sequence that starts with the term that is the reciprocal of the result when the number is repeatedly divided by 2 until the number is odd.

These will add up to $1+1+\frac{\frac{1}{3}+\frac{1}{5}+\frac{1}{9}+\frac{1}{15}+\frac{1}{25}+\frac{1}{27}+\cdots}{\frac{1}{2}}$. Note that the numerator of that fraction is the sum of the reciprocals of every number with only 3 or 5 in its prime factorization. Let's call that numerator $x$.

So now, we find $x$. That strategy worked out pretty well. Let's use it again.

The first sequence contains all numbers in the form of $\frac{1}{3^p}$. These add to $\frac{\frac13}{\frac23}$. The second sequence contains all numbers in the form of $\frac{1}{3^p\cdot5}$. These add to $\frac{\frac15}{\frac23}$. The third sequence contains all numbers in the form of $\frac{1}{3^p\cdot 5^2}$. These add to $\frac{\frac{1}{25}}{\frac{2}{3}}$

Essentially, every number is contained in a sequence that starts with the term that is the reciprocal of the result when the number is repeatedly divided by 3 until the number is not divisible by 3.

The total sum for $x$ is $\frac{1}{2}+\frac{\text{a geometric sequence}}{\frac{2}{3}}$, and that geometric sequence evaluates to $\frac{\frac{1}{5}}{1-\frac{1}{5}}=\frac{1}{4}$. Then we just need to do the computation.

$x$ is $\frac{\frac14}{\frac23}+\frac12=\frac78$. Recalling our answer is $\frac{x}{\frac12}+2$, we can plug in $x$ to get a final answer of $\frac{7}{4}+2=\frac{15}{4}$.

Finally, we can add $15+4=\boxed{\textbf{(C) } 19}$.

~yrock

What's up with the LaTeX rendering? Someone help...

I fixed it, dw it just an extra dollar sign

Video Solution by LetsSolveMathProblems

https://www.youtube.com/watch?v=woXlEargLpI&ab_channel=LetsSolveMathProblems

See Also

2018 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 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=2018_AMC_12A_Problems/Problem_19&oldid=221626"