Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 103 / 5 / b / ii / Solution

Suppose $\lambda ⊴\mu$ in the dominance order on partitions and $\lambda \ne \mu$. Let $i$ be the first unequal row. Then ${\lambda }_i<{\mu }_i$. PutWe have $D_i>0$, and eventually $D_h=0$. Let $j>i$ be its first return to zero. Then $D_h\ge 1$ for $i\le h<j$ and ${\lambda }_j>{\mu }_j$.

Move one box from row $j$ to row $i$. Increasing row $i$ is legal: if $i>1$, then ${\lambda }_{i-1}={\mu }_{i-1}\ge {\mu }_i>{\lambda }_i$. Decreasing row $j$ is also legal. If ${\lambda }_j={\lambda }_{j+1}$, then ${\mu }_{j+1}\le {\mu }_j<{\lambda }_j={\lambda }_{j+1}$, forcing $D_{j+1}<0$, a contradiction. Also ${\lambda }_j>0$. Thus the new list $\nu$ is a partition of an integer.

The new deficits equal $D_h-1$ on $i\le h<j$ and $D_h$ elsewhere, so $\lambda ⊴\nu ⊴\mu$. The quantity ${\sum }_r|{\lambda }_r-{\mu }_r|$ decreases by two, since the changed rows were a deficit and a surplus. Repeating must terminate at $\mu$. HenceThe construction proves both termination and preservation of the intermediate dominance inequalities.