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.)
 Eureka! (spoiler) | Comment 3 of 7 |
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
 Posted by Steve Herman on 2009-10-21 18:38:26

 Search: Search body:
Forums (0)