Waste less time on Facebook — follow Brilliant.
×

CMC - Problem 9

Problem 9. (8 points) Let \(a_n\) be a sequence such that \(a_1=2,a_2=k\) for some \(k\) and for all \(n\ge3\), \(a_n=a_{n-1}^{a_{n-2}}\). Let \(p,q,r,s\) be the values of \(a_{1024}\) where \(k=4,5,6,7\), respectively. Find the last two digits of \(p+q+r+s\).

Note by Cody Johnson
3 years, 11 months ago

No vote yet
8 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

I think it's 46.

敬全 钟 - 3 years, 11 months ago

Log in to reply

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)\).

敬全 钟 - 3 years, 11 months ago

Log in to reply

Some Latex suggestions. Use:

\pmod n

which comes out as \( \pmod n \) which looks nicer.

Anqi Li - 3 years, 11 months ago

Log in to reply

@Anqi Li Okay, I appreciate that and I will remember that

敬全 钟 - 3 years, 11 months ago

Log in to reply

Correct! 8 points for you!

Cody Johnson - 3 years, 11 months ago

Log in to reply

The last two digits of P=36,Q=25,R=36,S=49.Thus Last two digits of P+Q+R+S=46

Anant Chhajwani - 3 years, 11 months ago

Log in to reply

i dont know sir can u liease teach me i will be very glad to get teachings from you

Shantanu Raut - 3 years, 11 months ago

Log in to reply

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}\)...)

敬全 钟 - 3 years, 11 months ago

Log in to reply

Can you explain the second sentence? Do you mean that \(a_{1024}\)has \(4\) possible values or other thing else?

敬全 钟 - 3 years, 11 months ago

Log in to reply

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

Sadman Sakib - 3 years, 11 months ago

Log in to reply

Okay, I got it. Thanks.

敬全 钟 - 3 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...