RMO 2015

I have taken inspiration from my friend Swapnil's note and have decided to post this note.I have decided that I will post one or two problems every now and then that are related to the topics of RMO.They can either be proof problems, like the proof of an integral theorem e.t.c or ones like finding values.The questions will be either from preparation books or from Mathematical olympiads.I will keep on adding them one-by-one in the space below.The main rule is that there should be just one solution to one problem,unless,of course,there are more than one way of doing it.If the solution you have is the same as the one which has already been posted,kindly refrain from posting it,but if you have another method of solving the same problem,please do post it!I will post the solution only if one hasn't been posted in 33 days.So,Happy problem solving!\text{Happy problem solving!} 1.If p is a prime number,then prove that,(a+b)p(ap+bp)(modp)(a+b)^p\equiv(a^p+b^p)\pmod{p} Generalize it too!(Awesome part!) 2.For m>2m>2,prove that,ϕ(m)\phi(m)is even whereϕ\phi is the Euler's Totient Function 3.Prove that there are infinitely many squares in the sequence 1,3,6,10,15,21,28,......1,3,6,10,15,21,28,....... 4.Find all the pairs of positive integers (m,n) such that 2m+3n2^m+3^n is a perfect square.INMO\text{INMO} 5.Prove that 2p+3p2^p+3^p is not a perfect square for a prime pp. 6.If ab(modmn)a\equiv b\pmod{m^n},then prove that ambm(modmn+1)a^m\equiv b^m\pmod{m^{n+1}}(Given by Svatejas Shivakumar). 7.Find a polynomial with integer co-efficients such that P(a)=b,P(b)=c,P(c)=aP(a)=b,P(b)=c,P(c)=a where a,b,ca,b,c are distinct.(given by Anik Mandal).We need a solution for this.Surya Prakash has posted a solution. 8.Find the number of prime nn satisfying the equation 3n+1=k2,kZ+3n+1=k^2,k\in \mathbb{Z}^+.(Given by Mehul Arora). 9.If x3=x+1x^3=x+1 then find integers a,b,ca,b,c such that x7=ax2+bx+cx^7=ax^2+bx+c.(Given by Dev Sharma).

Note by Adarsh Kumar
4 years, 1 month ago

No vote yet
1 vote

  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

5) We consider case when p=2p=2. Clearly 22+32=4+9=132^2+3^2 = 4+9 = 13 which is not a perfect square.So now consider p>2p>2. Let if possible 2p+3q=q22^p+3^q=q^2 for some integer qq.We note that 2p0(mod4)2^p \equiv 0 \pmod{4} , 3p3(mod4)3^p \equiv 3 \pmod{4} , thus 2p+3p3(mod4)2^p+3^p \equiv 3 \pmod{4} but q20,1(mod4)q^2 \equiv 0,1 \pmod{4} which is a contradiction.

Nihar Mahajan - 4 years, 1 month ago

Log in to reply

Thanx for your solution.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

7) If P(x)P(x) is a polynomial with integer coefficients then for distinct integers aa, bb, we have abP(a)P(b)a-b|P(a)-P(b).

So, it implies that abP(a)P(b)=bca-b|P(a)-P(b) = b-c. Similarly we get, bccab-c|c-a and caabc-a|a-b. So finally what we get is abbca-b|b-c, bccab-c|c-a and caabc-a | a-b, this is possible iff ab=bc=caa-b = b-c =c-a. But this implies that a=b=ca=b=c. This is a contradiction as aa, bb and cc are distinct. Therefore no such polynomial exists.

Surya Prakash - 4 years, 1 month ago

Log in to reply

Thanks for the solution!

Anik Mandal - 4 years, 1 month ago

Log in to reply

Thanx for the solution.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

Is the first statement of your solution a lemma?

Nihar Mahajan - 4 years, 1 month ago

Log in to reply

No,it can be proved like this,Since abbc,abbcSince bcca,bccaSince caab,caabSince\ a-b|b-c,a-b\leq b-c\\ Since\ b-c|c-a,b-c\leq c-a\\ Since\ c-a|a-b,c-a\leq a-b.Combining these you get that the equality holds.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

Yes. It is a lemma. it is easy to prove

Surya Prakash - 4 years, 1 month ago

Log in to reply

@Surya Prakash Can you give me hint to prove it? Is it necessary to define a degree to the polynomials?

Nihar Mahajan - 4 years, 1 month ago

Log in to reply

@Nihar Mahajan Take P(x)=anxn+an1xn1++a0P(x) = a_{n} x^n + a_{n-1} x^{n-1} + \ldots + a_{0} where an,an1,a0a_{n} , a_{n-1} , \ldots a_{0} are integers. Now, subtract P(a)P(a) from P(b)P(b) and observe what happens.

Surya Prakash - 4 years, 1 month ago

Log in to reply

9) x3=x+1x7=x4(x+1)=x5+x4=x2(x+1)+x(x+1)=x3+x2+x2+x=2x2+2x+1(a,b,c)=(2,2,1)x^3=x+1 \Rightarrow x^7=x^4(x+1) = x^5+x^4 = x^2(x+1)+x(x+1) = x^3+x^2+x^2+x = 2x^2+2x+1 \\ \Rightarrow (a,b,c)=(2,2,1)

Nihar Mahajan - 4 years, 1 month ago

Log in to reply

No need of all that.See my solution.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

9)x3=x+1x6=(x2+2x+1)x7=x3+2x2+x=2x2+2x+1x^3=x+1\Rightarrow x^6=(x^2+2x+1)\Rightarrow x^7=x^3+2x^2+x=2x^2+2x+1.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

How u got this......explain

Ayush Verma - 3 years, 10 months ago

Log in to reply

For the 3rd3rd question,

The sequence is, S=1+3+6+10+15........+tnS=1+3+6+10+15........+{t}_{n}

To get the tn {t}_{n} we can write it as,

S=0+1+3+6+10+15........+tnS=0+1+3+6+10+15........+{t}_{n}

S=1+3+6+10+15+.....S=1+3+6+10+15+.....

Now, Subtracting both the sums,

0=12345.......tn0=-1-2-3-4-5-.......{t}_{n}

Therefore we can get,

tn=n(n+1)2 {t}_{n}=\frac {n(n+1)}{2}

Now to prove that there are infinitely many squares, Assume that tn{t}_{n} is a square. From here we see that if tn {t}_{n} is a square,

t4n(n+1)=4n(n+1)2.(2n+1)2 {t}_{4n(n+1)}=4\frac{n(n+1)}{2}.{(2n+1)}^{2} is also a square.

Hence if t1=1{t}_{1}=1 is a square then t8=36 {t}_{8}=36 is a square. And if t8{t}_{8} is a square then t48(8+1)=t288=144289 {t}_{4*8(8+1)}={t}_{288}=144*289 is a square.

Therefore,we get a sequence of infinite squares from here.

Saarthak Marathe - 4 years, 1 month ago

Log in to reply

Brilliant solution!

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

Thank you. See my solution for 2nd question

Saarthak Marathe - 4 years, 1 month ago

Log in to reply

6) ambm=(ab)(am1+am2b++abm2+bm1)a^{m}-b^{m}=(a-b)(a^{m-1}+a^{m-2}b+\ldots+ab^{m-2}+b^{m-1}).

Since ab(modmn),ab(modm)a \equiv b \pmod {m^{n}},a \equiv b \pmod {m}.

Hence, amibibm(modm)a^{m-i}b^{i} \equiv b^{m} \pmod {m} and am1+am2b++abm2+bm1mbm0(modm)a^{m-1}+a^{m-2}b+\ldots+ab^{m-2}+b^{m-1} \equiv mb^{m} \equiv 0 \pmod {m}

Hence, ambma^{m}-b^{m} is divisible by mn+1m^{n+1}.

Note: This solution is not original.

Credit: An Excursion in Mathematics.

A Former Brilliant Member - 4 years, 1 month ago

Log in to reply

Really elegant one! Thanx for posting it!

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

Your welcome :)

A Former Brilliant Member - 4 years, 1 month ago

Log in to reply

would it help?

The following results are by Fermet Little Theorm:

ap=amodpa^p = a modp

bp=bmodpb^p = b modp

then ap+bp=a+bmodpa^p + b^p = a + b modp

now (a+b)p=a+bmodp(a + b)^p = a + b modp

so (a+b)p=ap+bpmodp(a + b)^p = a^p + b^p modp

Dev Sharma - 4 years, 1 month ago

Log in to reply

Yeah you are right it was pretty simple.Sorry!

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

let us try 2nd question :

we can make following case and i am writing totient function as E,

Case 1 - when mm is prime then E(m) = m - 1, which is even.

Case 2 - when mm is even, clearly it would contain 2 so it even.

Dev Sharma - 4 years, 1 month ago

Log in to reply

Case 3 - when mm is odd (composite), then m would be divisible by any prime (3,5,7etc) and we know that totient function is multiplicative so, E(m) = E(any prime)E(left out)

also from case 1 we know E(prime) is even, so its even.

Dev Sharma - 4 years, 1 month ago

Log in to reply

"Clearly it would contain 2" please elaborate.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

I am sorry. I explained wrong.

Case 2. If m is even then m would be in form m = even . odd then we know that euler of odd number is even. So it would be even. Well, there would be one more, that is, even = even. Even

Dev Sharma - 4 years, 1 month ago

Log in to reply

@Dev Sharma I believe i am not correctly understanding your method.Do you mean that m=2k(2a+1)m=2^{k}*(2a+1) where 2k2^k is the even part of the number and 2a+12a+1 the odd part?

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

@Adarsh Kumar yes but i am not confident about case 2. And is case 1 and 3 correct?

Dev Sharma - 4 years, 1 month ago

Log in to reply

@Dev Sharma Could you explain after this in your case 2?Your case 1 is correct,i am not so sure about case 3,sorry.You could ask someone else.Actually there is a very simple way of proving this.If you want me to post i will.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

@Adarsh Kumar Please post solution.

Dev Sharma - 4 years, 1 month ago

Log in to reply

is it correct? If not, whats the mistake?

Dev Sharma - 4 years, 1 month ago

Log in to reply

So, what are today's problems?

Swapnil Das - 4 years, 1 month ago

Log in to reply

Thanks!

Harsh Shrivastava - 4 years, 1 month ago

Log in to reply

@Adarsh Kumar I believe that you can add a comment to the board, whenever you add a question. otherwise, it would be difficult to keep track.

You can add a comment like "Q3. is up" or "Next question!" so that people who are interested or have commented on this board get a notification, and they can check it out. Thanks.

Mehul Arora - 4 years, 1 month ago

Log in to reply

Oh nice idea thanx!

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

Looks like giving a good idea gets me a downvote :3

Anyway, Glad to help :)

Mehul Arora - 4 years, 1 month ago

Log in to reply

@Adarsh Kumar In question 7, please mention that a,b and c are distinct. :)

Mehul Arora - 4 years, 1 month ago

Log in to reply

done!

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

6) 3n+1=a23n + 1 = a^2

3n=a213n = a^2 - 1

3n=(a+1)(a1)3n = (a + 1)(a - 1)

so a+1=3soa=2a + 1 = 3 so a = 2 OR

a1=3soa=4a - 1 = 3 so a = 4

then n=1orn=5n = 1 or n = 5

so there are two n...

Dev Sharma - 4 years, 1 month ago

Log in to reply

Is this solution correct? I don't think so...

Harsh Shrivastava - 4 years, 1 month ago

Log in to reply

You assumed that 'n' is prime, which is not given in the question.....

Harsh Shrivastava - 4 years, 1 month ago

Log in to reply

Yeah , correct.

Nihar Mahajan - 4 years, 1 month ago

Log in to reply

@Harsh Shrivastava @Nihar Mahajan @Dev Sharma @Mehul Arora I am sorry but question 6 is wrong.It is satisfied fro more than one value of nn.It is my fault as i should have checked the problem before posting it.Sorry for the inconvenience caused.I am going to delete it.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

@Adarsh Kumar P has to be a prime I told you that.

Mehul Arora - 4 years, 1 month ago

Log in to reply

@Mehul Arora Ni you didn't,go and see the conversation.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

@Adarsh Kumar Oh , sorry if I didn't. Please repost the problem and mention that p is prime.

Mehul Arora - 4 years, 1 month ago

Log in to reply

@Mehul Arora Ohk.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

@Adarsh Kumar I have a question. How can I give you? (not on slack)

Dev Sharma - 4 years, 1 month ago

Log in to reply

@Dev Sharma Give it here.

Mehul Arora - 4 years, 1 month ago

Log in to reply

@Mehul Arora If x3=x+1x^3 = x + 1 then determine integer a,b,c x7=ax2+bx+cx^7 = ax^2 + bx + c

Dev Sharma - 4 years, 1 month ago

Log in to reply

@Dev Sharma Thanx for the question!Kindly delete this comment as i have posted it giving credit to you.

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

For the 2nd2nd question, Case 11: If there is atleast one odd prime factor of mm,

Then by Euler's Totient function corolary, We can say that if prime pp divides a number mm then p1p-1 divides ϕ(m)\phi(m) . As pp is odd, p1p-1 is even, Therefore,2ϕ(m) 2|\phi(m) .

Case 22: If there is no odd prime factor of mm,

Then mm can be written as m=2km={2}^{k} We can easily say that ϕ(m)=2k2k1 \phi(m)={2}^{k}-{2}^{k-1} Hence,2ϕ(m)2|\phi(m)

Saarthak Marathe - 4 years, 1 month ago

Log in to reply

All questions are done!

Saarthak Marathe - 4 years, 1 month ago

Log in to reply

Could you please provide the solution for the 6th6^{th} one?

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

Since no one has posted the solution for the 6th one yet, should I post it (solution given in the book)?

A Former Brilliant Member - 4 years, 1 month ago

Log in to reply

@A Former Brilliant Member Yes,please!

Adarsh Kumar - 4 years, 1 month ago

Log in to reply

First problem can be solved easily by using binomial therom

sameer pimparkhede - 4 years, 1 month ago

Log in to reply

no need

Saarthak Marathe - 4 years, 1 month ago

Log in to reply

fermat's theorem, isn't it?

Raghav Rathi - 3 years, 11 months ago

Log in to reply

@Calvin Lin Sir, is it possible for you to close this note since we already have a part 2 for this note.

A Former Brilliant Member - 4 years, 1 month ago

Log in to reply

I don't see why this note should be locked. It is still valid for discussion, and adding of more comments / problems.

I might consider doing so if OP requests for it.

Calvin Lin Staff - 4 years, 1 month ago

Log in to reply

can anybody solve the rmo 2008 Maharashtra region problem 5

Devang Patil - 4 years ago

Log in to reply

For the 8th8th question,

3n=(k1)(k+1)3n=(k-1)(k+1)

By the Prime factorisation principle, There is a unique prime factorisation for every number.

From here we can say that,

3=k1 3=k-1 and k+1=nk+1=n

Therefore,n=5 n=5 is the only prime of this form.

Saarthak Marathe - 4 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...