Problema C2 Ammissione Winter camp 2019 [L04\5]

[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 anticioo chiunque scriva una soluzione, o mi dia qualche consiglio

[Stef2008]

Scusate dovevo metterlo in combinatoria, non teoria dei numeri, come posso cambiarlo?

[ronny]

Testo nascosto:

Dovrei ristudiarmi la teoria dei grafi, ma mi viene un'idea. Se costruiamo un grafo dove ogni nodo è una delle n! parole, e gli archi
sono passaggi da una parola ad un altra tramite inversione delle prime lettere. Per ogni parola ci sono n-1 possibilità di inversione e quindi
il nodo avrà n-1 archi. Allora ci servirebbe un cammino hamiltoniano (semplice), cioè un cammino che passi una sola
volta da tutti i nodi. Però nel passaggio da una parola ad un'altra si deve scegliere quella che cambia il maggior numero di
lettere. Questo vincono forse può essere espresso con dei pesi sugli archi e la ricerca diventa quella del camminio con costo minimo.
Concludendo non saprei dire se funziona, ma forse è un'idea.

[Stef2008]

Grazie mille, lavorerò su questa idea!!

[afullo]

Scusate dovevo metterlo in combinatoria, non teoria dei numeri, come posso cambiarlo?

Te l'ho spostato in Combinatoria.

[Stef2008]

Scusate dovevo metterlo in combinatoria, non teoria dei numeri, come posso cambiarlo?

Te l'ho spostato in Combinatoria.

Grazie