Problema C2 Ammissione Winter camp

[Stef2008]

Si scrive inizialmente una parola con n lettere diverse. Poi ad ogni passaggio si scrive
una nuova parola di n lettere, invertendo la piú lunga sottoparola iniziale che non
produca una parola giá scritta. Dimostrare che si scriveranno n! parole.

Ho provato per induzione ma non ci sono riuscito, ringrazio in anticipo chiunque scriva una soluzione. Apprezzo anche qualsiasi consiglio