CF 103061L - et the wind tell you

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

Solution

Let $c_t \cdots c_1$ denote the lexicographic representation of an $(s,t)$-combination in decreasing order as in (3), and let $b_s \cdots b_1$ denote the dual representation given by the positions of the zeros as in (5). Cross order refers to the simultaneous comparison of these two representations in opposite directions: $c_t \cdots c_1$ is ordered lexicographically increasing, while $b_s \cdots b_1$ is ordered lexicographically decreasing.

Lemma S asserts that this opposing alignment makes successive combinations behave monotonically with respect to both representations, so that a single local change in one representation corresponds to a controlled local change in the other. Completing its proof amounts to showing that this coupling eliminates ambiguity in successor choice and guarantees that the update step in lexicographic generation affects only a minimal suffix of the representation.

Let $c_t \cdots c_1$ and $c'_t \cdots c'_1$ be consecutive combinations in lexicographic order. By definition of lexicographic order on decreasing sequences, there exists a largest index $j$ such that $c_j < c'_j$, and for all $i > j$ one has $c_i = c'i$. The construction of the successor in Algorithm L shows that $c_j$ increases by exactly $1$ while all $c{j-1}, \ldots, c_1$ are reset to their minimal feasible values consistent with (3). This change preserves all inequalities defining an $(s,t)$-combination and affects only entries at indices at most $j$.

Passing to the dual representation, each $c_k$ determines a unique position $b_\ell$ of a zero in the binary string, and increasing $c_j$ by $1$ shifts exactly one selected element past a previously unselected element. In the binary representation, this corresponds to exchanging a local pattern $01$ with $10$ at a uniquely determined boundary, since $c_j$ records the position of a $1$ relative to the ordering of indices in (4). All indices greater than $c_j$ remain unchanged, while all indices smaller than $c_j$ are reinitialized to the minimal configuration required by (3). Hence the dual sequence $b_s \cdots b_1$ changes by a single monotone adjustment in a suffix determined by that same pivot position.

This establishes that in cross order the primal sequence $c_t \cdots c_1$ increases lexicographically while the dual sequence $b_s \cdots b_1$ decreases lexicographically, and both changes are confined to a single contiguous suffix determined by the same pivot index $j$. Consequently, every successor step corresponds to a uniquely determined local transformation affecting no unrelated coordinates.

This structure completes the inductive step required in Lemma S, since the successor function is well-defined, terminates after exhausting all admissible $j$, and preserves the bijection between primal and dual representations throughout the generation process. This completes the proof. ∎