Difference between revisions of "2014 AIME I Problems/Problem 8"

Latest revision as of 19:01, 16 August 2024

Problem 8

The positive integers $N$ and $N^2$ both end in the same sequence of four digits $abcd$ when written in base $10$ , where digit $a$ is not zero. Find the three-digit number $abc$ .

Solution 1 (similar to Solution 3)

We have that $N^2 - N = N(N - 1)\equiv 0\mod{10000}$

Thus, $N(N-1)$ must be divisible by both $5^4$ and $2^4$ . Note, however, that if either $N$ or $N-1$ 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 $2^4 = 16$ , and the other is divisible by $5^4 = 625$ . Noting that $625 \equiv 1\mod{16}$ , we see that $625$ would work for $N$ , except the thousands digit is $0$ . The other possibility is that $N$ is a multiple of $16$ and $N-1$ is a multiple of $625$ . In order for this to happen, $N-1 \equiv -1 \pmod {16}.$ Since $625 \equiv 1 \pmod{16}$ , we know that $15 \cdot 625 = 9375 \equiv 15 \equiv -1 \mod{16}$ . Thus, $N-1 = 9375$ , so $N = 9376$ , and our answer is $\boxed{937}$ .

Solution 2 (bashing)

let $N= 10000t+1000a+100b+10c+d$ for positive integer values $t,a,b,c,d$ . When we square $N$ we get that $\begin{align*} 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) \end{align*}$

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: $2000ad+2000bc+100c^2+200bd+20cd+d^2.$ Now we need to compare each decimal digit with $1000a+100b+10c+d$ and see whether the digits are congruent in base 10. we first consider the ones digits:

$d^2\equiv d \pmod{10}.$

This can happen for only 3 values : 1, 5 and 6.

We can try to solve each case:

Case 1 $(d=1)$

Considering the tenths place, we have that:

$20cd=20c\equiv 10c \pmod {100}$ so $c= 0$ .

Considering the hundreds place we have that

$200bd+100c^2= 200b \equiv 100b \pmod{1000}$ so again $b=0$

now considering the thousands place we have that

$2000ad+2000bc = 2000a \equiv 1000a \pmod {10000}$ so we get $a=0$ but $a$ cannot be equal to $0$ so we consider $d=5.$

Case 2 $(d=5)$

considering the tenths place we have that:

$20cd+20=100c+20\equiv 20 \equiv 10c \mod {100}$ ( the extra $20$ is carried from $d^2$ which is equal to $25$ ) so $c=2$

considering the hundreds place we have that

$200bd+100c^2+100c= 1000b+600 \equiv600\equiv 100b \pmod{1000}$ ( the extra $100c$ is carried from the tenths place) so $b=6$

now considering the thousands place we have that

$2000ad+2000bc +1000b= 10000a+24000+ 6000\equiv0\equiv 1000a \pmod {10000}$ ( the extra $1000b$ is carried from the hundreds place) so a is equal 0 again

Case 3 $(d=6)$

considering the tenths place we have that:

$20cd+30=120c+30\equiv 30+20c \equiv 10c \pmod {100}$ ( the extra $20$ is carried from $d^2$ which is equal to $25$ ) if $c=7$ then we have

$30+20 \cdot 7 \equiv 70\equiv7 \cdot 10 \pmod{100}$

so $c=7$

considering the hundreds place we have that

$200bd+100c^2+100c+100= 1200b+4900+800 \equiv200b+700\equiv 100b \pmod{1000}$ ( the extra $100c+100$ is carried from the tenths place)

if $b=3$ then we have

$700+200 \cdot 3 \equiv 300\equiv3 \cdot 100 \pmod {1000}$

so $b=3$

now considering the thousands place we have that

$2000ad+2000bc +1000b+5000+1000= 12000a+42000+ 3000+6000\equiv0\equiv 2000a+1000\equiv 1000a \pmod {10000}$ ( the extra $1000b+6000$ is carried from the hundreds place)

if $a=9$ then we have

$2000 \cdot 9+1000 \equiv 9000\equiv9 \cdot 1000 \pmod {1000}$

so $a=9$

so we have that the last 4 digits of $N$ are $9376$ and $abc$ is equal to $\boxed{937}$

Solution 3 (general)

By the Chinese Remainder Theorem, the equation $N(N-1)\equiv 0\pmod{10000}$ is equivalent to the two equations: $\begin{align*} N(N-1)&\equiv 0\pmod{16},\\ N(N-1)&\equiv 0\pmod{625}. \end{align*}$ Since $N$ and $N-1$ are coprime, the only solutions are when $(N\mod{16},N\mod{625})\in\{(0,0),(0,1),(1,0),(1,1)\}$ .

Let $\varphi:\mathbb Z/10000\mathbb Z\to\mathbb Z/16\mathbb Z\times\mathbb Z/625\mathbb Z,$ $x\mapsto (x\mod{16},x\mod{625}).$ The statement of the Chinese Remainder theorem is that $\varphi$ is an isomorphism between the two rings. In this language, the solutions are $\varphi^{-1}(0,0)$ , $\varphi^{-1}(0,1)$ , $\varphi^{-1}(1,0)$ , and $\varphi^{-1}(1,1)$ . Now we easily see that $\varphi^{-1}(0,0)=0$ and $\varphi^{-1}(1,1)=1.$ Noting that $625\equiv 1\pmod{16}$ , it follows that $\varphi^{-1}(1,0)=625.$ To compute $\varphi^{-1}(0,1)$ , note that $(0,1)=15(1,0)+(1,1)$ in $\mathbb Z/16\mathbb Z\times\mathbb Z/625\mathbb Z,$ so since $\varphi^{-1}$ is linear in its arguments (by virtue of being an isomorphism), $\varphi^{-1}(0,1)=15\varphi^{-1}(1,0)+\varphi^{-1}(1,1)=15\times 625+1=9376.$

The four candidate digit strings $abcd$ are then $0000,0001,0625,9376$ . Of those, only $9376$ has nonzero first digit, and therefore the answer is $\boxed{937}$ .

Solution 4 (semi-bashing)

Note - $\overline{abcd}$ means the number formed when the digits represented by $a$ , $b$ , $c$ , and $d$ are substituted in. $\overline{abcd}\ne a\times b\times c\times d$ .

WLOG, we can assume that $N$ is a 4-digit integer $\overline{abcd}$ . Note that the only $d$ that will satisfy $N$ will also satisfy $d^2\equiv d\pmod{10}$ , as the units digit of $\overline{abcd}^2$ is affected only by $d$ , regardless of $a$ , $b$ , or $c$ .

By checking the numbers 0-9, we see that the only possible values of $d$ are $d=0, 1, 5, 6$ .

Now, we seek to find $c$ . Note that the only $\overline{cd}$ that will satisfy $N$ will also satisfy $\overline{cd}^2 \equiv \overline{cd}\pmod{100}$ , by the same reasoning as above - the last two digits of $\overline{abcd}^2$ are only affected by $c$ and $d$ . As we already have narrowed choices for $d$ , we start reasoning out.

First, we note that if $d=0$ , then $c=0$ , 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 $N$ ends in $00$ , then recursively, $a$ and $b$ must be $0$ , as a number divisible by 100 squared ends in four zeros. As $a$ cannot be 0, we throw out this possibility, as the only solution in this case is $0$ .

Now, let's assume that $d=1$ . $\overline{cd}$ is equal to $10c + d = 10c + 1$ . Squaring this gives $100c^2 + 20c + 1$ , and when modulo 100 is taken, it must equal $10c + 1$ . As $c$ is an integer, $100c^2$ must be divisible by 100, so $100c^2+20c+1 \equiv 20c + 1\pmod{100}$ , which must be equivalent to $10c + 1$ . Note that this is really $\overline{(2c)1}$ and $\overline{c1}$ , and comparing the 10's digits. So really, we're just looking for when the units digit of $2c$ and $c$ are equal, and a quick check reveals that this is only true when $c=0$ .However, if we extend this process to find $b$ and $a$ , we'd find that they are also 0. The only solution in this case is $1$ , and since $a=0$ here, this is not our solution. Therefore, there are no valid solutions in this case.

Let's assume that $d=5$ . Note that $(10c + 5)^2 = 100c^2 + 100c + 25$ , and when modulo $100$ is taken, $25$ is the remainder. So all cases here have squares that end in 25, so $\overline{cd}=25$ is our only case here. A quick check reveals that $25^2=625$ , which works for now.

Now, let $d=6$ . Note that $(10c + 6)^2 = 100c^2 + 120c + 36$ . Taking modulo 100, this reduces to $20c+36$ , which must be equivalent to $10c+6$ . Again, this is similar to $\overline{(2c+3)6}$ and $\overline{c6}$ , so we see when the units digits of $2c+3$ and $c$ are equal. To make checking faster, note that $2c$ is necessarily even, so $2c+3$ is necessarily odd, so $c$ must be odd. Checking all the odds reveals that only $c=3$ works, so this case gives $76$ . Checking quickly $76^2 = 5776$ , which works for now.

Now, we find $b$ , given two possibilities for $\overline{cd}$ .

Start with $\overline{cd} = 25$ . $\overline{bcd} = 100b + \overline{cd} = 100b + 25.$ Note that if we square this, we get $10000b^2 + 5000b + 625$ , which should be equivalent to $100b + 25$ modulo 1000. Note that, since $b$ is an integer, $10000b^2 + 5000 + 625$ simplifies modulo 1000 to $625$ . Therefore, the only $\overline{bcd}$ that works here is $625$ . $625^2 = 390625$ .

Now, assume that $\overline{cd}=76$ . We have $100b + 76$ , and when squared, becomes $10000b^2 + 15200b + 5776$ , which, modulo 1000, should be equivalent to $100b+76$ . Reducing $10000b^2 + 15200b + 5776$ modulo $1000$ gives $200b + 776$ . Using the same technique as before, we must equate the hundreds digit of $\overline{(2b+7)76}$ to $\overline{b76}$ , or equate the units digit of $2b+7$ and $b$ . Since $2b+7$ is necessarily odd, any possible $b$ 's must be odd. A quick check reveals that $b=3$ is the only solution, so we get a solution of $376$ . $376^2 = 141376$ .

Finally, we solve for $a$ . Start with $\overline{bcd}=625$ . We have $1000a + 625$ , which, squared, gives $1000000a^2 + 1250000a + 390625,$ and reducing modulo 10000 gives simply 625. So $\overline{abcd}=625$ . However, that makes $a=0$ . Therefore, no solutions exist in this case.

We turn to our last case, $\overline{bcd}=376$ . We have $1000a + 376^2 = 1000000a^2 + 752000a + 141376,$ and reducing modulo $10000$ gives $2000a + 1376$ , which must be equivalent to $1000a + 376$ . So we must have $\overline{(2a+1)376}$ being equivalent to $\overline{a376}$ modulo 1000. So, the units digit of $2a+1$ must be equal to $a$ . Since $2a+1$ is odd, $a$ must be odd. Lo and behold, the only possibility for $a$ is $a=3$ . Therefore, $\overline{abcd}=9376$ , so our answer is $\boxed{937}$ .

Solution 5 (easy observations)

We are given that $abcd^2$ ends in $abcd$ , which means that $d^2$ ends in $d$ . The only possible values for which this works is $d=0,1,5,6$ . Notice that if we set $d=0$ , we will have $c=0, b=0, a=0$ , which is not valid since $a\neq0$ . Furthermore, we can see that $d\neq1$ by quickly going over $11^2, 12^2, ..., 19^2$ and seeing that none of those numbers work. From number sense, we know that $B25^2$ ends in $...625$ regardless of $B$ . So, in this case, $b=6$ . However, notice that $76^2$ ends in $...76$ , and we can quickly find that $376^2=141376$ . Going back to $A625^2$ , we notice that no matter what $A$ is, $A625^2=...0625$ . Since $A\neq0$ , this case is not valid (write out $A625^2$ and multiply to see that the thousands digit is $5a+3+2+5+5a=10a+10$ which always ends in $0$ ). We turn our focus to $A376^2$ . Write out $376^2$ and multiply it out to see that the thousands digit is $6a+2+6+2+6a+1=12a+1$ . There is an extra $1$ due to carry over. Quickly testing numbers, the only possible value for $A$ is $9$ . So, $abcd=9376$ and our answer is $abc=\boxed{937}$ .

~hwan

Video Solution by OmegaLearn

https://youtu.be/gP5pejfcUl8?t=483

~ pi_is_3.14

@@ Line 1: / Line 1: @@
 == Problem 8 ==
-The positive integers <math>N</math> and <math>N^2</math> both end in the same sequence of four digits <math>abcd</math> when written in base 10, where digit a is not zero. Find the three-digit number <math>abc</math>.
+The positive integers <math>N</math> and <math>N^2</math> both end in the same sequence of four digits <math>abcd</math> when written in base <math>10</math>, where digit <math>a</math> is not zero. Find the three-digit number <math>abc</math>.
+==Solution 1 (similar to Solution 3)==
-== Solution (bashing)==
+We have that <math>N^2 - N = N(N - 1)\equiv 0\mod{10000}</math>
-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>
-However we dont have to deal with this whole expression but only with its last 4 digits so it is suffices to consider only:
+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 <math>5</math> and a <math>2</math> in its factorization, the other must end in either <math>1</math> or <math>9</math>, which is impossible for a number that is divisible by either <math>2</math> or <math>5</math>. 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 <math>625</math> would work for <math>N</math>, except the thousands digit is <math>0</math>. The other possibility is that <math>N</math> is a multiple of <math>16</math> and <math>N-1</math> is a multiple of <math>625</math>. In order for this to happen, <cmath>N-1 \equiv -1 \pmod {16}.</cmath> Since <math>625 \equiv 1 \pmod{16}</math>, we know that <math>15 \cdot 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>.
-<math>2000ad+2000bc+100c^2+200bd+20cd+d^2</math>
-know we need to compare each decimal digit with <math>1000a+100b+10c+d</math> and see whether the digits are congrount in base 10.
+== Solution 2 (bashing)==
+let <math>N= 10000t+1000a+100b+10c+d</math> for positive integer values <math>t,a,b,c,d</math>.
+When we square <math>N</math> we get that
+<cmath>\begin{align*}
+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)
+\end{align*}</cmath>
+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:
+<cmath>2000ad+2000bc+100c^2+200bd+20cd+d^2.</cmath>
+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:
-<math>d^2\equiv (mod  10)</math>
+<math>d^2\equiv d \pmod{10}.</math>
+This can happen for only 3 values : 1, 5 and 6.
-this can happen for only 3 values : 1, 5 and 6
+We can try to solve each case:
-we can try to solve each case
 *Case 1 <math>(d=1)</math>
-considering the tenths place
+Considering the tenths place,
 we have that:
-<math>20cd=20c\equiv 10c (mod  100)</math>
+<math>20cd=20c\equiv 10c \pmod {100}</math>
-so <math>c= 0</math>
+so <math>c= 0</math>.
-considering the hundreds place we have that
+Considering the hundreds place we have that
-<math>200bd+100c^2= 200b \equiv 100b (mod1000)</math>
+<math>200bd+100c^2= 200b \equiv 100b \pmod{1000}</math>
 so again <math>b=0</math>
 now considering the thousands place we have that
-<math>2000ad+2000bc = 2000a \equiv 1000a (mod 10000)</math>
+<math>2000ad+2000bc = 2000a \equiv 1000a \pmod {10000}</math>
-so we get <math>a=0</math> but <math>a</math> cannot be equal to 0 so we consider <math>d=5</math>
+so we get <math>a=0</math> but <math>a</math> cannot be equal to <math>0</math> so we consider <math>d=5.</math>
 *Case 2 <math>(d=5)</math>
@@ Line 38: / Line 48: @@
 we have that:
-<math>20cd+20=100c+20\equiv 20 \equiv 10c (mod  100)</math>
+<math>20cd+20=100c+20\equiv 20 \equiv 10c \mod  {100}</math>
-( the extra 20 is carried from <math>d^2</math> which is equal to 25)
+( the extra <math>20</math> is carried from <math>d^2</math> which is equal to <math>25</math>)
 so <math>c=2</math>
 considering the hundreds place we have that
-<math>200bd+100c^2+100c= 1000b+600 \equiv600\equiv 100b (mod1000)</math>
+<math>200bd+100c^2+100c= 1000b+600 \equiv600\equiv 100b \pmod{1000}</math>
-( the extra 100c is carried from the tenths place)
+( the extra <math>100c</math> is carried from the tenths place)
-so<math> b=6</math>
+so <math>b=6</math>
 now considering the thousands place we have that
-<math>2000ad+2000bc +1000b= 10000a+24000+ 6000\equiv0\equiv 1000a (mod 10000)</math>
+<math>2000ad+2000bc +1000b= 10000a+24000+ 6000\equiv0\equiv 1000a \pmod {10000}</math>
-( the extra 1000b is carried from the hundreds place)
+( the extra <math>1000b</math> is carried from the hundreds place)
 so a is equal 0 again
@@ Line 58: / Line 68: @@
 we have that:
-<math>20cd+30=120c+30\equiv 30+20c \equiv 10c (mod  100)</math>
+<math>20cd+30=120c+30\equiv 30+20c \equiv 10c \pmod {100}</math>
-( the extra 20 is carried from <math>d^2</math> which is equal to 25)
+( the extra <math>20</math> is carried from <math>d^2</math> which is equal to <math>25</math>)
 if <math>c=7</math> then we have
-<math>30+20*7 \equiv 70\equiv7*10(mod100)</math>
+<math>30+20 \cdot 7 \equiv 70\equiv7 \cdot 10 \pmod{100}</math>
 so <math>c=7</math>
@@ Line 68: / Line 78: @@
 considering the hundreds place we have that
-<math>200bd+100c^2+100c+100= 1200b+4900+700 \equiv200b+700\equiv 100b (mod1000)</math>
+<math>200bd+100c^2+100c+100= 1200b+4900+800 \equiv200b+700\equiv 100b \pmod{1000}</math>
-( the extra 100c+100 is carried from the tenths place)
+( the extra <math>100c+100</math> is carried from the tenths place)
 if <math>b=3</math> then we have
-<math>700+200*3 \equiv 300\equiv3*100 (mod 1000)</math>
+<math>700+200 \cdot 3 \equiv 300\equiv3 \cdot 100 \pmod {1000}</math>
 so <math>b=3</math>
@@ Line 79: / Line 89: @@
 now considering the thousands place we have that
-<math>2000ad+2000bc +1000b+5000+1000= 12000a+42000+ 3000+6000\equiv0\equiv 2000a+1000\equiv 1000a (mod 10000)</math>
+<math>2000ad+2000bc +1000b+5000+1000= 12000a+42000+ 3000+6000\equiv0\equiv 2000a+1000\equiv 1000a \pmod {10000}</math>
-( the extra 1000b+6000 is carried from the hundreds place)
+( the extra <math>1000b+6000</math> is carried from the hundreds place)
 if <math>a=9</math> then we have
-<math>2000*9+1000 \equiv 9000\equiv9*1000 (mod 1000)</math>
+<math>2000 \cdot 9+1000 \equiv 9000\equiv9 \cdot 1000 \pmod {1000}</math>
 so <math>a=9</math>
-so we have that the last 4 digits of N are <math>9376</math>
+so we have that the last 4 digits of <math>N</math> are <math>9376</math>
-and  <math>abc</math> is equal to <math>937</math>
+and  <math>abc</math> is equal to <math>\boxed{937}</math>
-== Solution (not bashing) ==
+== 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:
 <cmath>\begin{align*}
@@ Line 99: / Line 109: @@
 Since <math>N</math> and <math>N-1</math> are coprime, the only solutions are when <math>(N\mod{16},N\mod{625})\in\{(0,0),(0,1),(1,0),(1,1)\}</math>.
-Let <math>\varphi:\mathbb Z/10000\mathbb Z\to\mathbb Z/16\mathbb Z\times\mathbb Z/625\mathbb Z</math>, <math>x\mapsto (x\mod{16},x\mod{625})</math>. The statement of the Chinese Remainder theorem is that <math>\varphi</math> is an isomorphism between the two rings. In this language, the solutions are <math>\phi^{-1}(0,0)</math>, <math>\phi^{-1}(0,1)</math>, <math>\phi^{-1}(1,0)</math>, and <math>\phi^{-1}(1,1)</math>. Now we easily see that <math>\phi^{-1}(0,0)=0</math> and <math>\phi^{-1}(1,1)=1</math>. Noting that <math>625\equiv 1\pmod{16}</math>, it follows that <math>\phi^{-1}(1,0)=625</math>. To compute <math>\phi^{-1}(0,1)</math>, note that <math>(0,1)=15(1,0)+(1,1)</math> in <math>\mathbb \mathbb Z/16\mathbb Z\times\mathbb Z/625\mathbb Z</math>, so since <math>\phi</math> is linear in its arguments (by virtue of being an isomorphism), <math>\phi^{-1}(0,1)=15\phi^{-1}(1,0)+\phi^{-1}(1,1)=15\times 625+1=9376</math>.
+Let <cmath>\varphi:\mathbb Z/10000\mathbb Z\to\mathbb Z/16\mathbb Z\times\mathbb Z/625\mathbb Z,</cmath> <cmath>x\mapsto (x\mod{16},x\mod{625}).</cmath> The statement of the Chinese Remainder theorem is that <math>\varphi</math> is an isomorphism between the two rings. In this language, the solutions are <math>\varphi^{-1}(0,0)</math>, <math>\varphi^{-1}(0,1)</math>, <math>\varphi^{-1}(1,0)</math>, and <math>\varphi^{-1}(1,1)</math>. Now we easily see that <cmath>\varphi^{-1}(0,0)=0</cmath> and <cmath>\varphi^{-1}(1,1)=1.</cmath> Noting that <math>625\equiv 1\pmod{16}</math>, it follows that <cmath>\varphi^{-1}(1,0)=625.</cmath> To compute <math>\varphi^{-1}(0,1)</math>, note that <cmath>(0,1)=15(1,0)+(1,1)</cmath> in <cmath>\mathbb Z/16\mathbb Z\times\mathbb Z/625\mathbb Z,</cmath> so since <math>\varphi^{-1}</math> is linear in its arguments (by virtue of being an isomorphism), <cmath>\varphi^{-1}(0,1)=15\varphi^{-1}(1,0)+\varphi^{-1}(1,1)=15\times 625+1=9376.</cmath>
 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 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>.
+WLOG, we can assume that <math>N</math> is a 4-digit integer <math>\overline{abcd}</math>. Note that the only <math>d</math> that will satisfy <math>N</math> will also satisfy <math>d^2\equiv d\pmod{10}</math>, as the units digit of <math>\overline{abcd}^2</math> is affected only by <math>d</math>, regardless of <math>a</math>, <math>b</math>, or <math>c</math>.
+By checking the numbers 0-9, we see that the only possible values of <math>d</math> are <math>d=0, 1, 5, 6</math>.
+Now, we seek to find <math>c</math>. Note that the only <math>\overline{cd}</math> that will satisfy <math>N</math> will also satisfy <math>\overline{cd}^2 \equiv \overline{cd}\pmod{100}</math>, by the same reasoning as above - the last two digits of <math>\overline{abcd}^2</math> are only affected by <math>c</math> and <math>d</math>. As we already have narrowed choices for <math>d</math>, we start reasoning out.
+First, we note that if <math>d=0</math>, then <math>c=0</math>, 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 <math>N</math> ends in <math>00</math>, then recursively, <math>a</math> and <math>b</math> must be <math>0</math>, as a number divisible by 100 squared ends in four zeros. As <math>a</math> cannot be 0, we throw out this possibility, as the only solution in this case is <math>0</math>.
+Now, let's assume that <math>d=1</math>. <math>\overline{cd}</math> is equal to <math>10c + d = 10c + 1</math>. Squaring this gives <math>100c^2 + 20c + 1</math>, and when modulo 100 is taken, it must equal <math>10c + 1</math>. As <math>c</math> is an integer, <math>100c^2</math> must be divisible by 100, so <math>100c^2+20c+1 \equiv 20c + 1\pmod{100}</math>, which must be equivalent to <math>10c + 1</math>. Note that this is really <math>\overline{(2c)1}</math> and <math>\overline{c1}</math>, and comparing the 10's digits. So really, we're just looking for when the units digit of <math>2c</math> and <math>c</math> are equal, and a quick check reveals that this is only true when <math>c=0</math>.However, if we extend this process to find <math>b</math> and <math>a</math>, we'd find that they are also 0. The only solution in this case is <math>1</math>, and since <math>a=0</math> here, this is not our solution. Therefore, there are no valid solutions in this case.
+Let's assume that <math>d=5</math>. Note that <math>(10c + 5)^2 = 100c^2 + 100c + 25</math>, and when modulo <math>100</math> is taken, <math>25</math> is the remainder. So all cases here have squares that end in 25, so <math>\overline{cd}=25</math> is our only case here. A quick check reveals that <math>25^2=625</math>, which works for now.
+Now, let <math>d=6</math>. Note that <math>(10c + 6)^2 = 100c^2 + 120c + 36</math>. Taking modulo 100, this reduces to <math>20c+36</math>, which must be equivalent to <math>10c+6</math>. Again, this is similar to <math>\overline{(2c+3)6}</math> and <math>\overline{c6}</math>, so we see when the units digits of <math>2c+3</math> and <math>c</math> are equal. To make checking faster, note that <math>2c</math> is necessarily even, so <math>2c+3</math> is necessarily odd, so <math>c</math> must be odd. Checking all the odds reveals that only <math>c=3</math> works, so this case gives <math>76</math>. Checking quickly <math>76^2 = 5776</math>, which works for now.
+Now, we find <math>b</math>, given two possibilities for <math>\overline{cd}</math>.
+Start with <math>\overline{cd} = 25</math>. <math>\overline{bcd} = 100b + \overline{cd} = 100b + 25.</math> Note that if we square this, we get <math>10000b^2 + 5000b + 625</math>, which should be equivalent to <math>100b + 25</math> modulo 1000. Note that, since <math>b</math> is an integer, <math>10000b^2 + 5000 + 625</math> simplifies modulo 1000 to <math>625</math>. Therefore, the only <math>\overline{bcd}</math> that works here is <math>625</math>. <math>625^2 = 390625</math>.
+Now, assume that <math>\overline{cd}=76</math>. We have <math>100b + 76</math>, and when squared, becomes <math>10000b^2 + 15200b + 5776</math>, which, modulo 1000, should be equivalent to <math>100b+76</math>. Reducing <math>10000b^2 + 15200b + 5776</math> modulo <math>1000</math> gives <math>200b + 776</math>. Using the same technique as before, we must equate the hundreds digit of <math>\overline{(2b+7)76}</math> to <math>\overline{b76}</math>, or equate the units digit of <math>2b+7</math> and <math>b</math>. Since <math>2b+7</math> is necessarily odd, any possible <math>b</math>'s must be odd. A quick check reveals that <math>b=3</math> is the only solution, so we get a solution of <math>376</math>. <math>376^2 = 141376</math>.
+Finally, we solve for <math>a</math>. Start with <math>\overline{bcd}=625</math>. We have <math>1000a + 625</math>, which, squared, gives <cmath>1000000a^2 + 1250000a + 390625,</cmath> and reducing modulo 10000 gives simply 625. So <math>\overline{abcd}=625</math>. However, that makes <math>a=0</math>. Therefore, no solutions exist in this case.
+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
+<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 ==
+https://youtu.be/gP5pejfcUl8?t=483
+~ pi_is_3.14
+== See also ==
+{{AIME box|year=2014|n=I|num-b=7|num-a=9}}
+[[Category:Intermediate Number Theory Problems]]
+{{MAA Notice}}

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

Page

Toolbox

Search

Difference between revisions of "2014 AIME I Problems/Problem 8"

Latest revision as of 19:01, 16 August 2024

Contents

Problem 8

Solution 1 (similar to Solution 3)

Solution 2 (bashing)

Solution 3 (general)

Solution 4 (semi-bashing)

Solution 5 (easy observations)

Video Solution by OmegaLearn

See also