MathNet 2024-part-01 — 168 problems (EN–VI) Question 96

Let $d \ge 3$ be a positive integer. The binary strings of length $d$ are split into $2^{d-1}$ pairs, such that the strings in each pair differ in exactly one position. Show that there exists an alternating cycle 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.
(Lyuben Lichev)