Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
What did you try? What are your thoughts? How do you know the result holds? – Did Jan 24 '13 at 20:11
I'll delete the question... Why? – Did Jan 24 '13 at 20:17
WHY? $ $ $ $ – Did Jan 24 '13 at 20:21
Please stop defacing the question. – Andrés E. Caicedo Jan 24 '13 at 20:35
but now that it's up, I'm interested. It's not just for the asker. – mez Jan 24 '13 at 20:39

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|cite|improve this answer

Your Answer


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.