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.
|show 1 more comment|
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.