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.
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
Some thoughts
