Rimettere in ordine

[axpgn]

I figli del professor Rinaldi usano spesso i libri della ponderosa enciclopedia del padre per i loro compiti a casa (bei tempi ) ma non li rimettono mai a posto.
Ecco, questa è la disposizione dopo il loro ultimo passaggio: $7-3-5-4-9-1-10-6-2-8$

Il professore vuole rimetterli in ordine ma, data la pesantezza di ogni singolo volume, vorrebbe ottimizzare il compito ovvero ogni mossa consiste nel prendere un libro, spingere alcuni di quelli rimasti da un lato e riposizionare il libro tolto.

Qual è il numero minimo di mosse da fare?


Cordialmente, Alex

[ElementareWatson]

9 mosse?

Ho trovato un algoritmo per metterle tutte in ordine ma non ho ancora dimostrato se è il più veloce.

7 è il minimo che mi riesce

Ma su questo non ho un algoritmo, se non fossero disposte così non funzionerebbe.

[gabriella127]

Ho fatto un riordinamento con 6 mosse. Sposto in sequenza (ovviamente mettendoli in posti giusti, no a casaccio): 5-7-10-2-1-9 .
L'idea che mi è venuta è di cercare la sequenza consecutiva più lunga, nel nostro caso 3-4-6-8 (mi pare), così gli elementi della sequenza possono stare fermi.

[ElementareWatson]

"gabriella127":

Ho fatto un riordinamento con 6 mosse. Sposto in sequenza (ovviamente mettendoli in posti giusti, no a casaccio): 5-7-10-2-1-9 .
L'idea che mi è venuta è di cercare la sequenza consecutiva più lunga, nel nostro caso 3-4-6-8 (mi pare), così gli elementi della sequenza possono stare fermi.

Bella idea!

[gabriella127]

Non so se è il minimo, ma almeno non sono tanti.
Resta da capire se è il minimo.
Azzardo la congettura, che manco il teorema di Fermat:
Il numero minimo di mosse per riordinare $n$ numeri in sequenza è pari a $n$ meno la lunghezza della sequenza ordinata massima.

[axpgn]

Congettura giusta!

Esistono varie soluzioni perché esistono varie sequenze crescenti di pari lunghezza (p.es. $3, 5, 6, 8$ o $3, 5, 9, 10$) ma il minimo è sempre lo stesso

Cordialmente, Alex

[gabriella127]

Grazie! E ora un milione di dollari a chi dimostra la congettura!

[ElementareWatson]

"gabriella127":Grazie! E ora un milione di dollari a chi dimostra la congettura!

Beh la tua idea è già una mezza dimostrazione, se due numeri \(\displaystyle a_i \) e \(\displaystyle a_j \) sono tali che \(\displaystyle a_i < a_j \) ed \(\displaystyle a_j \) viene prima di \(\displaystyle a_i \) allora ci deve essere almeno una mossa per riordinarli, iterando il ragionamento si conclude.

[gabriella127]

La tua idea mi pare buona, ci penso su a mente più fresca.
Allora facciamo mezzo milione a te e mezzo milione a me