CMC - Problem 9

I do it this way. I start with $k=4$. First we try small numbers first.

$a_1 = 2, a_2 = 4, a_3 = 4^2 = 16, a_4 = 16^4 = 65536 \overline= 36 (mod 100), a_5 = 65536^{16} ...$

It would be laborious for us to calculate term $a_5$, so we try to trace the pattern, by testing some small values.

$36^1 = 36$

$36^2 = 1296 \overline= 96 (mod 100)$

$36^3 \overline= 96 \times 36 (mod 10000) \overline= 56 (mod 100)$

$36^4 \overline= 56 \times 36 (mod 10000) \overline = 16 (mod 100)$

$36^5 \overline= 16 \times 36 (mod 10000) \overline = 76 (mod 100)$

$36^6 \overline= 76 \times 36 (mod 10000) \overline = 36 (mod 100)$,

$36^7 \overline= 36 \times 36 (mod 10000) \overline = 96 (mod 100)$,

and so on. Obviously, the pattern recurs every 5 terms. Since $16 \overline= 1 (mod 5)$, so last two digits of $65536^{16}$ is $36$. Thus, we have $36$ as the last two digits of $p$, since no matter what happens, we have $6$ as the last digit of every term except term $a_1$ and $a_2$, and $6 \overline= 1 (mod 5)$.

Then, when $k = 5$, we have

$a_1 = 2, a_2 = 5, a_3 = 5^2 = 25, a_4 =25^5 ...$

Since $25^5$ is very hard to calculate, so we try to trace the pattern again,

$5^1 = 5$

$5^2 = 25$

$5^3 = 125$

$5^4 =625$

and so on. Starting from $5^2$, last two digits are $25$. Thus, $25^5$ has $25$ as the last two digits, so as the term $a_5 = 25^{25}$. Therefore, $q$ has $25$ as the last two digits.

Then, when $k = 6$, we have

$a_1 = 2, a_2 = 6, a_3 = 6^2 = 36, a_4 = 36^6 \overline= 36(mod 100), a_5 \overline= 36 (mod 100) ...$.

Hey! This case is almost the same as when $k=4$! So, last digits of $r = 36$

Finally, when $k=7$, we have

$a_1 = 2, a_2 = 7, a_3 = 7^2 = 49, a_4 = 49^7 ...$

Again, for the last time in this problem, we trace the pattern.

$49^1 = 49$

$49^2 = 2401$

$49^3 \overline= 01 \times 49 (mod 100) \overline = 49 (mod 100)$

$49^4 \overline= 49 \times 49 (mod 10000) \overline = 01 (mod 100)$

and so on. Obviously, the pattern recurs every two terms. Since $7 \overline= 1(mod 2)$, so $49^7 \overline= 49(mod 100)$, so as term $a_5 = 49^{343} \overline= 49(mod 100)$. This implies that $r$ has last two digits of $49$.

In the end, $p+q+r+s = 36+25+36+49 \overline= \boxed {46}(mod 100)$.

When $k = 4$ , $a_{1024} = p$ and when $k = 5$ , $a_{1024} = q$ and so on .

Okay, first of all, I start with $k=4$. Then, we follow the rules to define the next term of the sequence, we have $a_1 = 2, a_2 = k = 4, a_3 = a_{(3-1)}^{a_{(3-2)}} = a_2^{a_1} = 4^2 = 16, \text{and } a_4 = 16^4 = 65536$. So, why I write $65536 \overline= 36 \pmod {100}$ is because $100|65536 - 36$. So, you may ask me why I can't try $136, 236$ or bigger, yes, you can. But remember we need last two digits. It is all about Modular Arithmetic. So, if you don't understand or don't know what is Modular Arithmetic, click on the link. (By the way, you have to understand the main property of modular, that is when $a\overline= b \pmod n$, that means $n|a-b$.)

Now, let's move on to the line 7. (I expect you understand line 5 and 6) It would be laborious for us to calculate $36^3$ (In this competition, it is stated clearly that calculator or any calculating program is prohibited, so this way is faster and better), so I take the last two digits of 1296, which is 96, then since $36^3$ is equal to 36 times of 1296, so I multiply 96 with 36, and this process goes on and on (But I stopped it when it reaches $36^7$, since it is enough to prove that the pattern of the last two digits is recursive). So, you may ask me why I write $\pmod {10000}$ instead of $\pmod{100} \text{ or } \pmod{1000}$, from line 7 to line 12. Yes, you can, if you want to, there is no right and wrong about that, as long as your statement satisfy the main property I listed out. Okay, back to the solution, as we know, $6 \overline= 1\pmod5$, so from here it indicates the first term in the pattern. Therefore, $p$ has 36 as its last two digits, since the exponent ends with 6.

Then, we now move on to the case when $k=5$. Do you realize that except term $a_1$ and $a_2$, all of them ends with 25. This implies to every term and $q$ execpt term $a_1$ and $a_2$ has 25 as the last two digits.

Alright, for the case when $k=6$ and $k=7$, I use the same way, even though the case when $k=6$, I skipped a lot, since the exponent ends with 6, just like when $k=4$. Finally, sum up $p+q+r+s$, we have 46 as the last two digits.

So, I had try my best to explain, I hope you had understand. This question tests you Pattern Recognition the most, since you have to check out the pattern what has happened to the last two digits when the exponents are different. Otherwise, if you choose to use brute force, then you will have to calculate for 1024 times, that would drive you nuts. (I can't imagine what is the real value of $a_{1024}$...)