OliForum Matematico

Sia data una successione di interi positivi $ s_1, s_2, ... s_n $. Di questa successione si scelga una sotto successione $ 1 \le 2 \le i \le n $.
In modo che gli interi che la compongono siano presi in ordine crescente o decrescente.
Dimostrare che esiste sempre una sotto successione di lunghezza (ovvero il numero di elementi ordinati) $ \sqrt n $.
Spero che il testo sia corretto!

Il testo diceva anche che gli interi sono tutti distinti, e che le sottosequenze devono essere ordinate come la sequenza iniziale (cioè ad esempio 1 7 5 è una sottosequenza di 1 3 4 7 5 8, 1 8 4 non lo è perché non è ordinata). Il suggerimento era mostrare che, dato un intero si della successione, detto ai la lunghezza della massima sequenza crescente che termina con si, e detta bi la lunghezza della massima sottosequenza decrescente che termina con si, presi comunque due elementi si e sj si deve avere ai diverso da aj o bi diverso da bj (o eventualmente entrambi).

Dimostriamo il suggerimento. Prendiamo due interi si e sj, con sj che viene dopo si nella sequenza. si hanno due casi:
- se sj>si, allora sj allunga la sequenza crescente più lunga che termina con si, e dunque aj>ai.
- se sj>si,allora sj allunga la sequenza decrescente più lunga che termina con si, e dunque bj>bi.
in entrambi i casi le coppie ordinate (ai,bi) e (aj,bj) devono essere diverse per almeno un elemento.

Ora, poiché gli interi della sequenza sono n, devo poter formare n coppie ordinate distinte (ai,bi). Per fare ciò, ho bisogno di almeno [math]\sqrt{n} interi distinti. perciò uno (almeno) tra ai e bi deve assumere tutti i valori distinti compresi tra 1 e [math]\sqrt{n}. Ossia, esiste almeno una sottosequenza crescente o decrescente di lunghezza [math]\sqrt{n}.

QED

Scusami, non ho capito perché si devono poter formare n coppie ordinate distinte, potresti rispiegare l'ultima parte? Grazie

A ogni elemento $ S_i $ associ, come suggerisce il testo, la coppia ($ A_i $,$ B_i $) che indica la lunghezza delle più lunghe sequenze ordinate (rispettivamente crescente e decrescente) che finiscono con $ S_i $. Ora, come si dimostra, se due elementi sono distinti devono avere $ A_i $ o $ B_i $ distinti. Cioè, le n coppie ($ A_i $,$ B_i $) sono tutte distinte almeno per un elemento.

Va bene, e poi?

E poi. Quanti elementi ti servono almeno per formare n coppie ordinate distinte, utilizzando gli stessi elementi per entrambi i componenti di una coppia? Almeno $ \sqrt{n} $. Esempio. devi colorare in modo diverso n divise di calcio, formate da maglietta e pantaloncini, usando un solo colore per la maglietta e uno solo (anche lo stesso) per i pantaloncini. Ti servono almeno $ \sqrt{n} $ colori: infatti, se a ognuno degli $ \sqrt{n} $ colori delle magliette associ ognuno degli $ \sqrt{n} $ colori dei pantaloncini ottieni $ \sqrt{n^2}=n $ divise distinte, che sono coppie ordinate di un colore per la maglietta e uno per i pantaloncini.
Ora, se mi servono almeno $ \sqrt{n} $ valori distinti per le coppie (Ai,Bi) vuol dire che uno tra ai e bi assume almeno $ \sqrt{n} $ valori distinti. In altri termini, esistono almeno $ \sqrt{n} $ sequenze (supponiamo crescenti) di lunghezza diversa. Poiché la lunghezza di una sequenza è un valore compreso tra 1 e n, tra i $ \sqrt{n} $ valori che assume ai almeno uno è maggiore o uguale a $ \sqrt{n} $.
QED, spero definitivamente.

Ho capito, grazie mille!