CMC - Problem 9

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

Note by Cody Johnson
5 years, 10 months ago

No vote yet
8 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

I think it's 46.

敬全 钟 - 5 years, 10 months ago

Log in to reply

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

a1=2,a2=4,a3=42=16,a4=164=65536=36(mod100),a5=6553616...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 a5a_5, so we try to trace the pattern, by testing some small values.

361=3636^1 = 36

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

363=96×36(mod10000)=56(mod100)36^3 \overline= 96 \times 36 (mod 10000) \overline= 56 (mod 100)

364=56×36(mod10000)=16(mod100)36^4 \overline= 56 \times 36 (mod 10000) \overline = 16 (mod 100)

365=16×36(mod10000)=76(mod100)36^5 \overline= 16 \times 36 (mod 10000) \overline = 76 (mod 100)

366=76×36(mod10000)=36(mod100)36^6 \overline= 76 \times 36 (mod 10000) \overline = 36 (mod 100),

367=36×36(mod10000)=96(mod100)36^7 \overline= 36 \times 36 (mod 10000) \overline = 96 (mod 100),

and so on. Obviously, the pattern recurs every 5 terms. Since 16=1(mod5)16 \overline= 1 (mod 5), so last two digits of 655361665536^{16} is 3636. Thus, we have 3636 as the last two digits of pp, since no matter what happens, we have 66 as the last digit of every term except term a1a_1 and a2a_2, and 6=1(mod5)6 \overline= 1 (mod 5) .

Then, when k=5k = 5, we have

a1=2,a2=5,a3=52=25,a4=255...a_1 = 2, a_2 = 5, a_3 = 5^2 = 25, a_4 =25^5 ...

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

51=55^1 = 5

52=255^2 = 25

53=1255^3 = 125

54=6255^4 =625

and so on. Starting from 525^2, last two digits are 2525. Thus, 25525^5 has 2525 as the last two digits, so as the term a5=2525a_5 = 25^{25}. Therefore, qq has 2525 as the last two digits.

Then, when k=6k = 6, we have

a1=2,a2=6,a3=62=36,a4=366=36(mod100),a5=36(mod100)...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=4k=4! So, last digits of r=36r = 36

Finally, when k=7k=7, we have

a1=2,a2=7,a3=72=49,a4=497...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.

491=4949^1 = 49

492=240149^2 = 2401

493=01×49(mod100)=49(mod100)49^3 \overline= 01 \times 49 (mod 100) \overline = 49 (mod 100)

494=49×49(mod10000)=01(mod100)49^4 \overline= 49 \times 49 (mod 10000) \overline = 01 (mod 100)

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

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

敬全 钟 - 5 years, 10 months ago

Log in to reply

Some Latex suggestions. Use:

\pmod n

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

Anqi Li - 5 years, 10 months ago

Log in to reply

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

敬全 钟 - 5 years, 10 months ago

Log in to reply

Correct! 8 points for you!

Cody Johnson - 5 years, 10 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 - 5 years, 10 months ago

Log in to reply

Can you explain the second sentence? Do you mean that a1024a_{1024}has 44 possible values or other thing else?

敬全 钟 - 5 years, 10 months ago

Log in to reply

When k=4k = 4 , a1024=pa_{1024} = p and when k=5k = 5 , a1024=qa_{1024} = q and so on .

Sadman Sakib - 5 years, 10 months ago

Log in to reply

Okay, I got it. Thanks.

敬全 钟 - 5 years, 10 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 - 5 years, 10 months ago

Log in to reply

Okay, first of all, I start with k=4k=4. Then, we follow the rules to define the next term of the sequence, we have a1=2,a2=k=4,a3=a(31)a(32)=a2a1=42=16,and a4=164=65536a_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=36(mod100)65536 \overline= 36 \pmod {100} is because 1006553636100|65536 - 36. So, you may ask me why I can't try 136,236136, 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=b(modn)a\overline= b \pmod n, that means nabn|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 36336^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 36336^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 36736^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 (mod10000)\pmod {10000} instead of (mod100) or (mod1000)\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=1(mod5)6 \overline= 1\pmod5, so from here it indicates the first term in the pattern. Therefore, pp has 36 as its last two digits, since the exponent ends with 6.

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

Alright, for the case when k=6k=6 and k=7k=7, I use the same way, even though the case when k=6k=6, I skipped a lot, since the exponent ends with 6, just like when k=4k=4. Finally, sum up p+q+r+sp+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 a1024a_{1024}...)

敬全 钟 - 5 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...