# Combinatorics question. Bit stuck.

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.

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