Difference between revisions of "2014 AIME I Problems/Problem 8"
(→Solution 5 (easy observations)) |
(→Solution 4 (semi-bashing)) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 141: | Line 141: | ||
We turn to our last case, <math>\overline{bcd}=376</math>. We have <cmath>1000a + 376^2 = 1000000a^2 + 752000a + 141376,</cmath> and reducing modulo <math>10000</math> gives <math>2000a + 1376</math>, which must be equivalent to <math>1000a + 376</math>. So we must have <math>\overline{(2a+1)376}</math> being equivalent to <math>\overline{a376}</math> modulo 1000. So, the units digit of <math>2a+1</math> must be equal to <math>a</math>. Since <math>2a+1</math> is odd, <math>a</math> must be odd. Lo and behold, the only possibility for <math>a</math> is <math>a=3</math>. Therefore, <math>\overline{abcd}=9376</math>, so our answer is <math>\boxed{937}</math>. | We turn to our last case, <math>\overline{bcd}=376</math>. We have <cmath>1000a + 376^2 = 1000000a^2 + 752000a + 141376,</cmath> and reducing modulo <math>10000</math> gives <math>2000a + 1376</math>, which must be equivalent to <math>1000a + 376</math>. So we must have <math>\overline{(2a+1)376}</math> being equivalent to <math>\overline{a376}</math> modulo 1000. So, the units digit of <math>2a+1</math> must be equal to <math>a</math>. Since <math>2a+1</math> is odd, <math>a</math> must be odd. Lo and behold, the only possibility for <math>a</math> is <math>a=3</math>. Therefore, <math>\overline{abcd}=9376</math>, so our answer is <math>\boxed{937}</math>. | ||
+ | ==Solution 5 (easy observations)== | ||
− | |||
− | |||
− | |||
We are given that <math>abcd^2</math> ends in <math>abcd</math>, which means that <math>d^2</math> ends in <math>d</math>. The only possible values for which this works is <math>d=0,1,5,6</math>. Notice that if we set <math>d=0</math>, we will have <math>c=0, b=0, a=0</math>, which is not valid since <math>a\neq0</math>. Furthermore, we can see that | We are given that <math>abcd^2</math> ends in <math>abcd</math>, which means that <math>d^2</math> ends in <math>d</math>. The only possible values for which this works is <math>d=0,1,5,6</math>. Notice that if we set <math>d=0</math>, we will have <math>c=0, b=0, a=0</math>, which is not valid since <math>a\neq0</math>. Furthermore, we can see that | ||
+ | <math>d\neq1</math> by quickly going over <math>11^2, 12^2, ..., 19^2</math> and seeing that none of those numbers work. From number sense, we know that <math>B25^2</math> ends in <math>...625</math> regardless of <math>B</math>. So, in this case, <math>b=6</math>. However, notice that <math>76^2</math> ends in <math>...76</math>, and we can quickly find that <math>376^2=141376</math>. Going back to <math>A625^2</math>, we notice that no matter what <math>A</math> is, <math>A625^2=...0625</math>. Since <math>A\neq0</math>, this case is not valid (write out <math>A625^2</math> and multiply to see that the thousands digit is <math>5a+3+2+5+5a=10a+10</math> which always ends in <math>0</math>). We turn our focus to <math>A376^2</math>. Write out <math>376^2</math> and multiply it out to see that the thousands digit is <math>6a+2+6+2+6a+1=12a+1</math>. There is an extra <math>1</math> due to carry over. Quickly testing numbers, the only possible value for <math>A</math> is <math>9</math>. So, <math>abcd=9376</math> and our answer is <math>abc=\boxed{937}</math>. | ||
− | + | ~hwan | |
− | |||
− | |||
== Video Solution by OmegaLearn == | == Video Solution by OmegaLearn == |
Latest revision as of 20:01, 16 August 2024
Contents
Problem 8
The positive integers and
both end in the same sequence of four digits
when written in base
, where digit
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
and a
in its factorization, the other must end in either
or
, which is impossible for a number that is divisible by either
or
. Thus, one of them is divisible by
, and the other is divisible by
. Noting that
, we see that
would work for
, except the thousands digit is
. The other possibility is that
is a multiple of
and
is a multiple of
. In order for this to happen,
Since
, we know that
. Thus,
, so
, and our answer is
.
Solution 2 (bashing)
let for positive integer values
.
When we square
we get that
However, we don't 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
so we consider
- Case 2
considering the tenths place we have that:
( the extra
is carried from
which is equal to
)
so
considering the hundreds place we have that
( the extra
is carried from the tenths place)
so
now considering the thousands place we have that
( the extra
is carried from the hundreds place)
so a is equal 0 again
- Case 3
considering the tenths place we have that:
( the extra
is carried from
which is equal to
)
if
then we have
so
considering the hundreds place we have that
( the extra
is carried from the tenths place)
if then we have
so
now considering the thousands place we have that
( the extra
is carried from the hundreds place)
if then we have
so
so we have that the last 4 digits of 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
is taken,
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
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
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
.
Solution 5 (easy observations)
We are given that ends in
, which means that
ends in
. The only possible values for which this works is
. Notice that if we set
, we will have
, which is not valid since
. Furthermore, we can see that
by quickly going over
and seeing that none of those numbers work. From number sense, we know that
ends in
regardless of
. So, in this case,
. However, notice that
ends in
, and we can quickly find that
. Going back to
, we notice that no matter what
is,
. Since
, this case is not valid (write out
and multiply to see that the thousands digit is
which always ends in
). We turn our focus to
. Write out
and multiply it out to see that the thousands digit is
. There is an extra
due to carry over. Quickly testing numbers, the only possible value for
is
. So,
and our answer is
.
~hwan
Video Solution by OmegaLearn
https://youtu.be/gP5pejfcUl8?t=483
~ pi_is_3.14
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.