1
$\begingroup$

Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1.

I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w_1\cdots w_k$ and $x = x_1\cdots x_n$, and proceeding with a case-based argument. Let $i$ be the unique index where the strings differ. We have the following cases: 1) $1\leq i\leq k$ and 2) $i > k.$ We also need to consider the subcases a) $n < k$ and b) $n \ge k$ for each case. In the first case (case 1 a), $x_1\cdots x_n = w_1\cdots w_n$ and $w_1\cdots w_{i - n} = w_{n+1}\cdots w_i$. Also, $w_{i-n + 1} = w_{i+1}, \cdots, w_{k-n} = w_k.$ This argument seems very tedious, so I was wondering if there's a better argument?

$\endgroup$

2 Answers 2

3
$\begingroup$

Lemma:

The parity of the Hamming distance between two strings is the parity of the total number of $1$s.

Proof:

If you toggle any bit in any of the strings, the parity of the distance changes. Start from two "all zeroes" strings and toggle all it takes to get to the targeted strings.

E.g.:

$$00000, 00000\to0\to0\\01000, 00000\to1\to1\\01000, 00100\to2 \to0\\01000, 10100\to3\to1\\\\01000, 11100\to2\to0\\\cdots$$


The main claim follows because the total number of $1$s in $wx$ and $xw$ is perforce even.

$\endgroup$
1
  • $\begingroup$ Nice. So the distance can't be 1 as asked, but it also can't be 3, 5, 7 etc. $\endgroup$
    – gnasher729
    Commented Jun 20, 2022 at 14:18
2
$\begingroup$

$w$ and $x$ are binary strings.

Clearly $|wx|=|xw|$ and $|wx|_0=|xw|_0$. Suppose $wx$ and $xw$ differ only at position $i$, so that $(wx)[i]\ne(xw)[i]$, $(wx)[1..i-1]=(xw)[1..i-1]$, and $(wx)[i+1..n+k]=(xw)[i+1..n+k]$.

Wolog, assume $(wx)[i]$ is $1$, and thus $(xw)[i]$ is $0$. Now,

$$\begin{align}|wx|_0 &= |(wx)[1..i-1]|_0 + 0 + |(wx)[i+1..n+k]|_0\\ |xw|_0 &= |(xw)[1..i-1]|_0 + 1 + |(xw)[i+1..n+k]|_0\\ &= |(wx)[1..i-1]|_0 + 1 + |(wx)[i+1..n+k]|_0\\ \end{align}$$ which contradicts $|wx|_0=|xw|_0$.

More generally, let $w$ be any binary string and let $w'$ be any permutation of $w$. Using a generalization of the above argument, show that the Hamming distance between $w$ and $w'$ is even.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.