MathDB

Let

d \geq 3

be a positive integer. The binary strings of length

d

are splitted into

2^{d-1}

pairs, such that the strings in each pair differ in exactly one position. Show that there exists an

<span class='latex-italic'>alternating cycle</span>

of length at most

2d-2

, i.e. at most

2d-2

binary strings that can be arranged on a circle so that any pair of adjacent strings differ in exactly one position and exactly half of the pairs of adjacent strings are pairs in the split.

Problem Statement