Waste less time on Facebook — follow Brilliant.
×

RMO 2014 Delhi Region Q.3

Suppose for some positive integers \(r\) and \(s\), the digits of \(2^r\) is obtained by permuting the digits of \(2^s\) in decimal expansion. Prove that \(r=s\)


  • You can find rest of the problems here

  • You can find the solutions here

Note by Aneesh Kundu
2 years, 5 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

This one went straight like a tangent over my head. Aneesh Kundu · 2 years, 5 months ago

Log in to reply

if r < or = s 2^s - 2^r = 2^r(2^n - 1) where r+n=s 9 divides 2^n-1 (2^r is a permutation of the digits of 2^s) This is only possible when 2^n=1 Therefore, n=0 which implies that r=s Aaryan Tiwary · 1 year, 5 months ago

Log in to reply

I have also not solved this. But if we assume the number of digits of 2^r and 2^s are same here is a simple solution, Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee Without loss of generality let us assume r>s. Let r=s+k. where k>0 As 2^r and 2^s have same number of digits k<4. [ Since k>=4 will imply multiplying 2^s by a number >10 and thus ending up with a greater number of digits.] now as they have same digits their sum of digits is same SO they are congruent modulo 9. So 2^s+k - 2^s = 2^s( 2^k -1) ==0 (mod 9). Since (9,2^s)=1(i.e they are co-prime) this implies 2^k -1==0(mod 9). k<4 implies 2^k -1 can take values 1 , 3 or 7 all of which leads to a contradiction downright. So k=0 giving r=s. Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee Can you explain why you chose to use modulo 9 rather than modulo 3? Using modulo 3 allows k = 2 to work. Ryan Tamburrino · 2 years, 5 months ago

Log in to reply

@Ryan Tamburrino What do you mean? Modulo 3 will fail to contradict the case k=2 so modulo 9 is the only option left. Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee So one would have to first see that modulo 3 fails before you know to use modulo 9? Ryan Tamburrino · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee Why \(k\leq 4\)

Aren't we just rearranging the digits? Aneesh Kundu · 2 years, 5 months ago

Log in to reply

@Aneesh Kundu Of course!Permutation means rearrangement. k>=4 means we have to multiply 2^s by 16 or more which is >10.An that will lead us to more number of digits in 2^r Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee oh..sorry

Actually I misread \(r=s+k\) as \(r+s=k\), thats why I was wondering that \(k<4\) could be a really useful result. Aneesh Kundu · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee Apparantly this method fails when k=6n as 2^6n==1 (mod 9) which does not provide a contradiction. But this case can surely arise when THERE ARE A NUMBER OF ZEROES AS DIGITS IN 2^r. Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee Please anybody provide solution for this part Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee if \(k=6n\) and \(k<4\), then \(\dfrac{2}{3}>n\) this leaves us with no positive integer values for \(n\). Aneesh Kundu · 2 years, 5 months ago

Log in to reply

@Aneesh Kundu Noooo! We get k<4 only when we know that the number of digits in 2^r and 2^s are same. But if suppose there is a zero in 2^r. When we permute the digits the zero can bemade to come in front thus reducing the number of digits in 2^s. And then we cant say k<4. Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

Comment deleted Dec 08, 2014

Log in to reply

@Souryajit Roy I have also done the same sums. Do u think it is enough?? @ very anxious Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

what marks would you get to show that r-s<4 in this question < i could only proceed till here> Sauditya Yo Yo · 2 years, 4 months ago

Log in to reply

Suppose s ≤ r. If s < r then 2s < 2 r . Since the number of digits in 2s and 2r are the same, we have 2r < 10 × 2 s < 2 s+4. Thus we have 2s < 2 r < 2 s+4 which gives r = s + 1 or s + 2 or s + 3. Since 2r is obtained from 2s by permuting its digits, 2r − 2 s is divisible by 9. If r = s + 1, we see that 2r − 2 s = 2s and it is clearly not divisible by 9. Similarly, 2s+2 − 2 s = 3 × 2 s and 2s+3 − 2 s = 7 × 2 s and none of these is divisible by 9. We conclude that s < r is not possible. Hence r = s Jayakumar Krishnan · 2 years, 5 months ago

Log in to reply

What exactly is the question? Are leading 0's allowed or not? Gopalkrishna Nayak Pangal · 2 years, 5 months ago

Log in to reply

@Gopalkrishna Nayak Pangal I don't get it Aneesh Kundu · 2 years, 5 months ago

Log in to reply

@Gopalkrishna Nayak Pangal Since its not mentioned in the question whether both the power have the same no digits or not, we need to construct a general case.

Its strange that they still haven't uploaded the official solutions till now. Aneesh Kundu · 2 years, 5 months ago

Log in to reply

@Gopalkrishna Nayak Pangal That is the precise problem.Nothing is mentioned about the leading zeroes. I think if we consider the leading zeroes the standard of the question goes well above RMO. But i was stuck at this very juncture and failed to provide the above mod 9 solution. Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

@Chandrachur Banerjee Thee official key says the number of digits are same.I was trying to solve the more general case.I couldnt get it.But i noticed a strange thing 2^{34}=134217728 and 2^{30}=1073741824 and they have almost same digits that is they differ just 1 digit (2 and 4) I don`t think this may help But is it true? Thanks Gopalkrishna Nayak Pangal · 2 years, 5 months ago

Log in to reply

@Gopalkrishna Nayak Pangal Actually i should have felt that the general case is too difficult! the sad part is i felt it after submitting the answer script. Actually this means nothing now but still it was too much of spoilt milk not to cry over!! Jokes apart your observation is really interesting but i heard recently that someone have proved it,( though i haven't seen it myself) Chandrachur Banerjee · 2 years, 5 months ago

Log in to reply

i did not enjoy this problem at all! :( Nihar Mahajan · 2 years, 5 months ago

Log in to reply

Comment deleted 5 months ago

Log in to reply

@Naveen Kelvadi Try reading the question again Aneesh Kundu · 2 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...