Prove that the Hamming distances between three n-tuples cannot be 6,2,7

Question

Let $x,y,z \in \{0,1\}^n$, and let $d_H(x,y)$ be the Hamming distance between codes x and y.

Prove $d_H(x,y) = 6$, $d_H(y,z) = 2$, $d_H(x,z) = 7$ cannot happen.

Answer 1

Without loss of generality, suppose that you reorder the bits of x and z such that the first 7 bits of x are different to the first 7 bits of z, as their hamming distance is 7, while the rest of the bits must be the same. So suppose then again without loss of generality you have the following for x and z

x:0000000hhhhh..., z:1111111hhhhh...

Where h is everywhere 0 or 1 (it must be the same value in x and z).

First let $n \geq 9$.

The distance between z and y is 2, so you have 3 cases in total to check.

First case, y agrees with z in the first 7 bits. But this contradicts d(x,y)=6, so you have a contradiction.

Second case, without loss of generality, y agrees with z on the first 6 bits, but not on the seventh, which must be 0. But then in one of the remaining bit of y in which z has value h (note that by construction also x has value h), y must take value 1 - h. But then again $ d(x,y)\geq 7$, a contradiction.

Third and last case, without loss of generality, y agrees with z on the first 5 bits and the sixth and the seventh bits must be both 0. However all the rest of the bits of y must agree with z and, by construction, with x too. Since $n \geq9$, d(x,y) $\geq 7$, contradiction again.

For $n=7,8$ you can reason in a similar manner.

Answer 2

Welcome to MSE! I've looked into the triangular inequality: $d(x,z)\leq d(x,y)+d(y,z)$. But it doesn't help here: $2+6\geq 7$, $2+7\geq 6$, $6+7\geq 2$.

Answer 3

Notice that $d(x,y)=w(x+y)$ where the sum is modulo $2$, and $w$ is the weight function (it counts the number of ones).

Then $d(x,z) = w(x+z) = w(x+ y + y+ z) = w(a +b)$ where $a=x+y$ and $b=y+z$

Now $w(a+b) = w(a)+ w(b) - 2 w(c)$ where $c=a.b$ is the pointwise product (or bitwise AND function - or the number of ones in common). Then, in general

$$d(x,z)=d(x,y)+d(y,z)-2 k$$

for some integer $k$.

Or, equivalently, $d(x,z)+d(x,y)+d(y,z)$ is even.

Hence, it can never happen that, of the three mutual distance, two distances are even and one is odd. Either we have three even distances, or two odd and one even.

---

BTW 1: This problem has nothing to do with Hamming (or linear) codes, the statement refers to arbitrary binary tuples.

BTW 2: Next time you ask a question, please try to add some of your thoughts or what have you tried, to show us that you are not simply looking for someone else to do your homework. That's not what this website is for. And if the people here suspect you are doing that, they might downvote, close or refuse to answer your questions.

BTW 3: Welcome to MSE