Trova le parole di Hamming in R = 2^K Dimensioni

Question

C'è il problema originale e un problema equivalente.

Il problema equivalente: costruisci un set $ a $ che contiene array bit di lunghezza $ r-1 $, dove $ | a | = 2^{r-1}/r $ e $ HAMMING Space Distance (i, j) = 3 quad forall i, j in a, spazio i neq j $.

Misha Lavrov ha dato una risposta eccellente su Math.se che risolve il problema originale. Tuttavia, non ottengo la sua costruzione.

Se potessi dimostrare che il suo algoritmo risolve il problema per qualsiasi $ r = 2^k $ o fornisce il tuo algoritmo che risolva il problema / problema equivalente per qualsiasi $ r = 2^k $, lo apprezzerei davvero.

---

Il problema originale: scegli $ 2^r/r $ bit array, in cui ogni array di bit è di lunghezza $ r $ e $ r = 2^k $ per tutti $ k ge 2 $, in modo tale che gli array scelti possano essere divisi in 2 set, $ a $ e $ b $, dove

1. $ | A | = | b | = 2^{r-1}/r $
2. $ forall x in a. ( esiste y in B. (Hamming Space Distance (x, y) = 1)) $ e $ forall y in b. ( esiste x in A. (Hamming Space Distance (x, y) = 1)) $
3. $ Hamming Space Distance (i, j) = 3 quad forall i, j in a, spazio i neq j $
4. $ Hamming Space Distance (i, J) = 3 Quad forall i, J in B, Space I neq j $

Ecco la risposta per $ k = 2 $, dove i cerchi blu sono scelti da array di bit.

---

(Ps invece di $ n = 2^r $ dimensioni nella mia domanda su matema confuso.)