CF 103389C - 连锁商店

Rating: -
Tags: -
Solve time: 2m 18s
Verified: no

Solution

Setup

Let vertices be all binary strings $a_{2t-1}\dots a_1a_0$ with exactly $t$ zeros and $t$ ones. A move consists of choosing some index $j \in {1,\dots,2t-1}$ and swapping $a_0$ with $a_j$, producing a new string that still has $t$ zeros and $t$ ones.

The question asks whether all $(t,t)$-combinations can be generated by an ordering of all vertices in which consecutive strings differ by such a swap.

Equivalently, this asks whether the graph $G_t$ whose vertices are all subsets of ${0,1,\dots,2t-1}$ of size $t$, with edges

$$S \sim T \quad \Longleftrightarrow \quad T = S \triangle {0,j} \text{ for some } j \neq 0,$$

has a Hamiltonian cycle.

Known results

Each vertex $S$ can be classified by whether $0 \in S$.

If $0 \in S$, then $S = {0} \cup A$ where $A \subseteq {1,\dots,2t-1}$ and $|A| = t-1$.

If $0 \notin S$, then $S = B$ where $B \subseteq {1,\dots,2t-1}$ and $|B| = t$.

Thus the vertex set splits into two layers:

$$\mathcal{L}_{t-1} = {A \subseteq [2t-1] : |A| = t-1}, \quad \mathcal{L}_t = {B \subseteq [2t-1] : |B| = t}.$$

Under this identification, swapping $a_0$ with $a_j$ corresponds exactly to adding or removing $j$ from the subset of $[2t-1]$. Hence edges connect $A \in \mathcal{L}_{t-1}$ to $B \in \mathcal{L}_t$ precisely when $B = A \cup {j}$.

Therefore $G_t$ is isomorphic to the middle levels graph on the Boolean lattice of $[2t-1]$, restricted to levels $t-1$ and $t$.

The middle levels conjecture asserts that this graph is Hamiltonian for all $t$. This was posed in the 1980s and remained open for several decades. It was finally proved in full generality by Mütze (2014-2016 series of results), establishing that every middle levels graph has a Hamiltonian cycle.

Partial argument

The isomorphism above reduces the problem to constructing a Hamiltonian cycle in a bipartite graph whose parts are $\binom{2t-1}{t-1}$ and $\binom{2t-1}{t}$ vertices, with adjacency given by symmetric difference with a single element.

Each edge toggles membership of exactly one element $j \neq 0$, so every step is a valid swap of $a_0$ with some $a_j$. Any Hamiltonian cycle in the middle levels graph immediately yields a cyclic ordering of all $(t,t)$-combinations satisfying the required swap condition.

Thus a positive solution to the middle levels problem implies a positive answer to the present question.

Status

The problem is equivalent to the middle levels conjecture.

The middle levels conjecture is now a theorem: a Hamiltonian cycle exists for all $t \ge 1$, proved by Mütze and collaborators in the 2010s.

Therefore all $(t,t)$-combinations $a_{2t-1}\dots a_1a_0$ can indeed be generated by repeatedly swapping $a_0$ with some other element.

This completes the solution. ∎