Difference between revisions of "2022 AMC 12A Problems/Problem 23"
Sugar rush (talk | contribs) |
(→Video Solution by Math-X) |
||
(28 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Let <math>h_n</math> and <math>k_n</math> be the unique relatively prime positive integers such that | + | Let <math>h_n</math> and <math>k_n</math> be the unique relatively prime positive integers such that <cmath>\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\frac{h_n}{k_n}.</cmath> Let <math>L_n</math> denote the least common multiple of the numbers <math>1, 2, 3, \ldots, n</math>. For how many integers with <math>1\le{n}\le{22}</math> is <math>k_n<L_n</math>? |
− | <cmath> | + | <math>\textbf{(A) }0 \qquad\textbf{(B) }3 \qquad\textbf{(C) }7 \qquad\textbf{(D) }8\qquad\textbf{(E) }10</math> |
− | \ | + | |
− | </cmath> | + | ==Solution== |
+ | |||
+ | 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> | ||
− | + | For all primes <math>p</math> such that <math>p\leq n,</math> let <math>v_p(L_n)=e\geq1</math> be the largest power of <math>p</math> that is a factor of <math>L_n.</math> | |
− | == | + | It is clear that <math>L_n\equiv0\pmod{p},</math> so we test whether <math>\sum_{i=1}^{n}\frac{L_n}{i}\equiv0\pmod{p}.</math> Note that <cmath>\sum_{i=1}^{n}\frac{L_n}{i} \equiv \sum_{i=1}^{\left\lfloor\tfrac{n}{p^e}\right\rfloor}\frac{L_n}{ip^e} \ (\operatorname{mod} \ p^e) \equiv \sum_{i=1}^{\left\lfloor\tfrac{n}{p^e}\right\rfloor}\frac{L_n}{ip^e} \ (\operatorname{mod} \ p).</cmath> |
+ | We construct the following table for <math>v_p(L_n)=e:</math> | ||
+ | <cmath>\begin{array}{c|c|l|c} | ||
+ | \textbf{Case of }\boldsymbol{(p,e)} & \textbf{Interval of }\boldsymbol{n} & \hspace{22.75mm}\textbf{Sum} & \boldsymbol{\stackrel{?}{\equiv}0\ (\operatorname{mod} \ p)} \\ [0.5ex] | ||
+ | \hline\hline | ||
+ | & & & \\ [-2ex] | ||
+ | (2,1) & [2,3] & L_n/2 & \\ | ||
+ | (2,2) & [4,7] & L_n/4 & \\ | ||
+ | (2,3) & [8,15] & L_n/8 & \\ | ||
+ | (2,4) & [16,22] & L_n/16 & \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | (3,1) & [3,5] & L_n/3 & \\ | ||
+ | & [6,8] & L_n/3 + L_n/6 & \checkmark \\ | ||
+ | (3,2) & [9,17] & L_n/9 & \\ | ||
+ | & [18,22] & L_n/9 + L_n/18 & \checkmark \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | (5,1) & [5,9] & L_n/5 & \\ | ||
+ | & [10,14] & L_n/5 + L_n/10 & \\ | ||
+ | & [15,19] & L_n/5 + L_n/10 + L_n/15 & \\ | ||
+ | & [20,22] & L_n/5 + L_n/10 + L_n/15 + L_n/20 & \checkmark \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | (7,1) & [7,13] & L_n/7 & \\ | ||
+ | & [14,20] & L_n/7 + L_n/14 & \\ | ||
+ | & [21,22] & L_n/7 + L_n/14 + L_n/21 & \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | (11,1) & [11,21] & L_n/11 & \\ | ||
+ | & \{22\} & L_n/11 + L_n/22 & \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | (13,1) & [13,22] & L_n/13 & \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | (17,1) & [17,22] & L_n/17 & \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | (19,1) & [19,22] & L_n/19 & \\ [0.5ex] | ||
+ | \end{array}</cmath> | ||
+ | Note that: | ||
+ | <ol style="margin-left: 1.5em;"> | ||
+ | <li>If the <b>Sum</b> column has only one term, then it is never congruent to <math>0</math> modulo <math>p.</math></li><p> | ||
+ | <li>If <math>p</math> and <math>q</math> are positive integers such that <math>p\geq q,</math> then <math>L_p</math> is a multiple of <math>L_q.</math> Therefore, for a specific case, if the sum is congruent to <math>0</math> modulo <math>p</math> for the smallest element in the interval of <math>n,</math> then it is also congruent to <math>0</math> modulo <math>p</math> for all other elements in the interval of <math>n.</math></li><p> | ||
+ | </ol> | ||
+ | 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 | ||
+ | == Video Solution == | ||
We will use the following lemma to solve this problem. | We will use the following lemma to solve this problem. | ||
--------------------------- | --------------------------- | ||
Denote by <math>p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_m^{\alpha_m}</math> the prime factorization of <math>L_n</math>. | Denote by <math>p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_m^{\alpha_m}</math> the prime factorization of <math>L_n</math>. | ||
− | For any <math>i \in \left\{ 1, 2, \ | + | For any <math>i \in \left\{ 1, 2, \ldots, m \right\}</math>, denote <math>\sum_{j = 1}^{\left\lfloor \frac{n}{p_i^{\alpha_i}} \right\rfloor} \frac{1}{j} = \frac{a_i}{b_i}</math>, where <math>a_i</math> and <math>b_i</math> are relatively prime. |
Then | Then | ||
− | <math>k_n = L_n</math> if and only if for any <math>i \in \left\{ 1, 2, \ | + | <math>k_n = L_n</math> if and only if for any <math>i \in \left\{ 1, 2, \ldots, m \right\}</math>, <math>a_i</math> is not a multiple of <math>p_i</math>. |
--------------------------- | --------------------------- | ||
Line 27: | Line 77: | ||
</cmath> | </cmath> | ||
− | Therefore, the answer is <math>\boxed{\textbf{(D) 8 | + | Therefore, the answer is <math>\boxed{\textbf{(D) }8}</math>. |
− | < | + | <b>Note: Detailed analysis of this problem (particularly the motivation and the proof of the lemma above) can be found in my video solution below.</b> |
+ | ==Video Solution== | ||
https://youtu.be/4RHmsoDsU9E | https://youtu.be/4RHmsoDsU9E | ||
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | |||
+ | == Video Solution == | ||
+ | https://youtu.be/pZAez5A8tWA | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | ==Video Solution by Math-X== | ||
+ | https://youtu.be/7yAh4MtJ8a8?si=oklkf-_wUpjjfAed&t=8018 | ||
+ | |||
+ | ~Math-X | ||
== See Also == | == See Also == |
Latest revision as of 08:52, 29 March 2024
Contents
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
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
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.