I Cavalieri e il Mago

axpgn
Un numero infinito di Cavalieri (tutti di differente altezza) è allineato in riga di fronte al Mago.

Provare che il Mago può dire ad alcuni di loro di uscire dalla linea, in modo tale che nella linea rimanga un numero infinito di Cavalieri e che tutti questi rimasti nella linea siano ordinati in altezza crescente (o decrescente che è lo stesso :D )


Versione al finito (più semplice ... forse :D )

I numeri $1, 2, 3, ..., 100, 101$ sono scritti in linea in un ordine qualsiasi.

Provare che è sempre possibile cancellare $90$ di questi numeri in modo tale che gli $11$ restanti siano ordinati in modo crescente (o decrescente).


Cordialmente, Alex

Risposte
Studente Anonimo
Studente Anonimo
Non saprei davvero come spiegarlo in modo più semplice, cosa non capisci?

axpgn
Sei troppo complicato, tutti quegli indici che vanno e vengono, fanno giri immensi e poi ritornano (cit. :D )
Mi perdo sempre prima di arrivare in fondo :-D
D'altro canto ho la sensazione che la tua e la mia soluzione abbiano molto in comune; magari va a finire che è la stessa cosa :lol:

E allora eccola ...




Cordialmente, Alex

Studente Anonimo
Studente Anonimo
Eh sì è praticamente la stessa cosa :wink: abbiamo solo invertito crescente con decrescente

Usando circa la tua notazione per spiegare la mia

Studente Anonimo
Studente Anonimo
Poi fai tu cosa è meglio leggere :lol: :lol:

axpgn
@3m0o



Cordialmente, Alex

gabriella127
"axpgn":


E allora eccola ...






La spiegazione di axpgn è chiara (non ho ancora letto quella di 3m0o), però mi sembra ci vorrebbe qualche spiegazione in più (io me la sono data, almeno mi pare):


axpgn
@gabriella




Cordialmente, Alex

gabriella127






axpgn
L'avevo postata stamattina in mezzo alla risposta a 3m0o quindi è probabile che ti sia sfuggita, non l'avevo postata allora per ... lasciare i dettagli al lettore :-D

gabriella127
Ok :D

ViciousGoblin
A me l'argomento di axpng non torna :( .


Però forse ho capito male. Devo confessare poi che ho letto frettolosamente i messaggi successivi, in cui però non mi pare di vedere risolto il punto che sollevo sopra. Se invece la spiegazione mi è sfuggita mi scuso.

Sono invece d'accordo sulla prova di 3mOo che direi essere una dimostrazione del teorema di E.S.

gabriella127
"ViciousGoblin":
A me l'argomento di axpng non torna :( .


La riga grassettata sopra sembra suggerire che gli elementi della seconda sottosequenza siano tutti più grandi di quelli della prima, cioè $a_i\leq b_j$ (e così via per le sottosequenze successive). Questo non mi pare vero, e nemmeno mi sembra che $a_1\leq b_1$. Mettiamo per esempio che la sequenza originale cominci con $4,2,3,1$, allora $a_1=4$, $a_2=2$, $a_3=1$ mentre $b_1=3$. Dunque non mi pare chiaro come trovo la sottosequenza crescente (si farà naturalmente ma mi pare che la cosa si complichi).

Però forse ho capito male. Devo confessare poi che ho letto frettolosamente i messaggi successivi, in cui però non mi pare di vedere risolto il punto che sollevo sopra. Se invece la spiegazione mi è sfuggita mi scuso.
[/spoiler][/quote]


ViciousGoblin
@gabriella
Ci sta che come dici tu la cosa si sistemi. Però...

axpgn
Eh, però se non leggete tutti i messaggi :? :lol:
Ora non riesco a citare un mio messaggio precedente ma provate a leggere il mio post delle 15:20 di oggi :D

gabriella127
"ViciousGoblin":
@gabriella
Ci sta che come dici tu la cosa si sistemi. Però...


Scusami, ho sbagliato a scrivere, ho modificato il messaggio precedente (ero uscita e sono tornata a casa apposta perché mi sono resa conto che avevo sbagliato :-D ).

Volevo dire che ogni sottosequenza contiene tutti elementi maggiori del minimo della sequenza precedente (altrimenti farebbero parte della sequenza precedente.
Quindi, male che vada, per costruire la sequenza crescente basta prendere i minimi.

Poi rileggo con calma, ora devo uscire...


@ axpgn se ti va, puoi ripostare la soluzione completa tutta insieme, non spezzettata, dopo uno squillo di tromba? Se no andiamo in confusione, non è facile leggere tutto, il thread è lungo...

axpgn
Ci provo ... :D



Cordialmente, Alex

P.S.: a proposito di indici :D
In questa dimostrazione che ho scritto li ho usati anch'io per maggiore chiarezza ma non sarebbe necessario :wink:

gabriella127
Grazie, poi rileggo il tutto con calma, se no dico fesserie :)

ViciousGoblin
"gabriella127":
[quote="ViciousGoblin"]@gabriella
Ci sta che come dici tu la cosa si sistemi. Però...


Scusami, ho sbagliato a scrivere, ho modificato il messaggio precedente (ero uscita e sono tornata a casa apposta perché mi sono resa conto che avevo sbagliato :-D ).

Volevo dire che ogni sottosequenza contiene tutti elementi maggiori del minimo della sequenza precedente (altrimenti farebbero parte della sequenza precedente.
Quindi, male che vada, per costruire la sequenza crescente basta prendere i minimi.

Poi rileggo con calma, ora devo uscire...


@ axpgn se ti va, puoi ripostare la soluzione completa tutta insieme, non spezzettata, dopo uno squillo di tromba? Se no andiamo in confusione, non è facile leggere tutto, il thread è lungo...[/quote]
Hai ragione! Così funziona.

Mi spiace avrei dovuto leggere bene i messaggi precedenti. Ma l'interazione è più divertente...

axpgn
Ma io no? :cry: :-D :-D

gabriella127
"axpgn":
Ma io no? :cry: :-D :-D


Ti stiamo trascurando? :D

Ma no, ma no! Stavo giusto per rispondere a Viciousgoblin che è difficile leggere tutto in thread così lunghi, e che non ho ancora letto la soluzione completa che hai postato, l'ultima parte, e quella di 3m0o.

Quindi non finisce qui il thread!

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.