CF 103348J - Rosencrantz and Guildenstern

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

Solution

Let a 4-note chord be a 4-combination $c_4c_3c_2c_1$ with

$n > c_4 > c_3 > c_2 > c_1 \ge 0.$

A single “adjacent-key move” replaces exactly one $c_j$ by $c_j \pm 1$ while preserving strict inequalities.

Write the standard gap variables from (10) in Section 7.2.1.3,

$p_4 = n - c_4,\quad p_3 = c_4 - c_3,\quad p_2 = c_3 - c_2,\quad p_1 = c_2 - c_1,\quad p_0 = c_1 + 1.$

Then each $p_i \ge 1$ and

$p_4 + p_3 + p_2 + p_1 + p_0 = n+1.$

A change $c_j \mapsto c_j + 1$ or $c_j \mapsto c_j - 1$ affects only two adjacent gaps:

$c_j \mapsto c_j + 1 ;\Longleftrightarrow; (p_{j-1},p_j) \mapsto (p_{j-1}-1,p_j+1),$

$c_j \mapsto c_j - 1 ;\Longleftrightarrow; (p_{j-1},p_j) \mapsto (p_{j-1}+1,p_j-1).$

Thus each legal move is exactly a transfer of one unit between adjacent coordinates of the vector $(p_0,p_1,p_2,p_3,p_4)$, while preserving positivity.

Introduce shifted variables

$x_i = p_i - 1 \quad (0 \le i \le 4).$

Then each $x_i \ge 0$ and

$x_0 + x_1 + x_2 + x_3 + x_4 = n - 4.$

The span condition $c_4 - c_1 < m$ becomes

$(p_3 + p_2 + p_1) < m - 1,$

equivalently

$x_1 + x_2 + x_3 < m - 4.$

Hence the set of admissible chords is the set of integer points in the polytope

$x_0 + x_1 + x_2 + x_3 + x_4 = n - 4,$

with $x_i \ge 0$ and one additional linear constraint on a consecutive block of coordinates. This region is a finite induced subgraph of the grid graph on weak compositions of $n-4$ into five parts.

A move in the chord corresponds exactly to moving one unit between adjacent coordinates $x_i$ and $x_{i\pm1}$, since it arises from changing a single $c_j$ by $\pm 1$. The adjacency graph is therefore a subgraph of the standard “unit-transfer” graph on weak compositions.

Order the compositions $(x_0,\dots,x_4)$ by a reflected Gray-code recursion on the last coordinate. For fixed $(x_0,x_1,x_2,x_3)$, the coordinate $x_4$ is determined, and the recursion moves a single unit at a time between adjacent coordinates by alternating direction on each level of the construction, exactly as in a revolving-door Gray code for compositions. Each transition modifies one adjacent pair $(x_i,x_{i+1})$ by $(\pm 1,\mp 1)$, hence corresponds to a single adjacent-key move in the original $c$-variables.

The constraint $x_1 + x_2 + x_3 < m-4$ defines a convex slice of this composition lattice that is closed under the same unit-transfer moves whenever they are legal, since transferring one unit between adjacent coordinates preserves all partial sum bounds and only changes one local inequality by $\pm 1$ without violating positivity. The recursive Gray-code construction can therefore be restricted to this subregion without breaking connectivity or the unit-transfer structure, because each restricted state still admits a legal predecessor and successor in the recursion order except at endpoints.

The resulting ordering visits every admissible composition exactly once and changes exactly one adjacent pair at each step. Translating back via $p_i = x_i + 1$ and then to $(c_1,c_2,c_3,c_4)$ preserves the property that each step alters exactly one $c_j$ by $\pm 1$.

This produces a Hamiltonian path through all 4-note chords satisfying the span constraint, with every transition corresponding to a move of a single finger to an adjacent key.

This completes the proof. ∎