Difference between revisions of "2022 AMC 12A Problems/Problem 23"
(→Solution 2) |
MRENTHUSIASM (talk | contribs) (→Solution 2) |
||
(4 intermediate revisions by 2 users not shown) | |||
Line 5: | Line 5: | ||
<math>\textbf{(A) }0 \qquad\textbf{(B) }3 \qquad\textbf{(C) }7 \qquad\textbf{(D) }8\qquad\textbf{(E) }10</math> | <math>\textbf{(A) }0 \qquad\textbf{(B) }3 \qquad\textbf{(C) }7 \qquad\textbf{(D) }8\qquad\textbf{(E) }10</math> | ||
− | ==Solution== | + | ==Solution 1== |
We are given that <cmath>\sum_{i=1}^{n}\frac1i = \frac{1}{L_n}\sum_{i=1}^{n}\frac{L_n}{i} = \frac{h_n}{k_n}.</cmath> Since <math>k_n < L_n,</math> we need <math>\gcd\left(\sum_{i=1}^{n}\frac{L_n}{i}, L_n\right)>1.</math> | We are given that <cmath>\sum_{i=1}^{n}\frac1i = \frac{1}{L_n}\sum_{i=1}^{n}\frac{L_n}{i} = \frac{h_n}{k_n}.</cmath> Since <math>k_n < L_n,</math> we need <math>\gcd\left(\sum_{i=1}^{n}\frac{L_n}{i}, L_n\right)>1.</math> | ||
Line 59: | Line 59: | ||
Together, there are <math>\boxed{\textbf{(D) }8}</math> such integers <math>n,</math> namely <cmath>6,7,8,18,19,20,21,22.</cmath> | Together, there are <math>\boxed{\textbf{(D) }8}</math> such integers <math>n,</math> namely <cmath>6,7,8,18,19,20,21,22.</cmath> | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
+ | |||
==Solution 2== | ==Solution 2== | ||
Notice that <math>\sum_{i=1}^{n}\frac{1}{i} = \frac{\sum_{i=1}^{n}\frac{L_n}{i}}{L_n}</math>. Thus, in order for <math>L_n</math> to reduce to a smaller value, the numerator and denominator must share a common factor. | Notice that <math>\sum_{i=1}^{n}\frac{1}{i} = \frac{\sum_{i=1}^{n}\frac{L_n}{i}}{L_n}</math>. Thus, in order for <math>L_n</math> to reduce to a smaller value, the numerator and denominator must share a common factor. | ||
− | |||
We can start by testing some values of <math>n</math>, and quickly observe that <math>n=6</math> is the first number that satisfies the desired conditions. In particular, <math>\sum_{i=1}^{6}\frac{1}{i} = \frac{\sum_{i=1}^{6}\frac{L_6}{i}}{L_6} = \frac{147}{60} = \frac{49}{20}</math>. Since a factor of three is shared, we are motivated to observe factors of three in the numerator <math>\sum_{i=1}^{6}\frac{60}{i}</math>. Notice that <math>v_3(L_6) = 1</math>, since <math>3^1</math> is the greatest power of three that occurs in <math>1,2,3,4,5,6</math>. Consider the sum in the numerator in mod 3. We have <math>(\frac{60}{1}, \frac{60}{2}, \frac{60}{3}, \frac{60}{4}, \frac{60}{5}, \frac{60}{6} )\rightarrow (0,0,2,0,0,1)</math>. Adding 0+0+2+0+0+1 we get 0 mod 3, which is why we are able to simplify <math>\frac{147}{60}</math>. | We can start by testing some values of <math>n</math>, and quickly observe that <math>n=6</math> is the first number that satisfies the desired conditions. In particular, <math>\sum_{i=1}^{6}\frac{1}{i} = \frac{\sum_{i=1}^{6}\frac{L_6}{i}}{L_6} = \frac{147}{60} = \frac{49}{20}</math>. Since a factor of three is shared, we are motivated to observe factors of three in the numerator <math>\sum_{i=1}^{6}\frac{60}{i}</math>. Notice that <math>v_3(L_6) = 1</math>, since <math>3^1</math> is the greatest power of three that occurs in <math>1,2,3,4,5,6</math>. Consider the sum in the numerator in mod 3. We have <math>(\frac{60}{1}, \frac{60}{2}, \frac{60}{3}, \frac{60}{4}, \frac{60}{5}, \frac{60}{6} )\rightarrow (0,0,2,0,0,1)</math>. Adding 0+0+2+0+0+1 we get 0 mod 3, which is why we are able to simplify <math>\frac{147}{60}</math>. | ||
− | |||
Thus, we should be taking the numerator mod p, where p is a prime. | Thus, we should be taking the numerator mod p, where p is a prime. | ||
− | |||
Quickly, we wish to show that the numerator and denominator can never share a factor of 2. Say we have least common multiple <math>L_n</math>. Let <math>v_2(L_n) = e</math>. In other words, let <math>2^e</math> be the largest power of 2 such that <math>2^e</math> divides <math>L_n</math>. Notice that among all numbers <math>1</math> through <math>n</math>, only one of them can be a multiple of <math>2^e</math>, being <math>2^e</math> itself. The next multiple of <math>2^e</math> would be <math>2 \cdot 2^e = 2^{e+1}</math>, contradicting the fact that <math>v_2(L_n) = e</math>. This means that in the sum <math>\sum_{i=1}^{n}\frac{L_n}{i}</math>, there will be <math>1</math> value that is <math>1</math> mod <math>2</math>, resulting from <math>\frac{L_n}{2^e}</math>, and the rest are all <math>0</math>s. Clearly, the numerator will then be <math>1</math> mod <math>2</math>, which is not a multiple of 2. | Quickly, we wish to show that the numerator and denominator can never share a factor of 2. Say we have least common multiple <math>L_n</math>. Let <math>v_2(L_n) = e</math>. In other words, let <math>2^e</math> be the largest power of 2 such that <math>2^e</math> divides <math>L_n</math>. Notice that among all numbers <math>1</math> through <math>n</math>, only one of them can be a multiple of <math>2^e</math>, being <math>2^e</math> itself. The next multiple of <math>2^e</math> would be <math>2 \cdot 2^e = 2^{e+1}</math>, contradicting the fact that <math>v_2(L_n) = e</math>. This means that in the sum <math>\sum_{i=1}^{n}\frac{L_n}{i}</math>, there will be <math>1</math> value that is <math>1</math> mod <math>2</math>, resulting from <math>\frac{L_n}{2^e}</math>, and the rest are all <math>0</math>s. Clearly, the numerator will then be <math>1</math> mod <math>2</math>, which is not a multiple of 2. | ||
+ | When p=3, <math>n=6,7,8,18,19,20,21,22</math> will all work, and this can be easily tested through taking the numerator mod 3. p=5 is only satisfied when the <math>L_n</math> contains <math>(5,10,15,20)</math>, so when <math>n\ge 20</math>. However, this is just an overlap with the previous values, so there are <math>\boxed{\textbf{B) }8}</math>. | ||
− | + | ~skibbysiggy | |
== Video Solution == | == Video Solution == |
Latest revision as of 21:10, 4 November 2024
Contents
[hide]Problem
Let and be the unique relatively prime positive integers such that Let denote the least common multiple of the numbers . For how many integers with is ?
Solution 1
We are given that Since we need
For all primes such that let be the largest power of that is a factor of
It is clear that so we test whether Note that We construct the following table for Note that:
- If the Sum column has only one term, then it is never congruent to modulo
- If and are positive integers such that then is a multiple of Therefore, for a specific case, if the sum is congruent to modulo for the smallest element in the interval of then it is also congruent to modulo for all other elements in the interval of
Together, there are such integers namely ~MRENTHUSIASM
Solution 2
Notice that . Thus, in order for to reduce to a smaller value, the numerator and denominator must share a common factor.
We can start by testing some values of , and quickly observe that is the first number that satisfies the desired conditions. In particular, . Since a factor of three is shared, we are motivated to observe factors of three in the numerator . Notice that , since is the greatest power of three that occurs in . Consider the sum in the numerator in mod 3. We have . Adding 0+0+2+0+0+1 we get 0 mod 3, which is why we are able to simplify .
Thus, we should be taking the numerator mod p, where p is a prime.
Quickly, we wish to show that the numerator and denominator can never share a factor of 2. Say we have least common multiple . Let . In other words, let be the largest power of 2 such that divides . Notice that among all numbers through , only one of them can be a multiple of , being itself. The next multiple of would be , contradicting the fact that . This means that in the sum , there will be value that is mod , resulting from , and the rest are all s. Clearly, the numerator will then be mod , which is not a multiple of 2.
When p=3, will all work, and this can be easily tested through taking the numerator mod 3. p=5 is only satisfied when the contains , so when . However, this is just an overlap with the previous values, so there are .
~skibbysiggy
Video Solution
We will use the following lemma to solve this problem.
Denote by the prime factorization of . For any , denote , where and are relatively prime. Then if and only if for any , is not a multiple of .
Now, we use the result above to solve this problem.
Following from this lemma, the list of with and is
Therefore, the answer is .
Note: Detailed analysis of this problem (particularly the motivation and the proof of the lemma above) can be found in my video solution below.
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~MathProblemSolvingSkills.com
Video Solution by Math-X
https://youtu.be/7yAh4MtJ8a8?si=oklkf-_wUpjjfAed&t=8018
~Math-X
See Also
2022 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 22 |
Followed by Problem 24 |
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.