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 )


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

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

[Quinzio]

Direi che si risolve con il teorema di Bolzano Weierstrass,
https://it.wikipedia.org/wiki/Teorema_d ... eierstrass

[gabriella127]

@ Quinzio

Avevo pensato anche io a Bolzano Weierstrass, ma nel senso di inventarmi qualche teorema tipo 'da ogni successione con termini tutti diversi si può estrarre una sottosuccessione crescente' ma Bolzano Weierstrass? Dove sta la successione limitata? Possono essere cavalieri altissimi sempre più alti.

[ViciousGoblin]

"gabriella127":@ Quinzio

Avevo pensato anche io a Bolzano Weierstrass, ma nel senso di inventarmi qualche teorema tipo 'da ogni successione con termini tutti diversi si può estrarre una sottosuccessione crescente' ma Bolzano Weierstrass? Dove sta la successione limitata? Possono essere cavalieri altissimi sempre più alti.

Ma allora trovi una sottosuccessione crescente che diverge a più infinito

[axpgn]

Eviterei di usare teoremi preconfezionati, per vari motivi ma in primis perché è un problema per i ragazzi del biennio che si può risolvere logicamente senza grandi difficoltà

[gabriella127]

"ViciousGoblin":[quote="gabriella127"]@ Quinzio

Avevo pensato anche io a Bolzano Weierstrass, ma nel senso di inventarmi qualche teorema tipo 'da ogni successione con termini tutti diversi si può estrarre una sottosuccessione crescente' ma Bolzano Weierstrass? Dove sta la successione limitata? Possono essere cavalieri altissimi sempre più alti.

Ma allora trovi una sottosuccessione crescente che diverge a più infinito

[/quote]

Non ho capito. Volevo dire che non si può usare Bolzano Weierstrass perché la successione non è detto che sia limitata.
Se non è limitata si può trovare una sottosuccessione crescente, ok.
Ma se è limitata, cosa ci dice che c'è una sottosuccesione crescente? Mica Bolzano Weiestrass ce lo dice.

[gabriella127]

"axpgn":Eviterei di usare teoremi preconfezionati, per vari motivi ma in primis perché è un problema per i ragazzi del biennio che si può risolvere logicamente senza grandi difficoltà

In effetti non dovrebbero servire visto che c'è il caso finito.

[ViciousGoblin]

"gabriella127":[quote="ViciousGoblin"][quote="gabriella127"]@ Quinzio

Avevo pensato anche io a Bolzano Weierstrass, ma nel senso di inventarmi qualche teorema tipo 'da ogni successione con termini tutti diversi si può estrarre una sottosuccessione crescente' ma Bolzano Weierstrass? Dove sta la successione limitata? Possono essere cavalieri altissimi sempre più alti.

Ma allora trovi una sottosuccessione crescente che diverge a più infinito

[/quote]

Non ho capito. Volevo dire che non si può usare Bolzano Weierstrass perché la successione non è detto che sia limitata.
Se non è limitata si può trovare una sottosuccessione crescente, ok.
Ma se è limitata, cosa ci dice che c'è una sottosuccesione crescente? Mica Bolzano Weiestrass ce lo dice.

[/quote]

No certo. Bolzano Weierstrass ti dà una sottosuccessione convergente. Da qui con un po' di pazienza estrai una ulteriore sottosuccessione monotona. E'chiaro che non era questo il metodo auspicato... però anche a me era venuto così.

[gabriella127]

"ViciousGoblin": Bolzano Weierstrass ti dà una sottosuccessione convergente. Da qui con un po' di pazienza estrai una ulteriore sottosuccessione monotona. E'chiaro che non era questo il metodo auspicato... però anche a me era venuto così.

Scusami se sono dura di comprendonio, dalla sottosuccessione convergente come estrai la successione monotona? Non c'è nulla in Bolzano Weiestrass che ce lo garantisce. Intendo strettamente crescente, perché questo dice il problema di axpgn.
Prendi una successione fatta solo di $1$ e di $2$, limitata, Bolzano Weiserstrass ci dice che c'è sottosuccessione convergente, e in effetti c'è .
Dopodiché, picche, mica puoi estrarre una successione strettamente crescente.

Vabbe', forse non ci stiamo capendo, bisogna specificare che si tratta di una successione con termini tutti diversi, come nel problema.

[ViciousGoblin]

"gabriella127":

Scusami se sono dura di comprendonio, dalla sottosuccessione convergente come estrai la successione monotona? Non c'è nulla in Bolzano Weiestrass che ce lo garantisce. Intendo strettamente crescente, perché questo dice il problema di axpgn.
Prendi una successione fatta solo di $1$ e di $2$, limitata, Bolzano Weiserstrass ci dice che c'è sottosuccessione convergente, e in effetti c'è .
Dopodiché, picche, mica puoi estrarre una successione strettamente crescente.

Vabbe', forse non ci stiamo capendo, bisogna specificare che si tratta di una successione con termini tutti diversi, come nel problema.

Scusa Gabriella. Sono stato un po' evasivo nei dettagli anche perché scrivevo da cellulare. Ho anche cercato di dire che non c'è solo Bolzano-Weierstrass, ma comunque un po' di magheggi con le successioni. Ti elenco i passi che io avevo in mente, anche se mi pare che ci siamo sostanzialmente capiti.

Prendiamo una successione $(a_n)$ di numeri positivi.

1) Se $(a_n)$ non è limitata puoi costruire una sottosuccessione strettamente crescente che tende all'infinito;
2) Se $(a_n)$ è limitata puoi trovare una sua sottosuccessione $(b_n)$ che tende a un limite finito $l$ (Bolzano-Weierstrass);
3) Se $b_n\to l$ allora esiste una sottosuccessione di $(b_n)$ monotona - in effetti ci sono tre casi
a) $b_n$ è definitivamente costante;
b) $b_n>l$ per infiniti $n$;
c) $b_n nel caso a) la tesi è ovvia, negli altri due usi la definizione di limite (un po' come dovresti fare nel punto 1) )
4) Se la successione originaria aveva tutti valori diversi, allora alla fine hai una sottosuccessione strettamente monotona.

Sono invece bloccato nel dimostrare il caso finito... (e non capisco neanche come abbia a che fare con quello infinito).
Mi vengono in mente solo cose complicate...

[ViciousGoblin]

E' questo ?
https://en.wikipedia.org/wiki/Erd%C5%91 ... es_theorem
Mi pare che prendendo $r=s=11$ se ne deduca quello che dice axpng.
Boh...

[Quinzio]

Versione al finito.

Si prende la sequenza composta dai numeri da $1$ a $100$ disposta in questo modo:
$10, 9, ..., 2, 1, 20, 19, ..., 12, 11, 30, 29, ..., ..., ..., 100, 99, 92, 91$
(grafico in fondo)
che sarebbe con matlab: mod(100-a,10) + floor((a-1)./10)*10 + 1

Premetto che quanto scritto in seguito e' molto piu' facile e intuitivo da capire in forma grafica che come spiegazione testuale.
Comunque sia...

Questa sequenza (e la sua simmetrica) sono le uniche due a non avere una sotto-sequenza monotona lunga 11.
Per vedere che le due sequenze sono le uniche si possono invertire 2 numeri che appartengono alla stessa sotto-sequenza discendente.
Se si prendono i due numeri invertiti e un numero per ciascuno delle altre 9 sotto-sequenze discendenti, questa e' una sotto-sequenza ascendente di 11 numeri.
Se invece si invertono 2 numeri prendendoli da 2 sotto-sequenze discendenti diverse, si crea almeno una sotto-sequenza discendente di 11 numeri composta da uno dei due numeri scambiati e una sotto-sequenza discendente successiva.

Ora aggiungiamo un ulteriore numero $ n$ alla sequenza.
Per fare questo prendiamo la sequenza originale di $100$ numeri e sostituiamo tutti i numeri $k \ge n$ con $k+1$.
Poi aggiungiamo il numero $n$ ottenendo una sequenza di $101$ numeri.
Se $n$ e' stato aggiunto nella posizione successiva a $n+1$ allora abbiamo creato una sotto-sequenza discendente di 11 numeri consecutivi.
Se $n$ e' stato aggiunto in un'altra posizione, ma sempre all'interno della sotto-sequenza discendente di $n+1$, allora si crea una sotto-sequenza ascendente di 11 numeri.
Se $n$ e' in altra posizione ancora, si crea una sotto-sequenza discendente si 11 numeri composta a da $n$ e da una sotto-sequenza discendente in posizione successiva a $n$

[gabriella127]

"ViciousGoblin":[quote="gabriella127"]

Scusami se sono dura di comprendonio, dalla sottosuccessione convergente come estrai la successione monotona? Non c'è nulla in Bolzano Weiestrass che ce lo garantisce. Intendo strettamente crescente, perché questo dice il problema di axpgn.
Prendi una successione fatta solo di $1$ e di $2$, limitata, Bolzano Weiserstrass ci dice che c'è sottosuccessione convergente, e in effetti c'è .
Dopodiché, picche, mica puoi estrarre una successione strettamente crescente.

Vabbe', forse non ci stiamo capendo, bisogna specificare che si tratta di una successione con termini tutti diversi, come nel problema.

Scusa Gabriella. Sono stato un po' evasivo nei dettagli anche perché scrivevo da cellulare. Ho anche cercato di dire che non c'è solo Bolzano-Weierstrass, ma comunque un po' di magheggi con le successioni. Ti elenco i passi che io avevo in mente, anche se mi pare che ci siamo sostanzialmente capiti.

Prendiamo una successione $(a_n)$ di numeri positivi.

1) Se $(a_n)$ non è limitata puoi costruire una sottosuccessione strettamente crescente che tende all'infinito;
2) Se $(a_n)$ è limitata puoi trovare una sua sottosuccessione $(b_n)$ che tende a un limite finito $l$ (Bolzano-Weierstrass);
3) Se $b_n\to l$ allora esiste una sottosuccessione di $(b_n)$ monotona - in effetti ci sono tre casi
a) $b_n$ è definitivamente costante;
b) $b_n>l$ per infiniti $n$;
c) $b_n nel caso a) la tesi è ovvia, negli altri due usi la definizione di limite (un po' come dovresti fare nel punto 1) )
4) Se la successione originaria aveva tutti valori diversi, allora alla fine hai una sottosuccessione strettamente monotona.

Sono invece bloccato nel dimostrare il caso finito... (e non capisco neanche come abbia a che fare con quello infinito).
Mi vengono in mente solo cose complicate...

[/quote]

Grazie, grazie, sì s' era questo, ci eravamo capiti.

Quanto al caso finito, ci ho pensato dieci minuti e mi usciva il fumo dalle orecchie, facendo tentativi strampalati. Domani provo a ripensarci.
Io in questi giochi per lo più cerco il coniglio dal cilindro, cioè cerco idee super semplici, ma nascoste, che risolvono senza lungaggini. Spesso il coniglio c'è, alle volte no... bisogna fare trafile lunghe e complicate.
A me piacciono in giochi con l'idea 'geniale' semplice, ma difficile da vedere.

[gabriella127]

Bah, axpgn dice che lo possono risolvere senza difficoltà ragazzi del biennio, qua vedo teoremi vari.

Per fortuna non ha aggiunto 'ragazzi del biennio per quanto scemi', che già così axpgn mi fa sentire abbastanza cretina

[ViciousGoblin]

"Quinzio":

Versione al finito.

Si prende la sequenza composta dai numeri da $1$ a $100$ disposta in questo modo:
$10, 9, ..., 2, 1, 20, 19, ..., 12, 11, 30, 29, ..., ..., ..., 100, 99, 92, 91$
(grafico in fondo)
che sarebbe con matlab: mod(100-a,10) + floor((a-1)./10)*10 + 1

Premetto che quanto scritto in seguito e' molto piu' facile e intuitivo da capire in forma grafica che come spiegazione testuale.
Comunque sia...

Questa sequenza (e la sua simmetrica) sono le uniche due a non avere una sotto-sequenza monotona lunga 11.
Per vedere che le due sequenze sono le uniche si possono invertire 2 numeri che appartengono alla stessa sotto-sequenza discendente.
Se si prendono i due numeri invertiti e un numero per ciascuno delle altre 9 sotto-sequenze discendenti, questa e' una sotto-sequenza ascendente di 11 numeri.
Se invece si invertono 2 numeri prendendoli da 2 sotto-sequenze discendenti diverse, si crea almeno una sotto-sequenza discendente di 11 numeri composta da uno dei due numeri scambiati e una sotto-sequenza discendente successiva.

Ora aggiungiamo un ulteriore numero $ n$ alla sequenza.
Per fare questo prendiamo la sequenza originale di $100$ numeri e sostituiamo tutti i numeri $k \ge n$ con $k+1$.
Poi aggiungiamo il numero $n$ ottenendo una sequenza di $101$ numeri.
Se $n$ e' stato aggiunto nella posizione successiva a $n+1$ allora abbiamo creato una sotto-sequenza discendente di 11 numeri consecutivi.
Se $n$ e' stato aggiunto in un'altra posizione, ma sempre all'interno della sotto-sequenza discendente di $n+1$, allora si crea una sotto-sequenza ascendente di 11 numeri.
Se $n$ e' in altra posizione ancora, si crea una sotto-sequenza discendente si 11 numeri composta a da $n$ e da una sotto-sequenza discendente in posizione successiva a $n$

Scusa. Sembra abbastanza plausibile che quelle due sequenze siano le uniche a non avere una sotto-sequenza monotona lunga 11, però non capisco bene la dimostrazione. Non mi pare ovvio che la tesi segua dal fatto che scambiando due elementi allora si crea una sotto sequenza monotona lunga 11. Chi mi dice che facendo altri scambi non si trovi un'altra sequenza, diversa da quelle due, che di nuovo non ha sottosequenze monotone lunghe 11?

[Quinzio]

"gabriella127":Bah, axpgn dice che lo possono risolvere senza difficoltà ragazzi del biennio, qua vedo teoremi vari.

Per fortuna non ha aggiunto 'ragazzi del biennio per quanto scemi', che già così axpgn mi fa sentire abbastanza cretina

Eh ma i ragazzini del biennio hanno la mente fresca, non come quelli over-anta.

Scherzi a parte, di quelli del biennio (di cosa poi, delle superiori ?) te lo risolve 1 su 1000, di quelli che hanno la mamma prof di matematica e il papa' ingegnere.

[axpgn]

@gabriella
Eh, beh, i ragazzi russi di una volta
È un problema tratto da gare per studenti del 9° e 10° grado che dovrebbero corrispondere, grosso modo, a 14/15 anni (tra l'altro ho scoperto che la versione infinita è per quelli dell'ottavo grado, avete ragione voi, è ritenuta più complicata quella sul finito )
Peraltro, come dice Quinzio, non è che tutti i quindicenni siano in grado di risolverli
Le soluzioni non sono affatto complicate, non è necessario tirare in ballo teoremi importanti (quello citato da ViciousGoblin piacerebbe sicuramente a 3m0o ), soprattutto dopo che uno le ha lette
(comunque quella di Quinzio non l'ho capita, my fault, ed ho lo stesso dubbio di ViciousGoblin).


Cordialmente, Alex

[hydro1]

Se il sup dell'insieme delle altezze è infinito allora è facile, ed è facile formalizzare in termini elementari. In caso contrario, significa che tutte le altezze sono comprese tra $0$ ed $N$. Adesso il procedimento è: mi chiedo qual è il minimo delle altezze. Se non esiste significa che comunque presa un'altezza in $[0,N]$ allora ne esiste una più piccola. Ma questo è come dire che comunque preso un cavaliere ne esiste uno che viene dopo nella fila che è più basso, e quindi è facile estrarre una sottosuccessione decrescente. Se invece esiste un minimo $m_1\in [0,N]$, riparto da lì e mi chiedo quale sia il minimo delle altezze in $(m_1,N]$. Se non esiste, ragiono come prima. Altrimenti, esiste un minimo $m_2\in (m_1,N]$. Adesso vado avanti così: se continuo a trovare minimi ho costruito una successione crescente, altrimenti ad un certo punto ne posso costruire una decrescente.

[gabriella127]

"axpgn":
...gare per studenti del 9° e 10° grado che dovrebbero corrispondere, grosso modo, a 14/15 anni...
...come dice Quinzio, non è che tutti i quindicenni siano in grado di risolverli...
...Le soluzioni non sono affatto complicate ...

Mi danno i nervi 'sti quindicenni, se ne incontro uno che lo risolve gli dò uno schiaffo...

[axpgn]

@hydro

1) Supponiamo che non ci sia il Cavaliere più piccolo di tutti gli altri. Allora basta scegliere un Cavaliere e poi un altro alla sua destra più piccolo di lui e poi un altro più piccolo di questo e così via.

2) Se invece esiste il Cavaliere più piccolo, togliamolo idealmente dalla fila. Se alla sua destra non ne esiste un altro più piccolo allora siamo nel caso 1, se invece esiste togliamolo idealmente dalla fila. Se alla sua destra non ne esiste ... ecc.
Quindi se non si torna mai al caso 1, abbiamo una sequenza infinita di Cavalieri sempre più piccoli (che lasciamo in fila e togliamo gli altri )

[ViciousGoblin]

"axpgn":
Le soluzioni non sono affatto complicate, non è necessario tirare in ballo teoremi importanti (quello citato da ViciousGoblin piacerebbe sicuramente a 3m0o )


Cordialmente, Alex

Mah, a me pare che il caso finito sia esattamente il teorema di E.S. che ho citato (e che ho scoperto non conoscendolo).
Direi che una dimostrazione del caso finito ti da sicuramente una dimostrazione di quel teorema (almeno nel caso r=s).
Che poi la prima dimostrazione che si trova nella pagina di wikipedia è di una concisione disarmante ma mi pare difficile che un quindicenne ci arrivi (non ho letto le altre dimostrazioni proposte che a occhio mi sembrano meno elementari).