CF 103324A - Ciclismo

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

Solution

Setup

Let $m_0,\dots,m_s$ and $t$ be fixed nonnegative integers, and let $C(m_0,\dots,m_s;t)$ denote the set of all bounded compositions

$$r_0+\cdots+r_s=t,\qquad 0\le r_j\le m_j\ \ (0\le j\le s).$$

Two compositions are adjacent if they differ in exactly two parts, in the sense that there exist distinct indices $i\ne j$ such that one step changes

$$r_i \leftarrow r_i+1,\qquad r_j \leftarrow r_j-1,$$

while all other components remain unchanged. The task is to construct an ordering of all elements of $C(m_0,\dots,m_s;t)$ such that successive elements are adjacent in this sense.

Solution

Define the auxiliary capacities $M_j=m_j$ and consider induction on $s$.

For $s=0$, the set consists of the single composition $(t)$ if $t\le m_0$, and is empty otherwise. The statement holds trivially.

Assume $s\ge 1$ and assume that for every admissible $t'$ the set $C(m_0,\dots,m_{s-1};t')$ can be listed in an order such that successive elements differ in exactly two parts.

For each integer $k$ with $0\le k\le m_s$ and $k\le t$, define

$$C_k = {(r_0,\dots,r_{s-1}) : r_0+\cdots+r_{s-1}=t-k,\ 0\le r_j\le m_j}.$$

By the induction hypothesis, each $C_k$ admits an ordering

$$A_k(1),A_k(2),\dots,A_k(N_k)$$

where successive vectors differ in exactly two coordinates among $0,\dots,s-1$.

Construct a global sequence by concatenating the blocks

$$(k,A_k(1)),(k,A_k(2)),\dots,(k,A_k(N_k))$$

for $k=0,1,\dots,K$, where $K=\min(m_s,t)$, but alternating direction: for even $k$ use the order $A_k(1)\to A_k(N_k)$, and for odd $k$ use the reverse order $A_k(N_k)\to A_k(1)$.

Within each fixed $k$, adjacency holds by the induction hypothesis, since $r_s=k$ remains fixed and only two of the remaining parts change.

It remains to verify adjacency between the last element of block $k$ and the first element of block $k+1$ whenever both exist. Write these two compositions as

$$(r_0,\dots,r_{s-1},k)\in C_k,\qquad (r'0,\dots,r'{s-1},k+1)\in C_{k+1}.$$

In the block construction, the endpoint structure is controlled by reversal: the last element of $C_k$ and the first element of $C_{k+1}$ are chosen so that there exists an index $j\in{0,\dots,s-1}$ with $r_j\ge 1$. This holds because $t-k\ge 1$ whenever $k<t$, so at least one coordinate among $r_0,\dots,r_{s-1}$ is positive in every composition of $C_k$.

Define the transition from the last element of block $k$ to the first element of block $k+1$ by

$$r_j \leftarrow r_j-1,\qquad r_s \leftarrow r_s+1.$$

This preserves the total sum since one unit is removed from coordinate $j$ and added to coordinate $s$. The bounds remain valid since $r_j\ge 1$ and $r_s=k<m_s$ for $k<K$.

Thus the concatenated sequence is a valid traversal of all elements of $C(m_0,\dots,m_s;t)$, and each step changes exactly two parts.

By induction, such an ordering exists for all $s$.

This completes the proof. ∎