Difference between revisions of "2013 AMC 10B Problems/Problem 25"
(→Shortcut) |
m (→Solution 2) |
||
(108 intermediate revisions by 20 users not shown) | |||
Line 7: | Line 7: | ||
<math> \textbf{(A)}\ 5 \qquad\textbf{(B)}\ 10 \qquad\textbf{(C)}\ 15 \qquad\textbf{(D)}\ 20 \qquad\textbf{(E)}\ 25</math> | <math> \textbf{(A)}\ 5 \qquad\textbf{(B)}\ 10 \qquad\textbf{(C)}\ 15 \qquad\textbf{(D)}\ 20 \qquad\textbf{(E)}\ 25</math> | ||
− | ==Solution== | + | ==Solution 1== |
First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities. | First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities. | ||
Line 14: | Line 14: | ||
also that <math>N \equiv b \pmod{5}</math> | also that <math>N \equiv b \pmod{5}</math> | ||
− | Substituting these equations into the question and setting the units digits of 2N and S equal to each other, it can be seen that | + | Substituting these equations into the question and setting the units digits of <math>2N</math> and <math>S</math> equal to each other, it can be seen that <math>b < 5</math> (because otherwise <math>a</math> and <math>b</math> will have different parities), and thus <math>a=b</math>. |
<math>N \equiv a \pmod{6}</math>, | <math>N \equiv a \pmod{6}</math>, | ||
<math>N \equiv a \pmod{5}</math>, | <math>N \equiv a \pmod{5}</math>, | ||
Line 23: | Line 23: | ||
and <math>2N</math> can be written as <math>60x+2y</math> | and <math>2N</math> can be written as <math>60x+2y</math> | ||
− | + | Just keep in mind that <math>y</math> can be one of five choices: <math>0, 1, 2, 3,</math> or <math>4</math>, ; | |
Also, we have already found which digits of <math>y</math> will add up into the units digits of <math>2N</math>. | Also, we have already found which digits of <math>y</math> will add up into the units digits of <math>2N</math>. | ||
Now, examine the tens digit, <math>x</math> by using <math>\mod{25}</math> and <math>\mod{36}</math> to find the tens digit (units digits can be disregarded because <math>y=0,1,2,3,4</math> will always work) | Now, examine the tens digit, <math>x</math> by using <math>\mod{25}</math> and <math>\mod{36}</math> to find the tens digit (units digits can be disregarded because <math>y=0,1,2,3,4</math> will always work) | ||
− | Then we | + | Then we take <math>N=30x+y</math> <math>\mod{25}</math> and <math>\mod{36}</math> to find the last two digits in the base <math>5</math> and <math>6</math> representation. |
<cmath>N \equiv 30x \pmod{36}</cmath> | <cmath>N \equiv 30x \pmod{36}</cmath> | ||
<cmath>N \equiv 30x \equiv 5x \pmod{25}</cmath> | <cmath>N \equiv 30x \equiv 5x \pmod{25}</cmath> | ||
Line 36: | Line 36: | ||
Now, since <math>y=0,1,2,3,4</math> will always work if <math>x</math> works, then we can treat <math>x</math> as a units digit instead of a tens digit in the respective bases and decrease the mods so that <math>x</math> is now the units digit. | Now, since <math>y=0,1,2,3,4</math> will always work if <math>x</math> works, then we can treat <math>x</math> as a units digit instead of a tens digit in the respective bases and decrease the mods so that <math>x</math> is now the units digit. | ||
+ | <cmath>N \equiv 5x \pmod{6}</cmath> | ||
<cmath>N \equiv 6x \equiv x \pmod{5}</cmath> | <cmath>N \equiv 6x \equiv x \pmod{5}</cmath> | ||
− | |||
<cmath>2N\equiv 6x \pmod{10}</cmath> | <cmath>2N\equiv 6x \pmod{10}</cmath> | ||
Line 53: | Line 53: | ||
<cmath>2N\equiv 6n \pmod{10}</cmath> | <cmath>2N\equiv 6n \pmod{10}</cmath> | ||
− | From inspection, when | + | From careful inspection, this is true when |
<math>n=0, m=6</math> | <math>n=0, m=6</math> | ||
Line 68: | Line 68: | ||
<math>5* 5 = \boxed{\textbf{(E) }25}</math> | <math>5* 5 = \boxed{\textbf{(E) }25}</math> | ||
− | == | + | ==Solution 2== |
− | Notice that there are exactly <math>1000-100=900=5^2\cdot 6^2</math> possible values of <math> | + | Notice that there are exactly <math>1000-100=900=5^2\cdot 6^2</math> possible values of <math>N</math>. This means, in <math>100\le N\le 999</math>, every possible combination of <math>2</math> digits will happen exactly once. We know that <math>N=900,901,902,903,904</math> work because <math>900\equiv\dots00_5\equiv\dots00_6</math>. |
− | We know for sure that the units digit will add perfectly every <math>30</math> added or subtracted, because <math>\text{lcm }5,6=30</math>. So we only have to care about cases of <math> | + | We know for sure that the units digit will add perfectly every <math>30</math> added or subtracted, because <math>\text{lcm }(5, 6)=30</math>. So we only have to care about cases of <math>N</math> every <math>30</math> subtracted. In each case, <math>2N</math> subtracts <math>6</math>/adds <math>4</math>, <math>N_5</math> subtracts <math>1</math> and <math>N_6</math> adds <math>1</math> for the <math>10</math>'s digit. |
− | < | + | <cmath>\textbf{5 }\textcolor{red}{\text{ 0}}\text{ 4 3 2 1 0 }\textcolor{red}{\text{4}}\text{ 3 2 1 0 4 3 2 1 0 4 }\textcolor{red}{\text{3 2}}\text{ 1 0 4 3 2 1 0 4 3 2 }\textcolor{red}{\text{1}}</cmath> |
− | + | ||
− | + | <cmath>\textbf{6 }\textcolor{red}{\text{ 0}}\text{ 1 2 3 4 5 }\textcolor{red}{\text{0}}\text{ 1 2 3 4 5 0 1 2 3 4 }\textcolor{red}{\text{5 0}}\text{ 1 2 3 4 5 0 1 2 3 4 }\textcolor{red}{\text{5}}</cmath> | |
− | + | ||
− | + | <cmath>\textbf{10}\textcolor{red}{\text{ 0}}\text{ 4 8 2 6 0 }\textcolor{red}{\text{4}}\text{ 8 2 6 0 4 8 2 6 0 4 }\textcolor{red}{\text{8 2}}\text{ 6 0 4 8 2 6 0 4 8 2 }\textcolor{red}{\text{6}}</cmath> | |
As we can see, there are <math>5</math> cases, including the original, that work. These are highlighted in <math>\textcolor{red}{\text{red}}</math>. So, thus, there are <math>5</math> possibilities for each case, and <math>5\cdot 5=\boxed{\textbf{(E) }25}</math>. | As we can see, there are <math>5</math> cases, including the original, that work. These are highlighted in <math>\textcolor{red}{\text{red}}</math>. So, thus, there are <math>5</math> possibilities for each case, and <math>5\cdot 5=\boxed{\textbf{(E) }25}</math>. | ||
− | == See | + | == Solution 3 == |
+ | |||
+ | Notice that <math>N_5</math> ranges from <math>3</math> to <math>5</math> digits and <math>N_6</math> ranges from <math>3</math> to <math>4</math> digits. | ||
+ | |||
+ | Then let <math>a_i</math>, <math>b_i</math> denotes the digits of <math>N_5</math>, <math>N_6</math>, respectively such that <cmath>0\le a_i<5,0\le b_i<6</cmath> Thus we have <cmath>N=5^4a_1+5^3a_2+5^2a_3+5a_4+a_5=6^3b_1+6^2b_2+6b_3+b_4</cmath> | ||
+ | <cmath>625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4</cmath> | ||
+ | Now we are given <cmath>2N \equiv S \equiv N_5+N_6\pmod{100}</cmath> | ||
+ | <cmath>2(625a_1+125a_2+25a_3+5a_4+a_5) \equiv (10000a_1+1000a_2+100a_3+10a_4+a_5)+(1000b_1+100b_2+10b_3+b_4)\pmod{100}</cmath> | ||
+ | <cmath>1250a_1+250a_2+50a_3+10a_4+2a_5 \equiv 10000a_1+1000a_2+1000b_1+100a_3+100b_2+10a_4+10b_3+a_5+b_4\pmod{100}</cmath> | ||
+ | <cmath>50a_1+50a_2+50a_3+10a_4+2a_5 \equiv 10a_4+10b_3+a_5+b_4\pmod{100}</cmath> | ||
+ | Canceling out <math>a_5</math> left with | ||
+ | <cmath>50a_1+50a_2+50a_3+10a_4+a_5 \equiv 10a_4+10b_3+b_4\pmod{100}</cmath> | ||
+ | |||
+ | Since <math>a_5</math>, <math>b_4</math> determine the unit digits of the two sides of the congruence equation, we have <math>a_5=b_4=0,1,2,3,4</math>. Thus, | ||
+ | |||
+ | <cmath>50a_1+50a_2+50a_3+10a_4 \equiv 10a_4+10b_3\pmod{100}</cmath> canceling out <math>10a_4</math>, we have | ||
+ | <cmath>50a_1+50a_2+50a_3 \equiv 10b_3\pmod{100}</cmath> | ||
+ | <cmath>5a_1+5a_2+5a_3 \equiv b_3\pmod{10}</cmath> | ||
+ | <cmath>5(a_1+a_2+a_3) \equiv b_3\pmod{10}</cmath> | ||
+ | |||
+ | Thus <math>b_3</math> is a multiple of <math>5</math>. | ||
+ | |||
+ | Now going back to our original equation | ||
+ | <cmath>625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4</cmath> | ||
+ | Since <math>a_5=b_4</math>, | ||
+ | <cmath>625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3</cmath> | ||
+ | <cmath>5(125a_1+25a_2+5a_3+a_4)=6(36b_1+6b_2+b_3)</cmath> | ||
+ | <cmath>5(125a_1+25a_2+5a_3+a_4)=6[6(6b_1+b_2)+b_3]</cmath> | ||
+ | |||
+ | Since the left side is a multiple of <math>5</math>, then so does the right side. Thus <math>5\mid6(6b_1+b_2)+b_3</math>. | ||
+ | |||
+ | Since we already know that <math>5\mid b_3</math>, then <math>5\mid6(6b_1+b_2)</math>, from where we also know that <math>5\mid6b_1+b_2</math>. | ||
+ | |||
+ | For <math>b_1,b_2<6</math>, there is a total of 7 ordered pairs that satisfy the condition. Namely, | ||
+ | |||
+ | <cmath>(b_1,b_2)=(0,0),(0,5),(1,4),(2,3),(3,2),(4,1),(5,0)</cmath> | ||
+ | |||
+ | Since <math>N_6</math> has at least <math>3</math> digits, <math>(b_1,b_2)=(0,0)</math> doesn't work. Furthermore, when <math>b_1=5</math>, <math>216b_1</math> exceeds <math>1000</math> which is not possible as <math>N</math> is a three digit number, thus <math>(b_1,b_2)=(5,0)</math> won't work as well. | ||
+ | |||
+ | Since we know that <math>a_i<5</math>, for each of the ordered pairs <math>(b_1,b_2)</math>, there is respectively one and only one solution <math>(a_1,a_2,a_3,a_4)</math> that satisfies the equation | ||
+ | |||
+ | <cmath>625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3</cmath> | ||
+ | |||
+ | Thus there are five solutions to the equation. Also since we have 5 possibilities for <math>a_5=b_4</math>, we have a total of <math>5\cdot5=25</math> values for <math>N</math>. <math>\boxed{\textbf{(E) }25}</math> | ||
+ | |||
+ | ~ Nafer | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | Observe that the maximum possible value of the sum of the last two digits of the base <math>5</math> number and the base <math>6</math> number is <math>44+55=99</math>. | ||
+ | Let <math>N \equiv a \pmod {25}</math> and <math>N \equiv b \pmod {36}</math>. | ||
+ | |||
+ | If <math>a < \frac{25}{2}</math>, <math>2N \equiv 2a \pmod {25}</math> and if <math>a > \frac{25}{2}</math>, <math>2N \equiv 2a - 25 \pmod {25}</math>. | ||
+ | |||
+ | Using the same logic for <math>b</math>, if <math>b < 18</math>, <math>2N \equiv 2b \pmod {36}</math>, and in the other case <math>2N \equiv 2b - 36 \pmod {36}</math>. | ||
+ | |||
+ | We can do four cases: | ||
+ | |||
+ | Case 1: <math>a + b = 2a - 25 + 2b - 36 \implies a + b = 61</math>. | ||
+ | |||
+ | For this case, there is trivially only one possible solution, <math>(a, b) = (25, 36)</math>, which is equivalent to <math>(a, b) = (0, 0)</math>. | ||
+ | |||
+ | Case 2: <math>a + b = 2a - 25 + 2b \implies a + b = 25</math>. | ||
+ | |||
+ | Note that in this case, <math>a \geq 13</math> must hold, and <math>b < 18</math> must hold. | ||
+ | We find the possible ordered pairs to be: <math>(13, 12), (14, 11), (15, 10), ..., (24, 1)</math> for a total of <math>12</math> ordered pairs. | ||
+ | |||
+ | Case 3: <math>a + b = 2a + 2b - 36 \implies a + b = 36</math>. | ||
+ | |||
+ | Note that in this case, <math>b \geq 18</math> must hold, and <math>a < 13</math> must hold. | ||
+ | We find the possible ordered pairs to be: <math>(24, 12), (25, 11), (26, 10), ..., (35, 1)</math> for a total of <math>12</math> ordered pairs. | ||
+ | |||
+ | Case 4: <math>a + b = 2a + 2b</math>. | ||
+ | |||
+ | Trivially no solutions except <math>(a, b) = (0, 0)</math>, which matches the solution in Case 1, which makes this an overcount. | ||
+ | |||
+ | By CRT, each solution <math>(a, b)</math> corresponds exactly one positive integer in a set of exactly <math>\text{lcm} (25, 36) = 900</math> consecutive positive integers, and since there are <math>900</math> positive integers between <math>100</math> and <math>999</math>, our induction is complete, and our answer is <math>1 + 12 + 12 = \boxed{\textbf{(E) }25}</math>. | ||
+ | |||
+ | ~ fidgetboss_4000 | ||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://www.youtube.com/watch?v=tgCK-H5jsOE&t=497s | ||
+ | |||
+ | ==See Also== | ||
+ | |||
{{AMC12 box|year=2013|ab=B|num-b=22|num-a=24}} | {{AMC12 box|year=2013|ab=B|num-b=22|num-a=24}} | ||
Latest revision as of 17:45, 8 November 2024
- The following problem is from both the 2013 AMC 12B #23 and 2013 AMC 10B #25, so both problems redirect to this page.
Problem
Bernardo chooses a three-digit positive integer and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an integer . For example, if , Bernardo writes the numbers and , and LeRoy obtains the sum . For how many choices of are the two rightmost digits of , in order, the same as those of ?
Solution 1
First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities.
Say that
also that
Substituting these equations into the question and setting the units digits of and equal to each other, it can be seen that (because otherwise and will have different parities), and thus . , , ,
Therefore, can be written as and can be written as
Just keep in mind that can be one of five choices: or , ; Also, we have already found which digits of will add up into the units digits of .
Now, examine the tens digit, by using and to find the tens digit (units digits can be disregarded because will always work) Then we take and to find the last two digits in the base and representation. Both of those must add up to
()
Now, since will always work if works, then we can treat as a units digit instead of a tens digit in the respective bases and decrease the mods so that is now the units digit.
Say that (m is between 0-6, n is 0-4 because of constraints on x) Then
and this simplifies to
From careful inspection, this is true when
This gives you choices for , and choices for , so the answer is
Solution 2
Notice that there are exactly possible values of . This means, in , every possible combination of digits will happen exactly once. We know that work because .
We know for sure that the units digit will add perfectly every added or subtracted, because . So we only have to care about cases of every subtracted. In each case, subtracts /adds , subtracts and adds for the 's digit.
As we can see, there are cases, including the original, that work. These are highlighted in . So, thus, there are possibilities for each case, and .
Solution 3
Notice that ranges from to digits and ranges from to digits.
Then let , denotes the digits of , , respectively such that Thus we have Now we are given Canceling out left with
Since , determine the unit digits of the two sides of the congruence equation, we have . Thus,
canceling out , we have
Thus is a multiple of .
Now going back to our original equation Since ,
Since the left side is a multiple of , then so does the right side. Thus .
Since we already know that , then , from where we also know that .
For , there is a total of 7 ordered pairs that satisfy the condition. Namely,
Since has at least digits, doesn't work. Furthermore, when , exceeds which is not possible as is a three digit number, thus won't work as well.
Since we know that , for each of the ordered pairs , there is respectively one and only one solution that satisfies the equation
Thus there are five solutions to the equation. Also since we have 5 possibilities for , we have a total of values for .
~ Nafer
Solution 4
Observe that the maximum possible value of the sum of the last two digits of the base number and the base number is . Let and .
If , and if , .
Using the same logic for , if , , and in the other case .
We can do four cases:
Case 1: .
For this case, there is trivially only one possible solution, , which is equivalent to .
Case 2: .
Note that in this case, must hold, and must hold. We find the possible ordered pairs to be: for a total of ordered pairs.
Case 3: .
Note that in this case, must hold, and must hold. We find the possible ordered pairs to be: for a total of ordered pairs.
Case 4: .
Trivially no solutions except , which matches the solution in Case 1, which makes this an overcount.
By CRT, each solution corresponds exactly one positive integer in a set of exactly consecutive positive integers, and since there are positive integers between and , our induction is complete, and our answer is .
~ fidgetboss_4000
Video Solution
https://www.youtube.com/watch?v=tgCK-H5jsOE&t=497s
See Also
2013 AMC 12B (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 |
2013 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Question | |
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.