Source: Cute problem sent by Sudeep Kanath
Problem: Prove that (2n choose n) is never a perfect power
Update ( 21 June 2014 ):
Solution: Posted by Sandeep, Dinesh Krithivasan and Vishal Khatri in comments.
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Post Comments (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...
There is always atleast one prime between n and 2n. (Bertrand's postulate). These primes occur only once in factorization of 2nCn. So, 2nCn can never be a perfect power.
ReplyDeleteThanks
DeleteDirect consequence of Bertrand's postulate. After canceling out one of the n! in the denominator, the numerator will be the product of (n+1)(n+2)... up to 2n. By Bertrand's postulate, there is a prime in this group of numbers, say p. Then, (2n choose n) is divisible by p but not any powers of p and so cannot be a perfect power.
ReplyDeleteThis is probably nuking a mosquito though  there ought to be a simple proof.
Most proofs of Bertrand's postulate (at least the ones on wiki) start by studying the prime factorization of 2nCn. So, this reasoning is likely to be circular.
DeleteThanks.
DeleteIt will always be some power of 2 multiplied with some odd number. So, it can't be a perfect power.
ReplyDelete?? Wrong solution!
DeleteJust saw your comment on this..I agree, I have written it wrong... just have to work out again to what i wanted to write. Thanks for bringing it to notice :)
DeleteI meant to say that it will always be a power of 2 multiplied with some odd numbers of which at least one would a prime. And after reading the comments above and below, I noticed that the prime would be lying in n to 2n.
DeleteSo, I wrote it wrong, Thank you for pointing out :)
There is always a prime between n and 2n. Hence!
ReplyDeleteThanks
DeleteBertrand's postulate it is !!!
ReplyDeletehttp://en.wikipedia.org/wiki/Bertrand%27s_postulate