All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
2/5 ≤ m/n ≤ 3/5 (Posted on 2009-10-20) Difficulty: 3 of 5
Five distinct n-digit binary numbers are such that for any two numbers chosen from them the digits will coincide in precisely m places. There is no place with the common digit for all the five numbers. At least one of the binary numbers contains leading zero.

Prove that 2/5 ≤ m/n ≤ 3/5.

See The Solution Submitted by K Sengupta    
Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Some thoughts | Comment 2 of 7 |
Without loss of generality, assume that the first number is all zeroes (n of them).  Then the remaining 4 numbers must have m zeroes and (n-m) ones.  Consider any two of the remaining 4.  Swapping digits in one of them either leaves the number of matches between the two unchanged, or increases or decreases it by two.  Since we can eventually make the two numbers match by swapping digits, and at that point the number of matches between them is n, it follows that the m and n must have the same parity.

For example, (m,n) cannot be (2,5) or (3,6) or (4,7) or (6,7).

I don't think that this helps, but I did find it useful to start the proof by assuming that one number is n zeroes and that the remaining 4 numbers have m zeroes and (n-m) ones. 

Edited on October 21, 2009, 6:11 pm
  Posted by Steve Herman on 2009-10-21 18:10:08

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information