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.

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.)
Solution 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

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 (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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