Tanti piccioni

[xXStephXx]

Abbiamo un nido molto lungo dentro il quale si trovano $n$ piccioni allineati, tutti di altezza diversa. Se ne vogliono considerare alcuni, mantenendo inalterato l'allineamento iniziale, in modo che le loro altezze formino una successione monotona (o crescente o decrescente). Qual è in funzione di $n$, il più grande $m$ tale che siamo sicuri di riuscire a formare una successione monotona con almeno $m$ piccioni?

Ovviamente l'hint è palese

[LucaMac]

aspetta, ma se sono allineati e tutti ad altezza diversa si ha che formano TUTTI insieme una successione monotona. Quindi $m=n$.

[karlosson_sul_tetto]

Penso intenda allineati=disposti lungo una retta. Vedi il problema cosi: hai una successione $a_1,a_2, a_3\ldots a_n$ di numeri (reali penso vada bene). Prendi un sottoinsieme $S\subseteq \{1,2,\ldots n\}$ in modo tale che la successione ordinata degli $a_i \; i\in S$ sia monotona crescente/decrescente. Qual è la cardinalità massima di $S$?

[LucaMac]

Ok grazie, allora sono scemo io

[xXStephXx]

Si è quella, però precisiamo. Se chiedessi la cardinalità massima sarebbe sempre $n=m$ xD Io voglio proprio essere sicuro di riuscire sempre a prenderne almeno $m$ a prescindere da come sia la successione

[RiccardoKelso]

Il titolo del post mi ha attratto in maniera irresistibile; di conseguenza, nonostante la muffa che ho dovuto togliere per scrivere:

Chiamiamo $S$ l'insieme dei piccioni. Un modo ottimale per minimizzare la lunghezza massima di una possibile funzione monotona consiste nel considerare un numero $C$ di cassetti (o piccionaie, volendo rimanere in tema) e distribuirvi all'interno gli elementi di $S$ nel modo più omogeneo possibile, in modo che $C\ge |C|$ (dove $|C|$ è il numero massimo di piccioni in una piccionaia). Inoltre, l'ordinamento delle piccionaie lungo il lungo nido e dei volatili all'interno delle prime è tale che una funzione monotona che comprenda almeno due bipedi all'interno della stessa piccionaia non possa comprenderne all'interno di altre piccionaie (condizione $[1]$), mentre una funzione che ne comprenda di diverse piccionaie non possa comprenderne più di uno per ognuna (condizione $[2]$). Un esempio, considerando che il numero corrisponda alla posizione del piccione nella classifica dei più alti, è fornito dall'ennupla $\{7,8,9,4,5,6,1,2,3\}$, la quale raffigura un caso di $n=9$, ovviamente. Risulta che per ogni $n$ il minimo $m$ sempre "disponibile" è dato da $min\{m \in \mathbb{N} | m \ge \sqrt{n}\}$.

Per giustificare il fatto che dichiaro questa disposizione come ottimale dico che se non valesse la condizione $[1]$ allora la funzione potrebbe comprendere un numero $k_1 > |C|$ di piccioni, il che va a nostro sfavore. Simile discorso nel caso in cui non valesse la $[2]$, in quanto la funzione potrebbe comprendere un numero $k_2 > C$. Prego chiunque di darmi una mano per quanto riguarda il "rigore matematico", dato che ancora non mi ci destreggio bene.

[karlosson_sul_tetto]

La risposta è giusta, ma la dimostrazione, come tu stesso hai notato, non è molto rigorosa...
"Ad occhio", si capisce che il caso peggiore è in cui ho $\sqrt{n}$ blocchi ognuno lungo $\sqrt{n}$ piccioni (mi fa senso misurare una lunghezza in piccioni D: ); per dimostrare che è il caso ottimale, dovresti descrivere un algoritmo o spiegare perché tutti gli altri casi sono migliori del tuo caso peggiore.
Per esempio, non è molto chiaro (almeno a me) come scegli gli insiemi $C$. Se scelgo $n$ insiemi ciascuno di un elemento, le condizioni sono soddisfatte: $n\geq 1$, una sequenza monotona che prende due piccioni di una piccionaia non prende piccioni di altre piccionaie, una sequenza monotona tra piccionaie diverse prende al massimo un piccione per piccionaia; tuttavia in questo modo non ricavi niente. Cosa ancora più importante: sei sicuro che una tale distribuzione esista sempre? Con (2,7,4,6,3,1,9,8,5) qual è? Poi, se hai (1,2,3,4), in qualunque modo tu costruisca due insiemi, puoi trovare una successione che prende tutti e 4 gli elementi e che non soddisfa le tue condizioni.

Ora, siccome con questi insiemi non siamo riusciti a dimostrare di essere nel caso peggiore (perché non riusciamo a passare da un caso migliore a quello peggiore o perché questi insiemi non esistono), serve un'altra prospettiva. Prova a scegliere gli insiemi non partendo da quello che dovrebbero essere nel caso peggiore, ma da quelli di una configurazione generica scelti "nel modo giusto". Questi insiemi coincidono con quelli definiti da te nel caso peggiore, ma devi definirli in un altro modo, per le loro proprietà "interne", non quelle "esterne" (ovvero gruppi disgiunti di insiemi crescenti).

[RiccardoKelso]

In effetti quel mio $C\ge |C|$ è un'autentica bruttura. Tuttavia raddoppio al posto di lasciare e dico:
Ripensandoci bene la $[1]$ implica la $[2]$ e viceversa, useremo quindi la $[1.5]$ per comodità.
Il caso in cui la funzione possa comprendere il minor numero di piccioni è quello in cui vale la $[1.5]$ e allo stesso tempo la differenza $D$ tra $C$ e $|C|$ è minima. Quest'ultima può sempre essere $D\le 1$ e di conseguenza si ha che nel caso in cui può essere 0 ($n=a^2$ con $a$ naturale) lo è, e per le conseguenze che chiamiamo $[3]$ (si veda dopo) si tratta del caso peggiore per la nostra funzione; identica cosa per quando $D=1$, anche se in modo "meno peggiore" rispetto al caso in cui $D=0$. Però ricordiamo che $D$ è minima, di conseguenza se è 1 significa che non può essere 0, quindi il tutto dovrebbe stare in piedi.

Quelle che chiamo $[3]$ sono le conseguenze sulle possibili funzioni nel caso in cui la $[1.5]$ non si verifichi; le ripeto cercando di essere il più chiaro possibile. Con $C=|C|$ avremmo la possibilità di comprendere un numero maggiore di uno dei due tra $|C|$ e $C$ e quindi ovviamente anche dell'altro, mentre se è verificata avremmo che $m_{max}=C=|C|$. Allo stesso tempo, con $D=1$ si ha che $m(ver)_{max}=max\{C,|C|\}$ se $[1.5]$ è verificata, mentre in caso contrario avremo ovviamente $m(non\ ver)_{max}>max\{C,|C|\}$.

Cosa ancora più importante: sei sicuro che una tale distribuzione esista sempre? Con (2,7,4,6,3,1,9,8,5) qual è? Poi, se hai (1,2,3,4), in qualunque modo tu costruisca due insiemi, puoi trovare una successione che prende tutti e 4 gli elementi e che non soddisfa le tue condizioni.

Tento di specificare meglio: non è assolutamente necessario che esista sempre. Semplicemente, nel caso in cui non esiste, la $[1.5]$ non è verificata e di conseguenza avremo che $m_{max}=m(non\ ver)_{max}>m(ver)_{max}$, cosa che infatti avviene nell'ennupla da te fornita. Per questo motivo unito con le richieste del problema, penso che dovremmo appunto non considerare quei casi dato che non minimizzano $m_{max}$.

[karlosson_sul_tetto]

Quelle che chiamo $[3]$ sono le conseguenze sulle possibili funzioni nel caso in cui la $[1.5]$ non si verifichi; le ripeto cercando di essere il più chiaro possibile. Con $C=|C|$ avremmo la possibilità di comprendere un numero maggiore di uno dei due tra $|C|$ e $C$ e quindi ovviamente anche dell'altro, mentre se è verificata avremmo che $m_{max}=C=|C|$.

Il problema sta qui, almeno per come hai scritto la dimostrazione. Se ad un certo punto in uno dei cassettoni avessi (20,40,30), potresti collegare ai numeri successivi sia una successione crescente (20,40), sia una decrescente (40,30). Però le condizioni sono che i numeri siano maggiori di 40 e minori di 30, ma chi ti dice che in quei intervalli c'è una successione crescente/decrescente già lunga $|C|$? Per esempio, se i gruppi fossero da 6 elementi, potresti avere un altro cassettone con (15,10,5,45,50,65); in questo modo avresti una successione che passa tra due cassettoni diversi ma che ha una lunghezza minore di 6.
Si potrebbe dire "allora gli altri cassettoni devono essere compresi in un intervallo tot e tot altrimenti riesco a prendere questa sequenza più grande di $|C|=6$; ma se sono in questo intervallo allora ne ho quest'altra più grande", però cosi è un po' come procedere a tentativi, bisognerebbe trovare una dimostrazione che copra tutti i casi e tutti gli n...

Si può certamente fare una dimostrazione distinguendo bene tutti i casi possibili per n generico, però personalmente non avrei idea di come farla.

[RiccardoKelso]

Il problema sta qui, almeno per come hai scritto la dimostrazione. Se ad un certo punto in uno dei cassettoni avessi (20,40,30), potresti collegare ai numeri successivi sia una successione crescente (20,40), sia una decrescente (40,30). Però le condizioni sono che i numeri siano maggiori di 40 e minori di 30, ma chi ti dice che in quei intervalli c'è una successione crescente/decrescente già lunga $|C|$? Per esempio, se i gruppi fossero da 6 elementi, potresti avere un altro cassettone con (15,10,5,45,50,65); in questo modo avresti una successione che passa tra due cassettoni diversi ma che ha una lunghezza minore di 6.

Non sono sicuro di aver capito quello che intendi, comunque: giustamente dici che non si può procedere per tentativi, e si tratta di un'affermazione incontestabile. Infatti mi chiedo per quale motivo proponi esempi in cui le condizioni di cui sopra non sono verificate; io mi limito ad enunciare determinate condizioni che identificano un certo "limite superiore" per la lunghezza della funzione. Le condizioni non sussistono? (come negli esempi da te citati) Non c'è problema: si tratta di casi in cui la funzione assume valori superiori a quello minimo, quindi non ci interessa. Mi rendo conto che mi manca la parte "dimostrare che non sia possibile abbassare ulteriormente il limite massimo della funzione", ma oltre a questo il resto dovrebbe stare perlomeno in piedi, penso.

[xXStephXx]

Non sono riuscito a capire niente, non ho neanche capito quale freccia stavi facendo. Non mi sembra che tu abbia dimostrato che $\sqrt n$ lo riesci sempre ad ottenere (che poi sarebbe $\lceil \sqrt n \rceil$). Forse però hai dimostrato che non hai la certezza di ottenerne di più, almeno nel caso dei quadrati perfetti.

[karlosson_sul_tetto]

Le condizioni non sussistono? (come negli esempi da te citati) Non c'è problema: si tratta di casi in cui la funzione assume valori superiori a quello minimo, quindi non ci interessa.

È su questo punto che non sono d'accordo (ed è anche il motivo degli esempi che ho proposto). Tu dici che se è verificata la $[1.5]$, allora riesci a trovare una sequenza monotona lunga $\lceil \sqrt n \rceil$ e che ci sono casi in cui è effettivamente il minimo possibile. Se invece la $[1.5]$ non è verificata, allora si verifica uno dei casi descritti da $[3]$. Io dico che i casi da te descritti non sono tutti i possibili e che ce ne potrebbero essere alcuni che assumono solo valori inferiori al minimo.

Per esempio, riguardo alla tua affermazione:

Con $C=|C|$ avremmo la possibilità di comprendere un numero maggiore di uno dei due tra $|C|$ e $C$ e quindi ovviamente anche dell'altro

Nell'esempio precedente, quello con un cassetto da $(20,40,30, \ldots)$ e l'altro da $(15,10,5,45,50,55)$, si ha che le condizioni non sono rispettate, ma la successione che comprende tanti elementi di cassetti diversi ha lunghezza 5. La funzione, in questa piccola parte, assume un valore inferiore a quello minimo (perché avevo presupposto i cassetti da 6 elementi e quindi $|C|=6 \geq 5$. Questo contraddice quello che hai detto...

Il problema chiede di "trovare il minimo del massimo della funzione"; tu hai dimostrato che per una serie di casi (dove è verificata $[1.5]$), il massimo della funzione è inferiore a $\lceil \sqrt {n} \rceil$. Non voglio dire che questa parte della dimostrazione è sbagliata, ma che è una piccola parte della soluzione dell'intero problema, ovvero dimostrare che non ci sono configurazioni in cui "ogni sequenza ha lunghezza $< \lceil \sqrt n \rceil$.
Questa è la cosa che dici tu alla fine, "dimostrare che non sia possibile abbassare ulteriormente il limite massimo della funzione", che è una bella gatta da pelare. I miei esempi volevano dire che potrebbero esserci configurazioni in cui la $[1.5]$ non è verificata che hanno lunghezza massima minore di $\lceil\sqrt{n}\rceil$.

[RiccardoKelso]

Nell'esempio precedente, quello con un cassetto da (20,40,30,…) e l'altro da (15,10,5,45,50,55), si ha che le condizioni non sono rispettate, ma la successione che comprende tanti elementi di cassetti diversi ha lunghezza 5. La funzione, in questa piccola parte, assume un valore inferiore a quello minimo (perché avevo presupposto i cassetti da 6 elementi e quindi |C|=6≥5. Questo contraddice quello che hai detto...

Non penso che contraddica, dato che il fatto che la funzione possa assumere valori inferiori non toglie che ne assuma di superiori, il che succede quando le condizioni non sono verificate; noi cerchiamo di minimizzare il massimo, il fatto che un caso con massimo non minimizzato comprenda anche minimi più o meno bassi poco importa..

Il resto del discorso permane: ancora "non sappiamo per certo" se esistano o meno determinate condizioni tali che se rispettate abbassino il massimo ancora di più.

I miei esempi volevano dire che potrebbero esserci configurazioni in cui la [1.5] non è verificata che hanno lunghezza massima minore di ⌈n√⌉.

Lo dici nel senso che sei sicuro che ci siano o nel senso che va dimostrato che non ci sono? Tralasciando un attimo il valore $\lceil \sqrt {n} \rceil$, mi viene da dire che una sequenza lunga $n_1$ che rispetta la $[1.5]$ avrà sempre massimo inferiore rispetto a una sequenza lunga sempre $n_1$ ma che non la rispetta, questo proprio per la natura stessa delle condizioni.. Il discorso permane sulla (non?) esistenza di ulteriori condizioni in grado di abbassare il massimo oltre le $[1.5]$

[karlosson_sul_tetto]

Il resto del discorso permane: ancora "non sappiamo per certo" se esistano o meno determinate condizioni tali che se rispettate abbassino il massimo ancora di più.

Si, c'è ancora questa parte che dev'essere dimostrata

I miei esempi volevano dire che potrebbero esserci configurazioni in cui la [1.5] non è verificata che hanno lunghezza massima minore di ⌈n√⌉.

Lo dici nel senso che sei sicuro che ci siano o nel senso che va dimostrato che non ci sono? Tralasciando un attimo il valore $\lceil \sqrt {n} \rceil$, mi viene da dire che una sequenza lunga $n_1$ che rispetta la $[1.5]$ avrà sempre massimo inferiore rispetto a una sequenza lunga sempre $n_1$ ma che non la rispetta, questo proprio per la natura stessa delle condizioni.. Il discorso permane sulla (non?) esistenza di ulteriori condizioni in grado di abbassare il massimo oltre le $[1.5]$

Intendo che andrebbe dimostrato che non ci siano. A intuito sembra ragionevole che le stringhe che minimizzano il massimo siano quelle che soddisfano la $[1.5]$, e questo andrebbe dimostrato. Quello che cercavo di dire è che senza una dimostrazione completa non si può dire che quelle che soddisfano la $[1.5]$ hanno proprio il massimo minimo.

[RiccardoKelso]

Ora siamo d'accordo
Se mi viene particolarmente voglia ci provo