Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution (bashing))
(→‎Solution (general))
Line 4: Line 4:
  
 
==Solution (general)==
 
==Solution (general)==
 +
 +
We have that <math>N^2 - N = N(N - 1)\equiv 0\mod{10000}</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 (bashing)==

Revision as of 12:19, 15 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 (general)

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$ must be congruent to -1 (mod 16). Since $625 \equiv 1 \mod{16}$, we know that $15*625 = 9375 \equiv 15 \equiv -1 \mod{16}$. Thus, $N-1 = 9375$, so $N = 9376$, and our answer is $\boxed{937}$.

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 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*7 \equiv 70\equiv7*10 \pmod{100}$

so $c=7$

considering the hundreds place we have that

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

if $b=3$ then we have

$700+200*3 \equiv 300\equiv3*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*9+1000 \equiv 9000\equiv9*1000 \pmod {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/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 \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}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_I_Problems/Problem_8&oldid=61052"