Q36 Matemática  (IMO Shortlist 1998)

As cartas numeradas de 1 a 9 são dispostas aleatoriamente em uma fileira. Em uma jogada, pode-se escolher qualquer bloco de cartas consecutivas cujos números estejam em ordem crescente ou decrescente e trocar o bloco. Por exemplo, 9 1 $\underline{653}$ $2748$ pode ser alterado para $91$ $\underline{356}$ $2748$ . Prove que em no máximo 12 lances é possível dispor as 9 cartas de forma que seus números fiquem em ordem crescente ou decrescente.