Tanti piccioni

[xXStephXx]

Il titolo del post mi ha attratto in maniera irresistibile

Significa che dovresti usare pigeonhole Secondo me per vedere la strada giusta conviene fare come faresti nella realtà, supponendo di voler prendere la più lunga sequenza idonea. Ovviamente non guarderesti tutti i piccioni insieme andando a tentativi, sarebbe troppo dispersivo... Magari cominci considerando solo quelli più a sinistra, ignorando tutti gli altri... e via via ne aggiungi uno nuovo vedendo cosa si modifica.

[gpzes]

Il titolo del post mi ha attratto in maniera irresistibile

Significa che dovresti usare pigeonhole Secondo me per vedere la strada giusta conviene fare come faresti nella realtà, supponendo di voler prendere la più lunga sequenza idonea. Ovviamente non guarderesti tutti i piccioni insieme andando a tentativi, sarebbe troppo dispersivo... Magari cominci considerando solo quelli più a sinistra, ignorando tutti gli altri... e via via ne aggiungi uno nuovo vedendo cosa si modifica.

beh si...
ad essere sincero avevo fatto ragionamento leggermente diverso..inizio dai due più a sinistra..essi creano tre intervalli di altezze..allora devo sistemare n-2 elementi in tre fasce..ne esisterà una con almeno $ \lfloor {(n-2)/3}\rfloor+1 $ elementi....

[RiccardoKelso]

Si tratta di una strada che avevo provato inizialmente che però non mi ha portato da nessuna parte. Sfortunatamente ancora adesso non riesco a concretizzare l'idea, chiedo quindi umilmente che qualcuno espliciti

[xXStephXx]

Numeri i piccioni da $1$ a $n$ (da sinistra verso destra). All' $i-esimo$ piccione ci associ una coppia di naturali $(a_i, b_i)$ dove $a_i$ è la lunghezza della più lunga sequenza crescente che puoi formare prendendo l'$i-esimo$ piccione e guardando solo quelli alla sua sinistra, e analogamente $b_i$ è la lunghezza della più lunga decrescente. Ora facendo qualche considerazione sulle $(a_i,b_i)$ ottieni facilmente la tesi.

[EvaristeG]

Beh, insomma, c'è anche da dire che una minima variante di questo problema appare ad ogni lezione di P medium (o quasi) e ad alcune lezioni di P basic negli ultimi 5 o 6 Senior...

[RiccardoKelso]

Tutte cose a me note.

[EvaristeG]

Beh, l'onere di informarsi sta a voi, puelli carissimi.
Non è difficile notare il thread Senior 2015 con 41 pagine in Olimpiadi della Matematica...magari a quel punto uno si domanda cosa sia questo "senior" e usa un po' la funzione Cerca del forum.
Diciamo che il fatto che siano online le lezioni degli ultimi 9 anni (cioè file video e pdf per un totale di più di 800 ore di lezione su argomenti da base ad avanzati) dovrebbe essere una delle prime cose che sfrutta chi vuole ben prepararsi alle Olimpiadi.

BTW, in quello che ha scritto xXStephXx c'è un sacco di roba che va espansa... al lavoro, se non avevate mai visto questo genere di soluzione

[erFuricksen]

Propongo una formalizzazione del problema che dovrebbe (spero) andare bene per risolverlo

Ci basta immaginare l'insieme dei piccioni come un ordine parziale in cui, messi i piccioni in fila, esiste una relazione dal piccione A al piccione B se A viene prima di B in fila e A è più alto di B. In questo modo è facile vedere che una catena rappresenta una successione di piccioni crescente, mentre un'anticatena rappresenta una successione di piccioni decrescente. A questo punto per il Teorema di Dilworth posso dire che se esiste una partizione in $k$ anticatene al minimo allora esisterà una catena di almeno $k$ elementi. Vediamo allora che se $k \ge \sqrt{n}$ allora esiste sicuramente una catena di almeno $\sqrt{n}$ piccioni, mentre se $k < \sqrt{n}$ allora per pigeonhole almeno un'anticatena conterrà almeno $\sqrt{n}$ piccioni. E così si finisce, basta solo verificare che questo sia il minimo creando delle anticatene di cardinalità uguale fra loro nei casi in cui è possibile.

[xXStephXx]

Diciamo che era pensato per non "conoscere" esplicitamente Dilworth