[L05] L'ordine è tutto.

[Giovanni98]

Sono dati i numeri da $1$ a $n$ , con $n\ge2$ intero , in un qualche ordine. Una mossa consiste nello scegliere un intero e metterlo al suo posto. Per esempio se io ho $2,3,1,4,5$ e scelgo il numero $3$ allora dopo aver fatto la mossa avrò $2,1,3,4,5$. Altro esempio , se io ho $2,5,4,1,3$ e scelgo il numero $1$ dopo aver fatto la mossa avrò $1,2,5,4,3$.

a) Dimostrare che comunque si scelgano le mossa da fare prima o poi gli $n$ interi saranno ordinati in maniera crescente.

b) Quanto vale , in funzione di $n$ , il massimo numero di mosse che è possibile fare?

[Veritasium]

Bello!

Testo nascosto:

Per il punto a)

Procediamo per induzione: per [tex]n = 2[/tex] è ovvio. Supponiamolo vero per [tex]n[/tex] e dimostriamolo per [tex]n + 1.[/tex]

Notiamo che, se [tex]1[/tex] o [tex]n + 1[/tex] vanno al loro posto, il gioco finisce per il per il passo base, essendo che quel numero non si può più spostare e gli altri [tex]n[/tex] sono quindi nella situazione per cui si è supposto finiscano in ordine crescente.
Supponiamo ora per assurdo che il gioco non abbia termine. Allora, essendo che le possibili disposizioni dei numeri in fila sono finite (al massimo [tex](n + 1)![/tex]), ce ne deve essere una che si ripete più di una volta (in realtà infinite volte, ma ce ne bastano [tex]2[/tex]), sia essa [tex]P[/tex]. Applichiamo ora una qualsiasi mossa [tex]M[/tex] a [tex]P[/tex] spostando un numero [tex]a_1[/tex], [tex]WLOG[/tex] da sinistra a destra, dove ovviamente si intende che l'[tex]m-esimo[/tex] posto in fila è a destra dell'[tex]l-esimo[/tex] se e solo se [tex]m > l[/tex] (il [tex]WLOG[/tex] vale perchè, come si vedrà, il caso per cui [tex]a_1[/tex] viene spostato da destra a sinistra è analogo). Ora si ha che è necessario che [tex]a_1[/tex] torni al posto dov'era prima, prima o poi, perchè si ritorni nella situazione [tex]P.[/tex] Notiamo che ciò può accadere solo se dei numeri alla sinistra di [tex]a_1[/tex] vengono spostati alla sua destra, essendo che [tex]a_1[/tex] è al suo posto. Consideriamo la prima mossa [tex]M_1[/tex] in cui si verifica uno spostamento di questo tipo: [tex]a_1[/tex] si troverà in un posto [tex]k \ge a_1[/tex] (potrebbe essere avanzato verso destra, ma non verso sinistra essendo questa la prima mossa in cui ciò avviene). Allora, un certo numero [tex]a_2,[/tex] verrà posizionato alla destra di [tex]a_1[/tex], nel posto [tex]a_2 > a_1[/tex]. Dimostriamo ora che, in [tex]P, a_2[/tex] si trovava in un posto alla sinistra del posto [tex]a_1[/tex]: se non fosse così, allora dopo [tex]M, a_2[/tex] si sarebbe trovato alla destra di [tex]a_1,[/tex] ma essendo che appena prima di [tex]M_1[/tex] è alla sua sinistra, dovrebbe averlo scavalcato verso sinistra, implicando che il suo posto sarebbe appunto alla sinistra di quello di [tex]a_1[/tex], contraddicendo l'ipotesi che [tex]a_2 > a_1.[/tex]. Siamo ora in una situazione in cui [tex]a_2[/tex] si trova al suo posto, alla destra di dov'era in [tex]P[/tex]. Perchè la situazione ritorni quella che era in [tex]P, a_2[/tex] deve ritornare verso sinistra, il che può accadere, esattamente come nel caso precedente, venendo scavalcato da (almeno) un [tex]a_3 > a_2.[/tex] Iterando questo ragionamento, ovvero considerando sempre la prima mossa in cui uno spostamento di questo tipo accade, e notando che ogni volta [tex]a_{i + 1} > a_i[/tex], si vede che essendo la fila finita, [tex]n + 1[/tex] dovrà essere posizionato al suo posto (ricordando che tutto ciò vale se si prova a ricostruire la situazione [tex]P[/tex]), il che prova l'assurdo perchè, per quanto visto prima, una volta posizionato [tex]n + 1[/tex] (o analogamente, con [tex]a_{i + 1} < a_i[/tex] e il posizionamento di [tex]1[/tex]), il gioco finisce.
Perciò l'assurdo è dimostrato e il passo induttivo è provato.