Pigeonhole Principle: How many three-digit bit strings must we choose to be sure two of them agree on at least one digit?

Question

Textbook answer: 4

I don't see how the answer is 4, though. Because choose any two bit strings, say 000 and 111 or 010 and 101, then wouldn't any other bit string agree on one digit of any two of those bit strings that do not agree on none of the digits? So shouldn't the answer be 3? Or am I missing a special case?

Answer 1

You're right. If you pick a bit string, say $b_1b_2b_3$, then if the second bit string does not agree at any digit with the first bit string, then it must be $(1-b_1)(1-b_2)(1-b_3)$, i.e., the bitwise complement. But then the third bit string must agree at some place with one of these. (In fact it must agree with at least one of these in at least two places.)

As your examples indicate, if your first bit string was for example 011, then in order to not agree at any place, the second bit string must be 100, but then no matter what the first digit of the third bit string is, it has to be either 1 or 0, in which case it agrees with at least one of these strings.