Difference between revisions of "2020 AMC 10A Problems/Problem 24"
MRENTHUSIASM (talk | contribs) m (→Solution 8 (Euclidean Algorithm)) |
MRENTHUSIASM (talk | contribs) m (→Solution 8 (Euclidean Algorithm): Cleaned up notations.) |
||
Line 91: | Line 91: | ||
More generally, let <math>t\in\{1,2\},</math> so we get | More generally, let <math>t\in\{1,2\},</math> so we get | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | n+120-63k_1&=21t, &\hspace{55.5mm}(1 | + | n+120-63k_1&=21t, &\hspace{55.5mm}(1) \\ |
− | n+63-120k_2&=60. &\hspace{55.5mm}(2 | + | n+63-120k_2&=60. &\hspace{55.5mm}(2) |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Subtracting <math>(2 | + | Subtracting <math>(2)</math> from <math>(1)</math> and then simplifying give |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
57-63k_1+120k_2&=21t-60 \\ | 57-63k_1+120k_2&=21t-60 \\ | ||
Line 105: | Line 105: | ||
k_2&\equiv2\pmod{7}. | k_2&\equiv2\pmod{7}. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Recall that <math>n>1000.</math> From <math>(2 | + | Recall that <math>n>1000.</math> From <math>(2),</math> it follows that <cmath>1063-120k_2<n+63-120k_2=60,</cmath> from which <math>k_2>8.</math> Therefore, the possible values for <math>k_2</math> are <math>9,16,23,\ldots.</math> |
− | We need to check whether positive integers <math>k_1</math> and <math>t</math> (where <math>t\in\{1,2\}</math>) exist in <math>(1 | + | We need to check whether positive integers <math>k_1</math> and <math>t</math> (where <math>t\in\{1,2\}</math>) exist in <math>(1):</math> |
<ul style="margin-left: 1.5em, list-style-type: square;"> | <ul style="margin-left: 1.5em, list-style-type: square;"> | ||
− | <li>If <math>k_2=9,</math> then substituting into <math>(2 | + | <li>If <math>k_2=9,</math> then substituting into <math>(2)</math> gives <math>n=1077.</math> Next, substituting into <math>(1)</math> produces <math>1197-63k_1=21t,</math> or <math>57-3k_1=t.</math> <p> |
There are no solutions <math>(k_1,t).</math></li><p> | There are no solutions <math>(k_1,t).</math></li><p> | ||
− | <li>If <math>k_2=16,</math> then substituting into <math>(2 | + | <li>If <math>k_2=16,</math> then substituting into <math>(2)</math> gives <math>n=1917.</math> Next, substituting into <math>(1)</math> produces <math>2037-63k_1=21t,</math> or <math>97-3k_1=t.</math> <p> |
The solution is <math>(k_1,t)=(32,1).</math></li><p> | The solution is <math>(k_1,t)=(32,1).</math></li><p> | ||
</ul> | </ul> |
Revision as of 03:07, 26 January 2022
Contents
Problem
Let be the least positive integer greater than
for which
What is the sum of the digits of ?
Solution 1
We know that and
by the Euclidean Algorithm. Hence, let
and
, where
and
. Subtracting the two equations,
. Letting
, we get
. Taking modulo
, we have
. We are given that
, so
. Notice that if
then the condition
is violated. The next possible value of
satisfies the given condition, giving us
.
Alternatively, we could have said for
only, so
, giving us our answer. Since the problem asks for the sum of the digits of
, our answer is
.
~Prabh1512, with edits by Terribleteeth.
Solution 2
The conditions of the problem reduce to the following: and
, where
and
. From these equations, we see that
. Solving this Diophantine equation gives us that
and
. Since,
, we can do some bounding and get that
and
. Now we start bashing by plugging in numbers that satisfy these conditions:
is the first number that works so we get
,
. Therefore, we have
, and our answer is
.
Solution 3
We first find that and
, then we get
and
by definitions, where
and
are integers. It follows that
must be odd, since the GCD will be
instead of
if
is even. Also, the unit digit of
must be
, since the unit digit of
is always
and the unit digit of
is
. Therefore, we find that
must end in
to satisfy
having a unit digit of
. Also, we find that
must not be a multiple of
or else the GCD will be
. Therefore, we test values for
and find that
satisfies all these conditions. Therefore,
and
.
~happykeeper
Solution 4
We are given that and
By applying the Euclidean algorithm in reverse, we have
and
We now know that must be divisible by
and
so it is divisible by
Therefore,
for some integer
We know that
or else the first condition won't hold (
will be
) and
or else the second condition won't hold (
will be
). Since
gives us too small of an answer, then
from which
So, the answer is
Solution 5
tells us
. The smallest
that satisfies the previous condition and
is
, so we start from there. If
, then
. Because
,
or
. We see that
, which does not fulfill the requirement for
, so we continue by keep on adding
to
, in order to also fulfill the requirement for
. Soon, we see that
decreases by
every time we add
, so we can quickly see that
because at that point
. We add up all digits of
to get
.
~SmileKat32
Solution 6
We are able to set up the following system of congruences:
Therefore, by definition, we are able to set-up the following system of equations:
Thus, we have
from which
We know
and since
therefore
Simplifying this congruence further, we have
Thus, by definition,
Substituting this back into our original equation, we get
By definition, we are able to set up the following congruence:
Thus,
, so our answer is simply
.
Remark
Since we conclude that
Since we conclude that
Remember that
Lastly, the reason why is
would be divisible by
, which is not possible due to the certain condition.
~nikenissan ~Midnight
Solution 7
First, we find . We know that it is greater than
, so we first input
. From the first equation,
, we know that if
is correct, after we add
to it, it should be divisible by
, but not
:
This does not work. To get to the nearest number divisible by
, we have to add
to cancel out the remainder. (Note that we don't subtract
to get to
;
is already at its lowest possible value!)
Adding
to
gives us
. (Note:
is currently divisible by 63, but that's fine since we'll be changing it in the next step.)
Now using the second equation, , we know that if
is correct, then
is divisible by
but not
:
Again, this does not work. This requires some guessing and checking. We can add
over and over again until
is valid. This changes
while also maintaining that
has no remainders.
After adding
once, we get
. By pure luck, adding
two more times gives us
with no remainders.
We now have
. However, this number is divisible by
. To get the next possible number, we add the LCM of
and
(once again, to maintain divisibility), which is
. Unfortunately,
is still divisible by
. Adding
again gives us
, which is valid. However, remember that this is equal to
, so subtracting
from
gives us
, which is
.
The sum of its digits are .
~primegn
Solution 8 (Euclidean Algorithm)
By the Euclidean Algorithm, we have
Clearly,
must be either
or
and
must be
More generally, let so we get
Subtracting
from
and then simplifying give
Taking
modulo
produces
Recall that
From
it follows that
from which
Therefore, the possible values for
are
We need to check whether positive integers and
(where
) exist in
- If
then substituting into
gives
Next, substituting into
produces
or
There are no solutions
- If
then substituting into
gives
Next, substituting into
produces
or
The solution is
Finally, the least such positive integer is
The sum of its digits is
~MRENTHUSIASM
Solution 9 (Euclidean Algorithm)
Because we are finding value of for
, let
.
Using the Euclidian Algorithm,
So, we have
Let
,
,
,
is a multiple of
.
Let ,
,
.
,
.
By substituting ,
,
into
and
,
and
aren't valid answers, only
is. Therefore, the answer is
.
Solution 10 (Diophantine Equations)
We know , and
, where
is not a multiple of
.
Also, , and
, where
is not a multiple of
.
Let ,
,
.
Now the problem becomes and
.
Meaning has to be a multiple of
but not
, and
is a multiple of
but not
.
Using trial and error, the least values are and
.
Therefore, the answer is .
Solution 11 (Chinese Remainder Theorem)
We have
So, we conclude that
and
, respectively.
Because the moduli
and
are not relatively prime, namely
,
, and
, we convert the system of
linear congruences with non-coprime moduli into a system of
linear congruences with coprime moduli:
By Chinese Remainder Theorem, the general solution of system of
linear congruences is
We construct the following table:
Only
satisfies
and
. Therefore, the answer is
.
Video Solutions
Video Solution 1 (Richard Rusczyk)
https://artofproblemsolving.com/videos/amc/2020amc10a/514
Video Solution 2
https://youtu.be/8mNMKH0T9W0 - Happytwin
Video Solution 3 (Quick & Simple)
Education The Study of Everything
Video Solution 4
https://www.youtube.com/watch?v=gdGmSyzR908&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=5 ~ MathEx
Video Solution 5
https://youtu.be/R220vbM_my8?t=899 ~ amritvignesh0719062.0
See Also
2020 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 23 |
Followed by Problem 25 | |
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 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.