How to apply pigeonhole principle to a binary string problem Given two strings $x,y \in \{0,1\}^n$, we say that the distance between them is the number of coordinates in which they disagree, so for example, $00\ldots 00$ and $11\ldots 11$ are at distance $n$, while $00\ldots 00$ and $00\ldots 01$ are at distance $1$. 
Suppose that $n \geq 10.$ The question is the following: Do there exist three strings $x,y,z \in  \{0,1\}^n$ so that the distance between any two of them is strictly greater than $n/2$? 
I've been trying to show that for this inequality to be true, $x, y,$ and $z$ have to disagree on at most $n/2$ coordinates, but I'm having trouble writing up a proof/coming up with an appropriate counterexample. If anyone could help I'd love it.
 A: Yes. Such strings exist. 
You can get them to differ at a distance of up to $\lfloor 2n/3 \rfloor$.

Proof that distance $\lfloor 2n/3 \rfloor$ is maximal:

 In each coordinate, we can get at most 2 pairs of strings to disagree.
 Over all coordinates, we can get at most 2n coordinate-pairs to disagree.
 Hence, the $\lfloor 2n/3 \rfloor$ distance is the best that we can do.   


Proof that strings that differ in at least $ \lfloor \frac{2n}{3} \rfloor$ exist:
Simply take the $n=3$ case and repeat the coordinates as needed.
$\begin{array} {llllllllllllll}
0&0&0& &0&0&0& &0&0&0& \ldots \\
0&1&1& &0&1&1& &0&1&1& \ldots \\
1&1&0& &1&1&0& &1&1&0& \ldots \\ \end{array} $
(Clearly these differ in at least $ 2 \lfloor \frac{n}{3} \rfloor$ places. Slight checking of details / exact values when $ n \equiv 1, 2 \pmod{3}$)
A: There can in fact exist 3 strings that mutually differ by strictly more than $n/2$ digits. Consider $x =111111$, $y=000011$, $z = 110000$. This example generalizes to where $x$ is all ones, $y$ has the first third of digits as ones, and $z$ has the last third of digits as ones.
