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

Revision as of 17:24, 14 March 2014

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 (bashing)

let $N= 10000t+1000a+100b+10c+d$ for positive integer values t,a,b,c,d when we square N we get that $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)$

However we dont 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$ know we need to compare each decimal digit with $1000a+100b+10c+d$ and see whether the digits are congrount in base 10. we first consider the ones digits:

$d^2\equiv (mod 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 (mod 100)$ so $c= 0$

considering the hundreds place we have that

$200bd+100c^2= 200b \equiv 100b (mod1000)$ so again $b=0$

now considering the thousands place we have that

$2000ad+2000bc = 2000a \equiv 1000a (mod 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 (mod1000)$ ( 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 (mod 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 (mod 100)$ ( the extra 20 is carried from $d^2$ which is equal to 25) if $c=7$ then we have

$30+20*7 \equiv 70\equiv7*10(mod100)$

so $c=7$

considering the hundreds place we have that

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

if $b=3$ then we have

$700+200*3 \equiv 300\equiv3*100 (mod 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 (mod 10000)$ ( the extra 1000b+6000 is carried from the hundreds place)

if $a=9$ then we have

$2000*9+1000 \equiv 9000\equiv9*1000 (mod 1000)$

so $a=9$

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

Solution (not bashing)

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

@@ Line 90: / Line 90: @@
 so we have that the last 4 digits of N are <math>9376</math>
 and  <math>abc</math> is equal to <math>937</math>
+== Solution (not bashing) ==
+By the Chinese Remainder Theorem, the equation <math>N(N-1)\equiv 0\pmod{10000}</math> 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 <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/10000Z\to\mathbb Z/16Z\times\mathbb Z/625Z</math>, <math>x\mapsto (x\mod{16},x\mod{625})</math>. The statement of the Chinese Remainder theorem is therefore 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>(1,0)=15(0,1)+(1,1)</math> in <math>\mathbb Z/16Z\times\mathbb Z/625Z</math>, so since <math>\phi</math> is linear in its arguments (by virtue of being an isomorphism), <math>\phi^{-1}(1,0)=15\phi^{-1}(0,1)+\phi^{-1}(1,1)=15\times 625+1=9376</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>.

Page

Toolbox

Search

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

Revision as of 17:24, 14 March 2014

Problem 8

Solution (bashing)

Solution (not bashing)