How to apply pigeonhole principle to a binary string problem

Question

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.

Answer 1

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}$)

Answer 2

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.