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)
(→‎Problem 8)
Line 1: Line 1:
 
== Problem 8 ==
 
== 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>.
 +
 +
 +
== Solution (bashing)==
 +
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:
 +
<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.
 +
we first consider the ones digits:
 +
 +
<math>d^2\equiv (mod  10)</math>
 +
 +
this can happen for only 3 values : 1, 5 and 6
 +
 +
we can try to solve each case
 +
*Case 1 <math>(d=1)</math>
 +
considering the tenths place
 +
we have that:
 +
 +
<math>20cd=20c\equiv 10c (mod  100)</math>
 +
so <math>c= 0</math>
 +
 +
considering the hundreds place we have that
 +
 +
<math>200bd+100c^2= 200b \equiv 100b (mod1000)</math>
 +
so again <math>b=0</math>
 +
 +
now considering the thousands place we have that
 +
 +
<math>2000ad+2000bc = 2000a \equiv 1000a (mod 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>
 +
 +
*Case 2 <math>(d=5)</math>
 +
considering the tenths place
 +
we have that:
 +
 +
<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)
 +
so <math>c=2</math>
 +
 +
considering the hundreds place we have that
 +
 +
<math>200bd+100c^2+100c= 1000b+600 \equiv600\equiv 100b (mod1000)</math>
 +
( the extra 100c is carried from the tenths place)
 +
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>
 +
( the extra 1000b is carried from the hundreds place)
 +
so a is equal 0 again
 +
 +
*Case 3<math>(d=6)</math>
 +
considering the tenths place
 +
we have that:
 +
 +
<math>20cd+30=120c+30\equiv 30+20c \equiv 10c (mod  100)</math>
 +
( the extra 20 is carried from <math>d^2</math> which is equal to 25)
 +
if <math>c=7</math> then we have
 +
 +
<math>30+20*7 \equiv 70\equiv7*10(mod100)</math>
 +
 +
so <math>c=7</math>
 +
 +
considering the hundreds place we have that
 +
 +
<math>200bd+100c^2+100c+100= 1200b+4900+700 \equiv200b+700\equiv 100b (mod1000)</math>
 +
( the extra 100c+100 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>
 +
 +
so <math>b=3</math>
 +
 +
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>
 +
( the extra 1000b+6000 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>
 +
 +
so <math>a=9</math>
 +
 +
so we have that the last 4 digits of N are <math>9376</math>
 +
and  <math>abc</math> is equal to <math>937</math>

Revision as of 13:09, 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$

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