Difference between revisions of "2021 Fall AMC 12B Problems/Problem 12"
MRENTHUSIASM (talk | contribs) m |
m (→Solution 6) |
||
(21 intermediate revisions by 7 users not shown) | |||
Line 8: | Line 8: | ||
==Solution 1== | ==Solution 1== | ||
− | The prime | + | The prime factorizations of <math>768</math> and <math>384</math> are <math>2^8\cdot3</math> and <math>2^7\cdot3,</math> respectively. Note that <math>f(n)</math> is the sum of all fractions of the form <math>\frac 1d,</math> where <math>d</math> is a positive divisor of <math>n.</math> By geometric series, it follows that |
<cmath>\begin{alignat*}{8} | <cmath>\begin{alignat*}{8} | ||
f(768)&=\left(\sum_{k=0}^{8}\frac{1}{2^k}\right)+\left(\sum_{k=0}^{8}\frac{1}{2^k\cdot3}\right)&&=\frac{511}{256}+\frac{511}{768}&&=\frac{2044}{768}, \\ | f(768)&=\left(\sum_{k=0}^{8}\frac{1}{2^k}\right)+\left(\sum_{k=0}^{8}\frac{1}{2^k\cdot3}\right)&&=\frac{511}{256}+\frac{511}{768}&&=\frac{2044}{768}, \\ | ||
Line 19: | Line 19: | ||
==Solution 2== | ==Solution 2== | ||
− | The prime factorization of <math>384</math> is <math>2^7\cdot3,</math> so each of its positive divisors is of the form <math>2^m</math> or <math>2^m\cdot3</math> for some integer <math>m</math> such that <math>0\leq m\leq7.</math> We will use this fact to calculate the sum of all its positive divisors. Note that <cmath>2^m + 2^m\cdot3 = 2^m\cdot(1+3) = 2^m\cdot4 = 2^m\cdot2^2 = 2^{m+2}</cmath> is the sum of the two forms of positive divisors for all such <math>m.</math> By geometric series, the sum of all positive divisors of <math>384</math> is <cmath>2^ | + | The prime factorization of <math>384</math> is <math>2^7\cdot3,</math> so each of its positive divisors is of the form <math>2^m</math> or <math>2^m\cdot3</math> for some integer <math>m</math> such that <math>0\leq m\leq7.</math> We will use this fact to calculate the sum of all its positive divisors. Note that <cmath>2^m + 2^m\cdot3 = 2^m\cdot(1+3) = 2^m\cdot4 = 2^m\cdot2^2 = 2^{m+2}</cmath> is the sum of the two forms of positive divisors for all such <math>m.</math> By geometric series, the sum of all positive divisors of <math>384</math> is <cmath>\sum_{k=2}^{9}2^k = \frac{2^{10}-2^2}{2-1} = 1020,</cmath> from which <math>f(384) = \frac{1020}{384}.</math> Similarly, since the prime factorization of <math>768</math> is <math>2^8 \cdot 3,</math> we have <math>f(768) = \frac{2044}{768}.</math> |
Therefore, the answer is <math>f(768)-f(384)=\boxed{\textbf{(B)}\ \frac{1}{192}}.</math> | Therefore, the answer is <math>f(768)-f(384)=\boxed{\textbf{(B)}\ \frac{1}{192}}.</math> | ||
Line 31: | Line 31: | ||
Suppose that <math>n=\prod_{i=1}^{k}p_i^{e_i}</math> is the prime factorization of <math>n.</math> Since <math>\sigma(n)</math> is multiplicative, we have <cmath>\sigma(n)=\sigma\left(\prod_{i=1}^{k}p_i^{e_i}\right)=\prod_{i=1}^{k}\sigma\left(p_i^{e_i}\right)=\prod_{i=1}^{k}\left(\sum_{j=0}^{e_i}p_i^j\right)=\prod_{i=1}^{k}\frac{p_i^{e_i+1}-1}{p_i-1}</cmath> by geometric series. | Suppose that <math>n=\prod_{i=1}^{k}p_i^{e_i}</math> is the prime factorization of <math>n.</math> Since <math>\sigma(n)</math> is multiplicative, we have <cmath>\sigma(n)=\sigma\left(\prod_{i=1}^{k}p_i^{e_i}\right)=\prod_{i=1}^{k}\sigma\left(p_i^{e_i}\right)=\prod_{i=1}^{k}\left(\sum_{j=0}^{e_i}p_i^j\right)=\prod_{i=1}^{k}\frac{p_i^{e_i+1}-1}{p_i-1}</cmath> by geometric series. | ||
− | The prime | + | The prime factorizations of <math>768</math> and <math>384</math> are <math>2^8\cdot3</math> and <math>2^7\cdot3,</math> respectively. Note that |
<cmath>\begin{alignat*}{8} | <cmath>\begin{alignat*}{8} | ||
f(768) &= \left(\frac{2^9-1}{2-1}\cdot\frac{3^2-1}{3-1}\right)\div768 &&= \frac{2044}{768}, \\ | f(768) &= \left(\frac{2^9-1}{2-1}\cdot\frac{3^2-1}{3-1}\right)\div768 &&= \frac{2044}{768}, \\ | ||
Line 39: | Line 39: | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
+ | |||
+ | ==Solution 4== | ||
+ | Note that | ||
+ | <cmath>\begin{align*} | ||
+ | 384 &= 2^7\cdot3, \\ | ||
+ | 768 &= 2^8\cdot3. | ||
+ | \end{align*}</cmath> | ||
+ | Both numbers take the form <math>2^n\cdot3</math>. Define a function <math>S(n)</math> as being the sum of the factors for any number <math>2^n\cdot3</math>, where <math>n</math> is a nonnegative integer. | ||
+ | |||
+ | If you list out the factors of a number <math>2^n\cdot3</math>, all the factors are even except for <math>1</math> and <math>3</math>. So to produce a list of factors for the number <math>2^{n+1}\cdot3</math>, you can multiply all the factors on the first list by <math>2</math> and then add on <math>1</math> and <math>3</math>. Thus, <math>S(n) = 2S(n-1) + 4</math>. | ||
+ | |||
+ | We need to find <math>\frac{S(8)}{768} - \frac{S(7)}{384}</math>. This can be written as <math>\frac{2S(7)+4-2S(7)}{768}</math>. Our recursive formula states that <math>S(n) = 2S(n-1) + 4</math> so <math>S(n) - 2S(n-1) = 4</math>. Thus, the fraction simplifies to <math>\frac{4}{768} = \boxed{\textbf{(B)}\ \frac{1}{192}}</math>. Note that we never needed to figure out what <math>S(8)</math> or <math>S(7)</math> were, sparing us a lot of calculation. | ||
+ | |||
+ | ~Curious_crow | ||
+ | |||
+ | ==Solution 5== | ||
+ | We know that | ||
+ | <cmath>\begin{align*} | ||
+ | f(768) &= \frac{1 + 2 + 3 + 4 + \cdots + 768}{768}, \\ | ||
+ | f(384) &= \frac{1 + 2 + 3 + 4 + \cdots + 384}{384}. | ||
+ | \end{align*}</cmath> | ||
+ | We want to find the difference of these so | ||
+ | <cmath>\frac{1 + 2 + 3 + 4 + \cdots + 768}{768} - \frac{ 2(1 + 2 + 3 + 4 + \cdots + 384)}{2\cdot384} = \frac{1 + 2 + 3 + 4 + \cdots + 768}{768} - \frac{ 2 + 4 + 6 + 8 + \cdots + 768}{768}.</cmath> | ||
+ | We are only left with the even divisors of <math>768</math> on the fraction on the right so the answer would be the sum of all odd divisors of <math>768</math> (<math>1</math> and <math>3</math>) over <math>768</math>: | ||
+ | <cmath>\frac{1 + 3}{768}=\boxed{\textbf{(B)}\ \frac{1}{192}}.</cmath> | ||
+ | ~pengf | ||
+ | |||
+ | ==Solution 6== | ||
+ | As in Solution 1, the prime factorization of <math>768</math> is <math>2^8 \cdot 3</math>, and the prime factorization of <math>384</math> is <math>2^7 \cdot 3</math>. Recalling the sum of factors formula and sum of the powers of 2 formula, we find that the sum of the factors of <math>768</math> is <math>(1+2^1+2^2+2^3+2^4+2^5+2^6+2^7+2^8)(1+3^1)=(2^9-1)(4)=(511)(4)</math>, and the sum of factors of <math>384</math> is <math>1+2^1+2^2+2^3+2^4+2^5+2^6+2^7)(1+3^1)=(2^8-1)(4)=(255)(4)</math>. Then <math>f(768)=\frac{(511)(4)}{768}=\frac{511}{192}</math>, and <math>f(384)=\frac{(255)(4)}{384}=\frac{510}{192}</math>. So, <math>f(768)-f(384)=\frac{511}{192}-\frac{510}{192}=\boxed{\textbf{(B)}\ \frac{1}{192}}</math>. | ||
+ | |||
+ | ~ [https://artofproblemsolving.com/wiki/index.php/User:Cxsmi cxsmi] | ||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://youtu.be/jgyyGeEKhwk?t=1116 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
+ | |||
+ | ==Video Solution by TheBeautyofMath== | ||
+ | https://youtu.be/FFlj8W_xkPc | ||
+ | |||
+ | ~IceMatrix | ||
==See Also== | ==See Also== | ||
{{AMC12 box|year=2021 Fall|ab=B|num-a=13|num-b=11}} | {{AMC12 box|year=2021 Fall|ab=B|num-a=13|num-b=11}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 12:48, 4 April 2024
Contents
Problem
For a positive integer, let be the quotient obtained when the sum of all positive divisors of is divided by For example, What is
Solution 1
The prime factorizations of and are and respectively. Note that is the sum of all fractions of the form where is a positive divisor of By geometric series, it follows that Therefore, the answer is
~lopkiloinm ~MRENTHUSIASM
Solution 2
The prime factorization of is so each of its positive divisors is of the form or for some integer such that We will use this fact to calculate the sum of all its positive divisors. Note that is the sum of the two forms of positive divisors for all such By geometric series, the sum of all positive divisors of is from which Similarly, since the prime factorization of is we have
Therefore, the answer is
~mahaler
Solution 3
Let denotes the sum of all positive divisors of so
Suppose that is the prime factorization of Since is multiplicative, we have by geometric series.
The prime factorizations of and are and respectively. Note that Therefore, the answer is
~MRENTHUSIASM
Solution 4
Note that Both numbers take the form . Define a function as being the sum of the factors for any number , where is a nonnegative integer.
If you list out the factors of a number , all the factors are even except for and . So to produce a list of factors for the number , you can multiply all the factors on the first list by and then add on and . Thus, .
We need to find . This can be written as . Our recursive formula states that so . Thus, the fraction simplifies to . Note that we never needed to figure out what or were, sparing us a lot of calculation.
~Curious_crow
Solution 5
We know that We want to find the difference of these so We are only left with the even divisors of on the fraction on the right so the answer would be the sum of all odd divisors of ( and ) over : ~pengf
Solution 6
As in Solution 1, the prime factorization of is , and the prime factorization of is . Recalling the sum of factors formula and sum of the powers of 2 formula, we find that the sum of the factors of is , and the sum of factors of is . Then , and . So, .
~ cxsmi
Video Solution by OmegaLearn
https://youtu.be/jgyyGeEKhwk?t=1116
~ pi_is_3.14
Video Solution by TheBeautyofMath
~IceMatrix
See Also
2021 Fall AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 11 |
Followed by Problem 13 |
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.