Difference between revisions of "2020 AMC 10A Problems/Problem 24"
Line 6: | Line 6: | ||
== Solution 1 == | == Solution 1 == | ||
− | We know that <math>(n+57,63)=21, (n-57, 120)= 60</math>. Hence, <math>n+57=21\alpha,n-57=60 \gamma, (\alpha,3)=1, (\gamma,2)=1</math>. Subtracting the <math>2</math> equations, <math>38=7\alpha-20\gamma</math>. Letting <math>\gamma = 2s+1</math>, <math>58=7\alpha-40s</math>. Taking <math>\mod{40}, we have < | + | We know that <math>(n+57,63)=21, (n-57, 120)= 60</math>. Hence, <math>n+57=21\alpha,n-57=60 \gamma, (\alpha,3)=1, (\gamma,2)=1</math>. Subtracting the <math>2</math> equations, <math>38=7\alpha-20\gamma</math>. Letting <math>\gamma = 2s+1</math>, <math>58=7\alpha-40s</math>. Taking <math>\mod{40}</math>, we have <math>\alpha \equiv{14} \pmod{40}</math>. We are given <math>n=21\alpha -57 >1000 \implies \alpha \geq 51</math>. Notice that if <math>\alpha =54</math> then the condition <math>(\alpha,3)=1</math> is violated. The next possible value of <math>\alpha = 94</math> satisfies the given condition, giving us the answer <math>\boxed{1917}</math>. Alternatively, we could have said <math>\alpha = 40k+14 \equiv{0} \pmod{3}</math> for <math>k \equiv{1} \pmod{3}</math> only, so <math>k \equiv{0,2} \pmod{3}</math>, giving us our answer. |
Line 18: | Line 18: | ||
== Solution 2== | == Solution 2== | ||
− | We know that < | + | We know that <math>gcd(63, n+120)=21</math>, so we can write <math>n+120\equiv0\pmod {21}</math>. Simplifying, we get <math>n\equiv6\pmod {21}</math>. Similarly, we can write <math>n+63\equiv0\pmod {60}</math>, or <math>n\equiv-3\pmod {60}</math>. Solving these two modular congruences, <math>n\equiv237\pmod {420}</math> 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 <math>1000</math>, we find the least solution is <math>n=1077</math>. However, we are have not considered cases where <math>gcd(63, n+120) =63</math> or <math>gcd(n+63, 120) =120</math>. <math>{1077+120}\equiv0\pmod {63}</math> so we try <math>n=1077+420=1497</math>. <math>{1497+63}\equiv0\pmod {120}</math> so again we add <math>420</math> to <math>n</math>. It turns out that <math>n=1497+420=1917</math> does indeed satisfy the original conditions, so our answer is <math>1+9+1+7=\boxed{\textbf{(C) }18}</math>. |
==Solution 3 (bashing)== | ==Solution 3 (bashing)== | ||
− | We are given that < | + | We are given that <math>\gcd(63, n+120)=21</math> and <math>\gcd(n+63,120) = 60</math>. This tells us that <math>n+120</math> is divisible by <math>21</math> but not <math>63</math>. It also tells us that <math>n+63</math> is divisible by 60 but not 120. Starting, we find the least value of <math>n+120</math> which is divisible by <math>21</math> which satisfies the conditions for <math>n</math>, which is <math>1134</math>, making <math>n=1014</math>. We then now keep on adding <math>21</math> until we get a number which satisfies the second equation. This number turns out to be <math>1917</math>, whose digits add up to <math>\boxed{\textbf{(C) } 18}</math>. |
-Midnight | -Midnight | ||
Line 28: | Line 28: | ||
==Solution 4 (bashing but worse)== | ==Solution 4 (bashing but worse)== | ||
− | Assume that < | + | Assume that <math>n</math> has 4 digits. Then <math>n = abcd</math>, where <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math> represent digits of the number (not to get confused with <math>a * b * c * d</math>). As given the problem, <math>gcd(63, n + 120) = 21</math> and <math>gcd(n + 63, 120) = 60</math>. So we know that <math>d = 7</math> (last digit of <math>n</math>). That means that <math>12 + abc \equiv0\pmod {7}</math> and <math>7 + abc\equiv0\pmod {6}</math>. We can bash this after this. We just want to find all pairs of numbers <math>(x, y)</math> such that <math>x</math> is a multiple of 7 that is <math>5</math> greater than a multiple of <math>6</math>. Our equation for <math>12 + abc</math> would be <math>42*j + 35 = x</math> and our equation for <math>7 + abc</math> would be <math> 42*j + 30 = y</math>, where <math>j</math> is any integer. We plug this value in until we get a value of <math>abc</math> that makes <math>n = abc7</math> satisfy the original problem statement (remember, <math>abc > 100</math>). After bashing for hopefully a couple minutes, we find that <math>abc = 191</math> works. So <math>n = 1917</math> which means that the sum of its digits is <math>\boxed{\textbf{(C) } 18}</math>. |
~ Baolan | ~ Baolan | ||
==Solution 5== | ==Solution 5== | ||
− | The conditions of the problem reduce to the following. < | + | The conditions of the problem reduce to the following. <math>n+120 = 21k</math> where <math>gcd(k,3) = 1</math> and <math>n+63 = 60l</math> where <math>gcd(l,2) = 1</math>. From these equations, we see that <math>21k - 60l = 57</math>. Solving this diophantine equation gives us that <math>k = 20a + 17</math>, <math>l = 7a + 5</math> form. Since, <math>n</math> is greater than <math>1000</math>, we can do some bounding and get that <math>k > 53</math> and <math>l > 17</math>. Now we start the bash by plugging in numbers that satisfy these conditions. We get <math>l = 33</math>, <math>k = 97</math>. So the answer is <math>1917 \implies 1+9+1+7= |
− | \boxed{\textbf{(C) } 18}<math>. | + | \boxed{\textbf{(C) } 18}</math>. |
Edited by ~fastnfurious1 | Edited by ~fastnfurious1 | ||
==Solution 6== | ==Solution 6== | ||
− | You can first find that n must be congruent to < | + | You can first find that n must be congruent to <math>6\equiv0\pmod {21}</math> and <math>57\equiv0\pmod {60}</math>. The we can find that <math>n=21x+6</math> and <math>n=60y+57</math>, 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 <math>1+9+1+7 = \boxed{\textbf{(C) } 18}</math>.-happykeeper |
==Solution 7 (Reverse Euclidean Algorithm)== | ==Solution 7 (Reverse Euclidean Algorithm)== | ||
− | We are given that < | + | We are given that <math>\gcd(63, n+120) =21</math> and <math>\gcd(n+63, 120)=60.</math> By applying the Euclidean algorithm, but in reverse, we have <cmath>\gcd(63, n+120) = \gcd(63, n+120 + 63) = \gcd(63, n+183) = 21</cmath> and <cmath>\gcd(n+63, 120) = \gcd(n+63 + 120, 120) = \gcd(n+183, 120) = 60.</cmath> |
− | We now know that < | + | We now know that <math>n+183</math> must be divisible by <math>21</math> and <math>60,</math> so it is divisible by <math>\text{lcm}(21, 60) = 420.</math> Therefore, <math>n+183 = 420k</math> for some integer <math>k.</math> We know that <math>3 \nmid k,</math> or else the first condition won't hold (<math>\gcd</math> will be <math>63</math>) and <math>2 \nmid k,</math> or else the second condition won't hold (<math>\gcd</math> will be <math>120</math>). Since <math>k = 1</math> gives us too small of an answer, then <math>k=5 \implies n = 1917,</math> so the answer is <math>1+9+1+7 = \boxed{\textbf{(C) } 18}.</math> |
==Solution 8== | ==Solution 8== | ||
− | < | + | <math>\gcd(n+63,120)=60</math> tells us <math>n+63\equiv60\pmod {120}</math>. The smallest <math>n+63</math> that satisfies the previous condition and <math>n>1000</math> is <math>1140</math>, so we start from there. If <math>n+63=1140</math>, then <math>n+120=1197</math>. Because <math>\gcd(n+120,63)=21</math>, <math>n+120\equiv21\pmod {63}</math> or <math>n+120\equiv42\pmod {63}</math>. We see that <math>1197\equiv0\pmod {63}</math>, which does not fulfill the requirement for <math>n+120</math>, so we continue by keep on adding <math>120</math> to <math>1197</math>, in order to also fulfill the requirement for <math>n+63</math>. Soon, we see that <math>n+120\pmod {63}</math> decreases by <math>6</math> every time we add <math>120</math>, so we can quickly see that <math>n=1917</math> because at that point <math>n+120\equiv21\pmod {63}</math>. Adding up all the digits in <math>1917</math>, we have <math>\boxed{\textbf{(C) } 18}</math>. |
-SmileKat32 | -SmileKat32 | ||
Line 61: | Line 61: | ||
<cmath>21a + 6 = 60b + 57</cmath> | <cmath>21a + 6 = 60b + 57</cmath> | ||
<cmath>\implies 7a + 2 = 20b + 19.</cmath> | <cmath>\implies 7a + 2 = 20b + 19.</cmath> | ||
− | We know < | + | We know <math>7a \equiv 0 \pmod {7},</math> and since <math>7a = 20b + 17,</math> therefore <math>20b + 17 \equiv 0 \pmod{7}.</math> Simplifying this congruence further, we have |
<cmath>5b \equiv 1 \pmod{7}</cmath> | <cmath>5b \equiv 1 \pmod{7}</cmath> | ||
<cmath>\implies b \equiv 3 \pmod {7}.</cmath> | <cmath>\implies b \equiv 3 \pmod {7}.</cmath> | ||
− | Thus, by definition, < | + | Thus, by definition, <math>b = 7x + 3.</math> Substituting this back into our original equation, |
<cmath>n = 60(7x + 3) + 57</cmath> | <cmath>n = 60(7x + 3) + 57</cmath> | ||
<cmath>\implies n = 420x + 180 + 57</cmath> | <cmath>\implies n = 420x + 180 + 57</cmath> | ||
Line 70: | Line 70: | ||
By definition, we are able to set-up the following congruence: | By definition, we are able to set-up the following congruence: | ||
<cmath>n \equiv 237 \pmod{420}.</cmath> | <cmath>n \equiv 237 \pmod{420}.</cmath> | ||
− | Thus, < | + | Thus, <math>n = 1917</math>, so our answer is simply <math>\boxed{18}</math>. |
− | (Remarks. < | + | (Remarks. <math>n \equiv 6 \pmod{21}</math> since <math>n \equiv -120 \pmod{21},</math> by definition & <math>n \equiv 57 \pmod{60}</math> since <math>n \equiv -63 \pmod{60},</math> by definition. |
− | Remember, < | + | Remember, <math>5b \equiv 1 \pmod{7} \implies 5b \equiv 15 \pmod{7} \implies b \equiv 3 \pmod{7}.</math> |
− | Lastly, the reason why < | + | Lastly, the reason why <math>n \neq 1077</math> is <math>n + 120</math> would be divisible by <math>63</math>, which is not possible due to the certain condition.) |
~ nikenissan | ~ nikenissan | ||
Line 82: | Line 82: | ||
== Solution 10== | == Solution 10== | ||
− | First, we find < | + | First, we find <math>n</math>. We know that it is greater than <math>1000</math>, so we first input <math>n = 1000</math>. From the first equation, <math>gcd(63, n + 120) = 21</math>, we know that if <math>n</math> is correct, after we add <math>120</math> to it, it should be divisible by <math>21</math>, but not <math>63</math>. |
<cmath>\frac{n + 120}{21}, </cmath> | <cmath>\frac{n + 120}{21}, </cmath> | ||
<cmath>\frac{1120}{21}, </cmath> | <cmath>\frac{1120}{21}, </cmath> | ||
<cmath>53 r 7. </cmath> | <cmath>53 r 7. </cmath> | ||
− | Uh oh. To get to the nearest number divisible by < | + | Uh oh. To get to the nearest number divisible by <math>21</math>, we have to add <math>14</math> to cancel out the remainder. (Note that we don't subtract <math>7</math> to get to <math>53</math>; <math>n</math> is already at its lowest possible value!) |
− | Adding < | + | Adding <math>14</math> to <math>1000</math> gives us <math>n = 1014</math>. (Note: <math>n</math> is currently divisible by 63, but that's fine since we'll be changing it in the next step.) |
− | Now using, the second equation, < | + | Now using, the second equation, <math>gcd(n + 63, 120) = 60</math>, we know that if <math>n</math> is correct, after we add <math>63</math> to it, it should be divisible by <math>60</math>, but not <math>120</math>. |
<cmath>\frac{n + 63}{60}, </cmath> | <cmath>\frac{n + 63}{60}, </cmath> | ||
<cmath>\frac{1077}{60}, </cmath> | <cmath>\frac{1077}{60}, </cmath> | ||
<cmath>17r57. </cmath> | <cmath>17r57. </cmath> | ||
− | Uh oh (again). This requires some guessing and checking. We can add < | + | Uh oh (again). This requires some guessing and checking. We can add <math>21</math> over and over again until <math>n</math> is valid. This changes <math>n</math> while also maintaining that <math>\frac{n + 120}{21}</math> has no remainders. |
− | After adding < | + | After adding <math>21</math> once, we get <math>18 r 18</math>. By pure luck, adding <math>21</math> two more times gives us <math>19</math> with no remainders. |
− | We now have < | + | We now have <math>1077 + 21 + 21 + 21 = 1140</math>. However, this number is divisible by <math>120</math>. To get the next possible number, we add the LCM of <math>21</math> and <math>60</math> (once again, to maintain divisibility), which is <math>420</math>. Unfortunately, <math>1140 + 420 = 1560</math> is still divisible by <math>120</math>. Adding <math>420</math> again gives us <math>1980</math>, which is valid. However, remember that this is equal to <math>n + 63</math>, so subtracting <math>63</math> from <math>1980</math> gives us <math>1917</math>, which is <math>n</math>. |
− | The sum of its digits are < | + | The sum of its digits are <math>1 + 9 + 1 + 7 = 18</math>. |
− | So, our answer is < | + | So, our answer is <math>\boxed{\textbf{(C) }18}</math>. ~ primegn |
== Video Solution 1 == | == Video Solution 1 == |
Revision as of 08:06, 25 December 2020
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 . Hence,
. Subtracting the
equations,
. Letting
,
. Taking
, we have
. We are given
. Notice that if
then the condition
is violated. The next possible value of
satisfies the given condition, giving us the answer
. Alternatively, we could have said
for
only, so
, giving us our answer.
~Prabh1512
Solution 2
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 3 (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 4 (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 5
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 6
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 7 (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 8
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 9
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 know
and since
therefore
Simplifying this congruence further, we have
Thus, by definition,
Substituting this back into our original equation,
By definition, we are able to set-up the following congruence:
Thus,
, so our answer is simply
.
(Remarks. since
by definition &
since
by definition.
Remember,
Lastly, the reason why is
would be divisible by
, which is not possible due to the certain condition.)
~ nikenissan
Solution 10
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
.
Uh oh. 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, after we add
to it, it should be divisible by
, but not
.
Uh oh (again). 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 .
So, our answer is . ~ primegn
Video Solution 1
https://youtu.be/tk3yOGG2K-s ~ Richard Rusczyk
Video Solution 2
Education The Study of Everything
Video Solution 3
https://www.youtube.com/watch?v=gdGmSyzR908&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=5 ~ MathEx
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.