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

 2/5 ≤ m/n ≤ 3/5 (Posted on 2009-10-20)
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.

 No Solution Yet Submitted by K Sengupta Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 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

 Search: Search body:
Forums (0)