1
$\begingroup$

Given eight points on a circle that are to be labelled with three binary digits, we can easily find a labeling where all adjacent points have Hamming distance one.

I have also found examples where the average Hamming distance is equal to two, for instance [000, 011, 110, 001, 100, 010, 111, 101]. But is it possible to find a labeling where each adjacent pair has Hamming distance two?

edit: Forgot to point out that we're looking at the distance of ADJACENT pairs.

$\endgroup$
  • $\begingroup$ There are 8 possible words so the list would contain every word...but 000 and 111 have distance 3. $\endgroup$ – fretty Oct 5 '15 at 7:57
1
$\begingroup$

With distance 2, you can never get from the points having zero or two 1-bits to the points having one or three of them, so the answer is no.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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