Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why can't there exist 5 5-digit binary numbers such that each pair has 1 or 2 digits in common?

Another way to state the condition is that any pair has either 3 or 4 digits that are different.

share|improve this question
1  
What did you try? What are your thoughts? How do you know the result holds? –  Did Jan 24 '13 at 20:11
2  
I'll delete the question... Why? –  Did Jan 24 '13 at 20:17
1  
WHY? $ $ $ $ –  Did Jan 24 '13 at 20:21
1  
Please stop defacing the question. –  Andres Caicedo Jan 24 '13 at 20:35
2  
but now that it's up, I'm interested. It's not just for the asker. –  mez Jan 24 '13 at 20:39

1 Answer 1

Assume we have found 5 such numbers $(a_1,a_2,a_3,a_4,a_5)$. We can generate new solutions by exclusively or'ing each one with any constant we choose, and by picking $a_1$ we can get a solution where one of the five numbers is $0$.

Now, each other number must have either 3 or 4 $1's$ in to satisfy the conditions. Note that any pair of 5 bit numbers with 4 $1's$ would share 3 bits in common, so at most one of the other 4 numbers has 4 $1's$. Thus we have at least 3 numbers with only 3 $1's$. Since there are only 5 bits, at least one pair of these must share a $0$, but that would mean they also share two of the $1's$. Hence this set cannot satisfy the requirements, and thus no such set exists.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.