Difference between revisions of "2020 AMC 10A Problems/Problem 24"
m (→Solution 4) |
|||
Line 39: | Line 39: | ||
-SmileKat32 | -SmileKat32 | ||
+ | |||
+ | ==Solution 8 (bashing with 420)== | ||
+ | Because <math>\gcd(n+120, 63)=21</math>, this means that <math>n+120</math> is divisible by <math>21</math> but not by <math>63</math>. This also applies to <math>n+63</math> in the same way, where <math>n+63</math> is divisible by <math>60</math> but not <math>120</math>. Because <math>n+120</math> is divisble by <math>21</math>, this also means that <math>n+15</math> is divisble by <math>21</math> because <math>120\pmod {21}</math> is equal to <math>15</math>, and by a similar logic,<math>n+3</math> is divisible by <math>60</math> because <math>63\pmod {60}</math> is equal to <math>3</math>. | ||
+ | |||
+ | This means that <math>n</math> is <math>15</math> less than a multiple of <math>21</math>(<math>n+15</math>) which is <math>12</math> more than a multiple of <math>60</math>(<math>n+3</math>). Thus we look for multiples of <math>21</math> that are <math>12</math> more than a multiple of <math>60</math>, and are over <math>1000</math>, and then check if it is either divisible by <math>63</math>, or the number <math>12</math> less than it is divisible than <math>120</math>. This brings us to <math>1092</math> first, however <math>1080(1092-12)</math> is divisible by <math>120</math>. We then repeatedly add <math>420</math>(the lcm of <math>21</math> and <math>12</math>) until we find a suitable number, which turns out to be <math>1932</math>. Subtracting <math>15</math> and we get <math>1917</math>, whose digits add up to <math>\boxed{(C)18}</math>. | ||
+ | |||
+ | - Jeffereeeeeee | ||
+ | |||
== Video Solution == | == Video Solution == |
Revision as of 15:21, 16 May 2020
Contents
[hide]Problem
Let be the least positive integer greater than
for which
What is the sum of the digits of
?
Solution 1
We know that , so we can write
. Simplifying, we get
. Similarly, we can write
, or
. Solving these two modular congruences,
which we know is the only solution by CRT (Chinese Remainder Theorem used to so,be a system of MODULAR CONGURENCES). Now, since the problem is asking for the least positive integer greater than
, we find the least solution is
. However, we are have not considered cases where
or
.
so we try
.
so again we add
to
. It turns out that
does indeed satisfy the original conditions, so our answer is
.
Solution 2 (bashing)
We are given that and
. This tells us that
is divisible by
but not
. It also tells us that
is divisible by 60 but not 120. Starting, we find the least value of
which is divisible by
which satisfies the conditions for
, which is
, making
. We then now keep on adding
until we get a number which satisfies the second equation. This number turns out to be
, whose digits add up to
.
-Midnight
Solution 3 (bashing but worse)
Assume that has 4 digits. Then
, where
,
,
,
represent digits of the number (not to get confused with
). As given the problem,
and
. So we know that
(last digit of
). That means that
and
. We can bash this after this. We just want to find all pairs of numbers
such that
is a multiple of 7 that is
greater than a multiple of
. Our equation for
would be
and our equation for
would be
, where
is any integer. We plug this value in until we get a value of
that makes
satisfy the original problem statement (remember,
). After bashing for hopefully a couple minutes, we find that
works. So
which means that the sum of its digits is
.
~ Baolan
Solution 4
The conditions of the problem reduce to the following. where
and
where
. From these equations, we see that
. Solving this diophantine equation gives us that
,
form. Since,
is greater than
, we can do some bounding and get that
and
. Now we start the bash by plugging in numbers that satisfy these conditions. We get
,
. So the answer is
.
Edited by ~fastnfurious1
Solution 5
You can first find that n must be congruent to and
. The we can find that
and
, where x and y are integers. Then we can find that y must be odd, since if it was even the gcd will be 120, not 60. Also, the unit digit of n has to be 7, since the unit digit of 60y is always 0 and the unit digit of 57 is 7. Therefore, you can find that x must end in 1 to satisfy n having a unit digit of 7. Also, you can find that x must not be a multiple of three or else the gcd will be 63. Therefore, you can test values for x and you can find that x=91 satisfies all these conditions.Therefore, n is 1917 and
=
.-happykeeper
Solution 6 (Reverse Euclidean Algorithm)
We are given that and
By applying the Euclidean algorithm, but 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
so the answer is
Solution 7
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
. Adding up all the digits in
, we have
.
-SmileKat32
Solution 8 (bashing with 420)
Because , this means that
is divisible by
but not by
. This also applies to
in the same way, where
is divisible by
but not
. Because
is divisble by
, this also means that
is divisble by
because
is equal to
, and by a similar logic,
is divisible by
because
is equal to
.
This means that is
less than a multiple of
(
) which is
more than a multiple of
(
). Thus we look for multiples of
that are
more than a multiple of
, and are over
, and then check if it is either divisible by
, or the number
less than it is divisible than
. This brings us to
first, however
is divisible by
. We then repeatedly add
(the lcm of
and
) until we find a suitable number, which turns out to be
. Subtracting
and we get
, whose digits add up to
.
- Jeffereeeeeee
Video Solution
https://youtu.be/tk3yOGG2K-s -
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.