Q6 Matemática  (Baltic Way 2007)

Freddy anota os números $1,2,\dots ,n$ em alguma ordem. Então ele faz uma lista de todos os pares $(i,j)$ tal que $1\le i<j\le n$ e o número $i$-th é maior que o número $j$-th em sua permutação. Depois disso, Freddy repete a seguinte ação enquanto possível: escolha um par $(i,j)$ da lista atual, troque o número $i$-th e o $j$-th na permutação atual e exclua $(i,j)$ da lista. Prove que Freddy pode escolher pares em tal ordem que, após o término do processo, os números na permutação estejam em ordem crescente.