Sottosequenze monotòne

[talpuz]

Data una sequenza di $ n $ numeri reali $ \left(a_1,a_2,\hdots, a_{n}\right) $ mostrare che è sempre possibile trovare una sottosequenza monotòna di almeno $ \lceil \sqrt{n} \rceil $ elementi, ovvero è possibile trovare indici $ \left(i_1,i_2,\hdots, i_{\lceil \sqrt{n} \rceil}\right) $ tali che $ i_1 \leq i_2 \leq \hdots \leq i_{\lceil \sqrt{n} \rceil} $ e
$ a_{i_1} \leq a_{i_2} \leq \hdots \leq a_{i_{\lceil \sqrt{n} \rceil}} $
oppure
$ a_{i_1} \geq a_{i_2} \geq \hdots \geq a_{i_{\lceil \sqrt{n} \rceil}} $.

[Catraga]

E' un bel problema...
Per semplificare direi di considerare il caso in cui n sia un quadrato perfetto.
Negli altri casi basta estendere la successione con l'ultimo termine ripetuto fino a raggiungere un quadrato perfetto di elementi.

[Simo_the_wolf]

Questo è simpatico, anzi, carino....
comunque io procederei così: noto che se $ a_i \geq a_j $, denotando con $ M_i $ la lunghezza massima di una successione monotòna crescente che parte da $ a_i $ e con $ m_i $ la lunghezza massima di una successione monotòna decrescente che parte da $ a_i $, allora, si presentano 2 casi:
1) $ i>j $ che implica sicuramente $ M_i > M_j $
2) $ i<j $ che implica sicuramente $ m_i < m_j $
Quindi abbiamo che per ogni $ i \neq j $ le due coppie $ (M_i,m_i) $ e $ (M_j,m_j) $ sono diverse. Supponiamo ora per assurdo che non esistano successioni monotòne di lunghezza $ \geq \lceil \sqrt {n} \rceil $. Quindi dovrà essere $ 1 \leq M_i , m_i \leq \lceil \sqrt {n} \rceil -1 $. Tutte le coppie sono n ma i possibili valori per queste coppie sono $ (\lceil \sqrt {n} \rceil -1)^2 < n $ e quindi, dovendo ogni coppia essere diversa l'una dall'altra, abbiamo l'assurdo. Quindi c'è almeno una successione monotòna di lunghezza $ \geq \lceil \sqrt {n} \rceil $. Secondo lo stesso procedimento si può dimostare che se abbiamo almeno (n-1)(m-1)+1 numeri allora possiamo trovare o una successione monotòna crescente di n termini o una decrescente di m termini (o il contrario).

[Marco]

Dimostrami questa:

se $ a_i \geq a_j $,
1) $ i>j $ che implica sicuramente $ M_j > M_i $

Mi sembra che si possa aggiustare, ma che così come l'hai scritta non torni.

[Simo_the_wolf]

Sì scusate, avevo scambiato gli indici... (e non i mignoli... )