For $0 \leq d \leq 9$, we define the numbers \[S_{d}=1+d+d^{2}+\cdots+d^{2006}\]Find the last digit of the number \[S_{0}+S_{1}+\cdots+S_{9}.\]
Problem
Source: Central American Olympiad 2006, Problem 1
Tags: modular arithmetic, geometry, 3D geometry
skimnc
30.04.2007 09:20
There is probably a way better way to do this but I felt like trying it.
$S_{d}=\sum_{n=0}^{2006}d^{n}= \frac{1 \cdot (1-d^{2007})}{1-d}=\frac{d^{2007}-1}{d-1}$
$S_{0}=1 \Rightarrow$ Last digit is $1$
$S_{1}=1+2006 \cdot 1=2007 \Rightarrow$ Last digit is $7$
$S_{2}=2^{2007}-1 \Rightarrow$ Last digit is $3$
Click to reveal hidden textNote that:
$2^{1}-1=1$; Last digit is $1$.
$2^{2}-1=3$; Last digit is $3$.
$2^{3}-1=7$; Last digit is $7$.
$2^{4}-1=15$; Last digit is $5$.
$2^{5}-1=31$; Last digit is $1$.
$2^{6}-1=63$; Last digit is $3$.
$2^{7}-1=127$; Last digit is $7$.
$2^{8}-1=255$; Last digit is $5$.
$2^{9}-1=511$; Last digit is $1$.
$\ldots$
$2^{2004}-1 \Rightarrow$; Last digit is $5$.
$2^{2005}-1 \Rightarrow$; Last digit is $1$.
$2^{2006}-1 \Rightarrow$; Last digit is $3$.
$2^{2007}-1 \Rightarrow$; Last digit is $7$.
So the $2^{2006}-1$ will have a last term of $3$.
$S_{3}=\frac{3^{2006}-1}{3-1}=\frac{3^{2006}-1}{2}\Rightarrow$ Last digit is $4$.
Click to reveal hidden textNote that:
$\frac{3^{1}-1}{2}=1$; Last digit is $1$.
$\frac{3^{2}-1}{2}=4$; Last digit is $4$.
$\frac{3^{3}-1}{2}=13$; Last digit is $3$.
$\frac{3^{4}-1}{2}=40$; Last digit is $0$.
$\frac{3^{5}-1}{2}=121$; Last digit is $1$.
$\frac{3^{6}-1}{2}=364$; Last digit is $4$.
$\frac{3^{7}-1}{2}=1093$; Last digit is $3$.
$\frac{3^{8}-1}{2}=3280$; Last digit is $0$.
$\frac{3^{9}-1}{2}=9841$; Last digit is $1$.
$\ldots$
$\frac{3^{2004}-1}{2}\Rightarrow$; Last digit is $0$.
$\frac{3^{2005}-1}{2}\Rightarrow$; Last digit is $1$.
$\frac{3^{2006}-1}{2}\Rightarrow$; Last digit is $4$.
$\frac{3^{2007}-1}{2}\Rightarrow$; Last digit is $3$.
Continue to note patterns and end up with:
$S_{0}\Rightarrow 1$
$S_{1}\Rightarrow 7$
$S_{2}\Rightarrow 7$
$S_{3}\Rightarrow 3$
$S_{4}\Rightarrow 1$
$S_{5}\Rightarrow 1$
$S_{6}\Rightarrow 7$
$S_{7}\Rightarrow 7$
$S_{8}\Rightarrow 3$
$S_{9}\Rightarrow 1$
$1+7+7+3+1+1+7+7+3+1=38 \Rightarrow$ Last digit is $\boxed{8}$.
HTA
30.04.2007 14:13
skimnc wrote: There is probably a way better way to do this but I felt like trying it.
$S_{d}=\sum_{n=0}^{2006}d^{n}= \frac{1 \cdot (1-d^{2006})}{1-d}=\frac{d^{2006}-1}{d-1}$
$S_{0}=1 \Rightarrow$ Last digit is $1$
$S_{1}=1+2006 \cdot 1=2007 \Rightarrow$ Last digit is $7$
$S_{2}=2^{2006}-1 \Rightarrow$ Last digit is $3$
Click to reveal hidden textNote that:
$2^{1}-1=1$; Last digit is $1$.
$2^{2}-1=3$; Last digit is $3$.
$2^{3}-1=7$; Last digit is $7$.
$2^{4}-1=15$; Last digit is $5$.
$2^{5}-1=31$; Last digit is $1$.
$2^{6}-1=63$; Last digit is $3$.
$2^{7}-1=127$; Last digit is $7$.
$2^{8}-1=255$; Last digit is $5$.
$2^{9}-1=511$; Last digit is $1$.
$\ldots$
$2^{2004}-1 \Rightarrow$; Last digit is $5$.
$2^{2005}-1 \Rightarrow$; Last digit is $1$.
$2^{2006}-1 \Rightarrow$; Last digit is $3$.
So the $2^{2006}-1$ will have a last term of $3$.
$S_{3}=\frac{3^{2006}-1}{3-1}=\frac{3^{2006}-1}{2}\Rightarrow$ Last digit is $4$.
Click to reveal hidden textNote that:
$\frac{3^{1}-1}{2}=1$; Last digit is $1$.
$\frac{3^{2}-1}{2}=4$; Last digit is $4$.
$\frac{3^{3}-1}{2}=13$; Last digit is $3$.
$\frac{3^{4}-1}{2}=40$; Last digit is $0$.
$\frac{3^{5}-1}{2}=121$; Last digit is $1$.
$\frac{3^{6}-1}{2}=364$; Last digit is $4$.
$\frac{3^{7}-1}{2}=1093$; Last digit is $3$.
$\frac{3^{8}-1}{2}=3280$; Last digit is $0$.
$\frac{3^{9}-1}{2}=9841$; Last digit is $1$.
$\ldots$
$\frac{3^{2004}-1}{2}\Rightarrow$; Last digit is $0$.
$\frac{3^{2005}-1}{2}\Rightarrow$; Last digit is $1$.
$\frac{3^{2006}-1}{2}\Rightarrow$; Last digit is $4$.
We can continue to note that the last digit of $S_{d}$ will always be the same last digit of $\frac{d^{2}-1}{d-1}$ aka it will be $d+1$ with the exception of $d=1,6$ in which case it is $\frac{d^{1}-1}{d-1}=1$
$S_{0}\Rightarrow 1$
$S_{1}\Rightarrow 7$
$S_{2}\Rightarrow 3$
$S_{3}\Rightarrow 4$
$S_{4}\Rightarrow 5$
$S_{5}\Rightarrow 6$
$S_{6}\Rightarrow 1$
$S_{7}\Rightarrow 8$
$S_{8}\Rightarrow 9$
$S_{9}\Rightarrow 0$
$1+7+3+4+5+6+1+8+9+0=44 \Rightarrow$ Last digit is $\boxed{4}$.
my solution is the same as you but i dont think it's the best way could anybody have another idea ?
skimnc
30.04.2007 14:41
I see why $1$ doesn't work out to be $d+1$ but why doesn't $6$? I noticed the pattern was it repeated every $5$ numbers but I have no clue as to why $6$ randomly decides to not work.
Kouichi Nakagawa
30.04.2007 17:23
$S_{0}\equiv 1 \pmod{10}$
$S_{1}\equiv 7 \pmod{10}$
$S_{2}\equiv 7 \pmod{10}$
$S_{3}\equiv 3 \pmod{10}$
$S_{4}\equiv 1 \pmod{10}$
$S_{5}\equiv 1 \pmod{10}$
$S_{6}\equiv 7 \pmod{10}$
$S_{7}\equiv 7 \pmod{10}$
$S_{8}\equiv 3 \pmod{10}$
$S_{9}\equiv 1 \pmod{10}$
Therefore, $\sum_{d=0}^{9}S_{d}\equiv 1+7+7+3+1+1+7+7+3+1=38\equiv \boxed{8}\pmod{10}$
Farenhajt
30.04.2007 21:32
Or we can sum the thing by the columns instead of rows: Ten ones give $10$, ten first powers give $45$, ten squares give $0+1+4+9+6+5+6+9+4+1=45$, ten cubes give $45$, ten fourth powers give $0+1+6+1+6+5+6+1+6+1=33$. From fifth power on, the cycle repeats. Hence we have $10+501\cdot(45+45+45+33)+45+45\equiv 8\pmod{10}$
skimnc
30.04.2007 23:00
I originally only carried the sum formula out to $r^{n}$ when it should of been $r^{n+1}$.. I edited it.
rachel12
19.01.2011 08:49
Farenhajt wrote: Or we can sum the thing by the columns instead of rows: Ten ones give $10$, ten first powers give $45$, ten squares give $0+1+4+9+6+5+6+9+4+1=45$, ten cubes give $45$, ten fourth powers give $0+1+6+1+6+5+6+1+6+1=33$. From fifth power on, the cycle repeats. Hence we have $10+501\cdot(45+45+45+33)+45+45\equiv 8\pmod{10}$ I am agree with you. Also doing the same and i think it is the easiest way to calculate. Thanks