سؤال

There is the original problem, and an equivalent problem.

The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$.

Misha Lavrov gave an excellent answer on Math.SE that solves the original problem. However, I don't get his construction.

If you could prove that his algorithm solves the problem for any $r=2^k$, or provide your own algorithm that solves the problem / equivalent problem for any $r=2^k$, I'd really appreciate it.


The original problem: choose $2^r/r$ bit arrays, where each bit array is of length $r$, and $r=2^k$ for all $k \ge 2$, such that the chosen arrays can be split into 2 sets, $A$ and $B$, where

  1. $|A|=|B|=2^{r-1}/r$
  2. $\forall x \in A.(\exists y \in B.(hamming \space distance (x, y) = 1))$ and $\forall y \in B.(\exists x \in A.(hamming \space distance (x, y) = 1))$
  3. $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$
  4. $hamming \space distance (i, j) = 3 \quad \forall i, j \in B, \space i \neq j$

Here is the answer for $k = 2$, where blue circles are chosen bit arrays.


(P.S. Instead of $n=2^r$ dimensions in my question on Math.SE, I used $r=2^k$ here, because Misha's answer referred to bit arrays of length $r$. I hope this is not too confusing.)

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top