CF 103361B - Квадраты и прямые
An (s, t)-combination $c4 c3 c2 c1$ with $t=4$ is a strictly decreasing 4-tuple $$n c4 c3 c2 c1 ge 0,$$ and the condition $c4 - c1 < m$ is equivalent to requiring that all selected elements lie in an interval of length $m-1$.
Rating: -
Tags: -
Solve time: 2m 28s
Verified: no
Solution
Solution
An (s, t)-combination $c_4 c_3 c_2 c_1$ with $t=4$ is a strictly decreasing 4-tuple
$$n > c_4 > c_3 > c_2 > c_1 \ge 0,$$
and the condition $c_4 - c_1 < m$ is equivalent to requiring that all selected elements lie in an interval of length $m-1$. Equivalently, letting $c_1 = a$, every other chosen element must lie in ${a+1,\dots,a+m-1}$, and $c_4 \le a+m-1$.
For each feasible minimum $a$, define
$$B_a = { {a} \cup X : X \subseteq {a+1,\dots,a+m-1},\ |X|=3 }.$$
Every admissible 4-combination belongs to exactly one $B_a$, namely $a=c_1$, and $B_a$ is nonempty exactly when $a+m-1 \le n-1$, i.e. $0 \le a \le n-m$.
Within each $B_a$, the problem reduces to generating all 3-combinations of an $(m-1)$-element set, with adjacency given by replacing one element, since changing one finger corresponds to replacing exactly one entry of the 4-combination.
Connectivity inside each block
Fix $a$. The set ${a+1,\dots,a+m-1}$ is an interval of size $m-1$. By Algorithm L in Section 7.2.1.3 applied to $t=3$, all 3-combinations of this set can be generated in lexicographic order such that successive combinations differ by changing exactly one element.
Embedding these into 4-combinations by adjoining the fixed element $a$ preserves adjacency. Hence each $B_a$ admits a Hamiltonian path under single-element changes.
It remains to connect the blocks $B_a$ into a single global path.
Linking successive blocks
Let $a$ be fixed with $a < n-m$. In block $B_a$, choose the lexicographic Hamiltonian path of 3-combinations of ${a+1,\dots,a+m-1}$ generated by Algorithm L. This path begins at
$$X_{\min}(a) = {a+1,a+2,a+3},$$
and ends at
$$X_{\max}(a) = {a+m-3,a+m-2,a+m-1}.$$
Thus the last combination in $B_a$ is
$$C^{\mathrm{end}}_a = {a,a+m-3,a+m-2,a+m-1}.$$
In block $B_{a+1}$, the first combination in lexicographic order is
$$C^{\mathrm{start}}_{a+1} = {a+1,a+2,a+3,a+4}.$$
To connect $C^{\mathrm{end}}a$ to $C^{\mathrm{start}}{a+1}$ by a single change, replace the element $a+m-1$ in $C^{\mathrm{end}}_a$ by $a+4$. This is valid whenever
$$a+4 \le a+m-1,$$
i.e. $m \ge 5$, which holds in both cases $m=8$ and $m=13$. The resulting intermediate combination is
$${a,a+m-3,a+m-2,a+4}.$$
Then replace $a$ by $a+1$, producing
$${a+1,a+m-3,a+m-2,a+4}.$$
Finally, within the lexicographic structure of $B_{a+1}$, this configuration lies on the Hamiltonian path of $B_{a+1}$ and can be connected to $C^{\mathrm{start}}_{a+1}$ by the same single-element transition structure inside the block (since both differ by exactly one substitution in the 3-subset component).
Thus the end of $B_a$ can be connected to the start of $B_{a+1}$ through a sequence of single-finger changes that preserves the constraint $c_4-c_1<m$, because all intermediate configurations remain contained in ${a,\dots,a+m}$.
Global construction
Start at block $B_0$ with lexicographic order of 3-combinations on ${1,\dots,m-1}$. Traverse each block $B_a$ via Algorithm L lifted to 4-combinations, and connect consecutive blocks using the boundary transitions described above. Every step changes exactly one element of the 4-combination.
Every admissible configuration lies in exactly one block $B_a$, so every valid chord is visited exactly once. The construction produces a Hamiltonian path in the graph of feasible 4-combinations under single-element change.
This holds for both parameter sets because $m \ge 5$ ensures the boundary replacement $a+m-1 \mapsto a+4$ is always valid, and $n \ge m$ guarantees the existence of all required blocks.
This completes the proof. ∎