Ovviamente l'hint è palese

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 ha scritto: 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.
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.RiccardoKelso ha scritto: 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|$.
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.karlosson_sul_tetto ha scritto: 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.
È 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.RiccardoKelso ha scritto: 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.
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...RiccardoKelso ha scritto: 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
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..karlosson_sul_tetto ha scritto: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...
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 ha scritto:I miei esempi volevano dire che potrebbero esserci configurazioni in cui la [1.5] non è verificata che hanno lunghezza massima minore di ⌈n√⌉.
Si, c'è ancora questa parte che dev'essere dimostrataRiccardoKelso ha scritto: 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ù.
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 ha scritto: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 ha scritto:I miei esempi volevano dire che potrebbero esserci configurazioni in cui la [1.5] non è verificata che hanno lunghezza massima minore di ⌈n√⌉.