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.
Well, I like this problem a lot, now that I have had the crucial insight. Proof is as follows:
A) Line the five numbers up, one below the other, and consider each column individually. There is no common digit, so each column has at least one 1 and 1 zero. If they are split 3 and 2 (i.e., 3 ones and 2 zeroes or 3 zeroes and 2 ones) then there are 4 pairwise matches in the column. If they are split 4 and 1 then there are 6 pairwise matches in the column. Since there are n columns, the number of pairwise matches is between 4n and 6n.
B) Now, consider that we have 5 numbers. They form 10 pairs with each other (5*4/2), and each pair has m matching digits, so there are 10m matches.
c) So 4n <= 10m <= 6n
Therefore, 2/5 <= m/n <= 3/5
D) It is interesting to me we have still not proved that there actually exist 5 distinct n-digit binary numbers such that for any two numbers chosen from them the digits will coincide in precisely m places. But then, we weren't asked to!
Edited on October 21, 2009, 6:39 pm
Eureka! (spoiler)
