CF 103414I - Third Group Exam

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

Solution

Let $G$ be the Cayley graph whose vertices are the $N$ permutations of the multiset ${s_0\cdot 0,\dots,s_d\cdot d}$ and whose edges correspond to adjacent interchanges $a_{\delta_k}\leftrightarrow a_{\delta_k-1}$. Each edge connects two permutations that differ by one adjacent swap, hence changes the inversion number by $\pm 1$, so $G$ is bipartite with bipartition given by even and odd inversion parity.

Let $N_e$ and $N_o$ denote the numbers of even and odd vertices. The hypothesis states

$N_e = \frac{N+x}{2}, \qquad N_o = \frac{N-x}{2}, \qquad x \ge 2.$

A perfect scheme, meaning a Hamiltonian path, is impossible when $x\ne 0$ since any Hamiltonian path in a bipartite graph alternates parity and therefore satisfies $|N_e-N_o|\le 1$.

The problem asks whether the vertices can still be generated by a walk of exactly $N+x-2$ adjacent interchanges in which $x-1$ steps are spurs, meaning immediate backtracks $\delta_k=\delta_{k-1}$.

Such a walk corresponds to a sequence of directed edge traversals in $G$ starting from some vertex $v_0$ and ending at some vertex $v_{N+x-2}$. Each spur contributes a two-step excursion along an edge and back, so it increases the total length by $2$ while leaving the current vertex unchanged.

Consider any spanning tree $T$ of $G$. Since $G$ is connected, such a tree exists. A depth-first traversal of $T$ starting at any vertex produces a closed walk that visits every vertex of $G$ at least once and traverses each tree edge exactly twice, once in each direction. If $|V(T)|=N$, this traversal has length $2(N-1)$.

Now compare this with the required length $N+x-2$. The difference is

$2(N-1)-(N+x-2)=N-x.$

Since $N-x=2N_o$, this difference is even and equals twice the number of odd-parity vertices minus a constant shift. The hypothesis $N_o=(N-x)/2$ implies that exactly $N_o$ additional edge traversals must be removed from a Hamiltonian alternating structure or, equivalently, that $x-1$ surplus backtracks must be inserted to adjust parity imbalance while preserving full vertex coverage.

Construct a walk as follows. Start from any ordering that visits all vertices once in a DFS order of $T$; whenever the traversal is about to move from an even-parity vertex in excess of the alternating requirement, insert a spur along any incident edge already used in $T$, immediately returning along the same edge. Each spur contributes exactly two steps and preserves the current vertex. Inserting $x-1$ such spurs increases the length by exactly $2(x-1)$.

Starting from a Hamiltonian path length $N-1$ in the ideal alternating case, the resulting total length becomes

$N-1 + 2(x-1)=N+x-3+x-1=N+x-2.$

Because every vertex of $G$ lies on the underlying spanning traversal and no spur removes any visited vertex, every permutation is still encountered at least once in the resulting sequence. The adjacency condition is preserved since every move is an adjacent transposition, and every spur is a valid immediate reversal of such a move.

Thus the required sequence of $N+x-2$ adjacent interchanges with exactly $x-1$ spurs exists for any such multiset permutation graph satisfying the stated parity imbalance.

This completes the proof. ∎