# Very interesting problem that I can't solve.

• Feb 27th 2010, 08:14 AM
chengbin
Very interesting problem that I can't solve.
This was on my grade 10 Cayley math contest a few days ago. It is really interesting, but super hard.

We have a circle with 10 points (think of a clock that goes from 0-9). The dial starts at 0. In each move Tom moves the dial $n^n$ times. So on the first move Tom moves $1^1$ times, and the dial is at 1. Second move Tom moves $2^2$ times, and the dial is at 5, and third move Tom moves $3^3$ times, and the dial is at 2. What number would the dial be pointing at after 1234 moves?

Essentially it is asking what $\sum_{n=1}^{1234} n^n \text { mod } 10$ is.
• Feb 27th 2010, 09:32 AM
qmech
Try this:

1. Break this into 2 problems:
(your sum) = a mod 2.
(your sum) = b mod 5.

If you can find a and b, you can find the equivalent:
(your sum) = c mod 10. (use Chinese remainder theorem) and you are done.

Now to find b: (finding a is easier)
Remember that the numbers
1,2,3,4,5,6,7,8,9,10... = 1,2,3,4,0,1,2,3,4,0...mod (5).
So your 'n' in the bottom doesn't vary all that much.

Also, remember Fermat's little theorem => if a isn't a multiple of p, then
a^(p-1)=1(p). In other words, things like:
4^4=1(5), 12^12=1(5), etc.

This should simplify your sum a lot.
• Feb 27th 2010, 09:45 AM
chengbin
Thanks for your attempt at helping me.

I'm not sure if I understand your explanation. It seems to be a university level solution.

This question is from a grade 10 contest, so it should be solved with grade 10 level mathematics and a serious amount of cleverness.
• Feb 27th 2010, 10:25 AM
qmech
Ok, try this.

It should be obvious that 11^11 is the same as 1^11 because all you care about is the last digit.

Then try pairing: 1^1 and 9^9, since 9 = -1 (going 1 unit in the other direction). Also, tricks like 5^anything = 5(10), 6^anything = 6 (10), etc.
• Feb 27th 2010, 03:02 PM
chengbin
Quote:

Originally Posted by qmech
Ok, try this.

It should be obvious that 11^11 is the same as 1^11 because all you care about is the last digit.

Then try pairing: 1^1 and 9^9, since 9 = -1 (going 1 unit in the other direction). Also, tricks like 5^anything = 5(10), 6^anything = 6 (10), etc.

I still don't see how that can help me. I can see it being helpful for the first 10 terms...
• Feb 27th 2010, 03:17 PM
icemanfan
Note that a move of $(10k)^{10k}$ moves the dial to the same position it was before.

It should also be obvious that $(10k + a)^{10k + a}$ is equivalent to $a^{10k + a} = a^{10k} \cdot a^a$.

Then just look for helpful patterns. For instance:

$2^2 \equiv 4, 2^{12} \equiv 6, 2^{22} \equiv 4, 2^{32} \equiv 6$

so consecutive pairs of these terms will cancel out.
• Feb 27th 2010, 03:27 PM
chengbin
Quote:

Originally Posted by icemanfan
Note that a move of $(10k)^{10k}$ moves the dial to the same position it was before.

It should also be obvious that $(10k + a)^{10k + a}$ is equivalent to $a^{10k + a} = a^{10k} \cdot a^a$.

Then just look for helpful patterns. For instance:

$2^2 \equiv 4, 2^{12} \equiv 6, 2^{22} \equiv 4, 2^{32} \equiv 6$

so consecutive pairs of these terms will cancel out.

So I only need to find out what $1231^{1231}+1232^{1232}+1233^{1233}+1234^{1234} mod 10$ is?

Am I doing this right?

$1231^{1231}=[123(10)+1]^{123(10)+1}=1^{1231}=1$?