Difference between revisions of "2014 AIME I Problems/Problem 8"
Pandabear10 (talk | contribs) |
m |
||
Line 3: | Line 3: | ||
− | ==Solution ( | + | ==Solution 1 (similar to Solution 3)== |
We have that <math>N^2 - N = N(N - 1)\equiv 0\mod{10000}</math> | We have that <math>N^2 - N = N(N - 1)\equiv 0\mod{10000}</math> | ||
Line 9: | Line 9: | ||
Thus, <math>N(N-1)</math> must be divisible by both <math>5^4</math> and <math>2^4</math>. Note, however, that if either <math>N</math> or <math>N-1</math> has both a 5 and a 2 in its factorization, the other must end in either 1 or 9, which is impossible for a number that is divisible by either 2 or 5. Thus, one of them is divisible by <math>2^4 = 16</math>, and the other is divisible by <math>5^4 = 625</math>. Noting that <math>625 \equiv 1\mod{16}</math>, we see that 625 would work for <math>N</math>, except the thousands digit is 0. The other possibility is that <math>N</math> is a multiple of 16 and <math>N-1</math> is a multiple of 625. In order for this to happen, <math>N-1</math> must be congruent to -1 (mod 16). Since <math>625 \equiv 1 \mod{16}</math>, we know that <math>15*625 = 9375 \equiv 15 \equiv -1 \mod{16}</math>. Thus, <math>N-1 = 9375</math>, so <math>N = 9376</math>, and our answer is <math>\boxed{937}</math>. | Thus, <math>N(N-1)</math> must be divisible by both <math>5^4</math> and <math>2^4</math>. Note, however, that if either <math>N</math> or <math>N-1</math> has both a 5 and a 2 in its factorization, the other must end in either 1 or 9, which is impossible for a number that is divisible by either 2 or 5. Thus, one of them is divisible by <math>2^4 = 16</math>, and the other is divisible by <math>5^4 = 625</math>. Noting that <math>625 \equiv 1\mod{16}</math>, we see that 625 would work for <math>N</math>, except the thousands digit is 0. The other possibility is that <math>N</math> is a multiple of 16 and <math>N-1</math> is a multiple of 625. In order for this to happen, <math>N-1</math> must be congruent to -1 (mod 16). Since <math>625 \equiv 1 \mod{16}</math>, we know that <math>15*625 = 9375 \equiv 15 \equiv -1 \mod{16}</math>. Thus, <math>N-1 = 9375</math>, so <math>N = 9376</math>, and our answer is <math>\boxed{937}</math>. | ||
− | == Solution (bashing)== | + | == Solution 2 (bashing)== |
let <math>N= 10000t+1000a+100b+10c+d</math> for positive integer values t,a,b,c,d | let <math>N= 10000t+1000a+100b+10c+d</math> for positive integer values t,a,b,c,d | ||
when we square N we get that <math>N^2=(10000t+1000a+100b+10c+d)^2=10^8t^2+10^6a^2+10^4b^2+10^2c^2+d^2+2(10^7ta+10^6tb+10^5tc+10^4td+10^5ab+10^4ac+10^3bc+10^ad+10^2bd+10cd)</math> | when we square N we get that <math>N^2=(10000t+1000a+100b+10c+d)^2=10^8t^2+10^6a^2+10^4b^2+10^2c^2+d^2+2(10^7ta+10^6tb+10^5tc+10^4td+10^5ab+10^4ac+10^3bc+10^ad+10^2bd+10cd)</math> | ||
Line 15: | Line 15: | ||
However we dont have to deal with this whole expression but only with its last 4 digits so it is suffices to consider only: | However we dont have to deal with this whole expression but only with its last 4 digits so it is suffices to consider only: | ||
<math>2000ad+2000bc+100c^2+200bd+20cd+d^2</math> | <math>2000ad+2000bc+100c^2+200bd+20cd+d^2</math> | ||
− | now we need to compare each decimal digit with <math>1000a+100b+10c+d</math> and see whether the digits are | + | now we need to compare each decimal digit with <math>1000a+100b+10c+d</math> and see whether the digits are congruent in base 10. |
we first consider the ones digits: | we first consider the ones digits: | ||
Line 97: | Line 97: | ||
and <math>abc</math> is equal to <math>937</math> | and <math>abc</math> is equal to <math>937</math> | ||
− | == Solution ( | + | == Solution 3 (general) == |
By the Chinese Remainder Theorem, the equation <math>N(N-1)\equiv 0\pmod{10000}</math> is equivalent to the two equations: | By the Chinese Remainder Theorem, the equation <math>N(N-1)\equiv 0\pmod{10000}</math> is equivalent to the two equations: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
Line 109: | Line 109: | ||
The four candidate digit strings <math>abcd</math> are then <math>0000,0001,0625,9376</math>. Of those, only <math>9376</math> has nonzero first digit, and therefore the answer is <math>\boxed{937}</math>. | The four candidate digit strings <math>abcd</math> are then <math>0000,0001,0625,9376</math>. Of those, only <math>9376</math> has nonzero first digit, and therefore the answer is <math>\boxed{937}</math>. | ||
− | == Solution (semi-bashing) == | + | == Solution 4 (semi-bashing) == |
*Note - <math>\overline{abcd}</math> means the number formed when the digits represented by <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> are substituted in. <math>\overline{abcd}\ne a\times b\times c\times d</math>. | *Note - <math>\overline{abcd}</math> means the number formed when the digits represented by <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> are substituted in. <math>\overline{abcd}\ne a\times b\times c\times d</math>. |
Revision as of 18:38, 11 March 2018
Contents
Problem 8
The positive integers and both end in the same sequence of four digits when written in base 10, where digit a is not zero. Find the three-digit number .
Solution 1 (similar to Solution 3)
We have that
Thus, must be divisible by both and . Note, however, that if either or has both a 5 and a 2 in its factorization, the other must end in either 1 or 9, which is impossible for a number that is divisible by either 2 or 5. Thus, one of them is divisible by , and the other is divisible by . Noting that , we see that 625 would work for , except the thousands digit is 0. The other possibility is that is a multiple of 16 and is a multiple of 625. In order for this to happen, must be congruent to -1 (mod 16). Since , we know that . Thus, , so , and our answer is .
Solution 2 (bashing)
let for positive integer values t,a,b,c,d when we square N we get that
However we dont have to deal with this whole expression but only with its last 4 digits so it is suffices to consider only: now we need to compare each decimal digit with and see whether the digits are congruent in base 10. we first consider the ones digits:
this can happen for only 3 values : 1, 5 and 6
we can try to solve each case
- Case 1
considering the tenths place we have that:
so
considering the hundreds place we have that
so again
now considering the thousands place we have that
so we get but cannot be equal to 0 so we consider
- Case 2
considering the tenths place we have that:
( the extra 20 is carried from which is equal to 25) so
considering the hundreds place we have that
( the extra 100c is carried from the tenths place) so
now considering the thousands place we have that
( the extra 1000b is carried from the hundreds place) so a is equal 0 again
- Case 3
considering the tenths place we have that:
( the extra 20 is carried from which is equal to 25) if then we have
so
considering the hundreds place we have that
( the extra 100c+100 is carried from the tenths place)
if then we have
so
now considering the thousands place we have that
( the extra 1000b+6000 is carried from the hundreds place)
if then we have
so
so we have that the last 4 digits of N are and is equal to
Solution 3 (general)
By the Chinese Remainder Theorem, the equation is equivalent to the two equations: Since and are coprime, the only solutions are when .
Let , . The statement of the Chinese Remainder theorem is that is an isomorphism between the two rings. In this language, the solutions are , , , and . Now we easily see that and . Noting that , it follows that . To compute , note that in , so since is linear in its arguments (by virtue of being an isomorphism), .
The four candidate digit strings are then . Of those, only has nonzero first digit, and therefore the answer is .
Solution 4 (semi-bashing)
- Note - means the number formed when the digits represented by , , , and are substituted in. .
WLOG, we can assume that is a 4-digit integer . Note that the only that will satisfy will also satisfy , as the units digit of is affected only by , regardless of , , or .
By checking the numbers 0-9, we see that the only possible values of are .
Now, we seek to find . Note that the only that will satisfy will also satisfy , by the same reasoning as above - the last two digits of are only affected by and . As we already have narrowed choices for , we start reasoning out.
First, we note that if , then , as a number ending in 0, and therefore divisible by 10, is squared, the result is divisible by 100, meaning it ends in two 0's. However, if ends in , then recursively, and must be , as a number divisible by 100 squared ends in four zeros. As cannot be 0, we throw out this possibility, as the only solution in this case is .
Now, let's assume that . is equal to . Squaring this gives , and when modulo 100 is taken, it must equal . As is an integer, must be divisible by 100, so , which must be equivalent to . Note that this is really and , and comparing the 10's digits. So really, we're just looking for when the units digit of and are equal, and a quick check reveals that this is only true when .However, if we extend this process to find and , we'd find that they are also 0. The only solution in this case is , and since here, this is not our solution. Therefore, there are no valid solutions in this case.
Let's assume that . Note that , and when modulo 100 is taken, 25 is the remainder. So all cases here have squares that end in 25, so is our only case here. A quick check reveals that , which works for now.
Now, let . Note that . Taking modulo 100, this reduces to , which must be equivalent to . Again, this is similar to and , so we see when the units digits of and are equal. To make checking faster, note that is necessarily even, so is necessarily odd, so must be odd. Checking all the odds reveals that only works, so this case gives . Checking quickly , which works for now.
Now, we find , given two possibilities for .
Start with . Note that if we square this, we get , which should be equivalent to modulo 1000. Note that, since is an integer, simplifies modulo 1000 to . Therefore, the only that works here is . .
Now, assume that . We have , and when squared, becomes , which, modulo 1000, should be equivalent to . Reducing modulo 1000 gives . Using the same technique as before, we must equate the hundreds digit of to , or equate the units digit of and . Since is necessarily odd, any possible 's must be odd. A quick check reveals that is the only solution, so we get a solution of . .
Finally, we solve for . Start with . We have , which, squared, gives , and reducing modulo 10000 gives simply 625. So . However, that makes . Therefore, no solutions exist in this case.
We turn to our last case, . We have , and reducing modulo 10000 gives , which must be equivalent to . So we must have being equivalent to modulo 1000. So, the units digit of must be equal to . Since is odd, must be odd. Lo and behold, the only possibility for is . Therefore, , so our answer is .
See also
2014 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.