Strong convergence in posets (Q423649)

The following solitaire game is considered. The game is played on a poset \((P,\prec)\) with n elements. The player is handed an arbitrary permutation \(\pi=(x_{1},x_{2},\dots,x_{n})\) of the elements in \(P\). At each round an element may swap positions with a smaller element preceding it. For example, if \(x_{i}\prec x_{i+1}\), then it is allowed to move from \(\pi\) to the permutation \((x_{1},x_{2},\dots,x_{i-1},x_{i+1},x_{i},x_{i+2},\dots,x_{n})\) of \(P\)'s elements. The player is to carry out such steps as long as such swaps are possible. When there are several consecutive pairs of elements that satisfy this condition, the player can choose which pair to swap next. It is shown that the final permutation is uniquely determined by the initial order of \(P\)'s elements. The proof works by constructing an appropriate system of invariants.