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

[axpgn]

"ViciousGoblin":... ma mi pare difficile che un quindicenne ci arrivi

Appunto

È una soluzione meno formale e più terra terra

[gabriella127]

"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 )

Vabbuo', però questo è sempre il caso di infiniti cavalieri, il caso finito non lo abbiamo risolto.

'Sto quindicenne a risolvere non arriva, latita .

E anche a me il caso finito sembra il teorema citato da ViciousGoblin con $r=s=11$

Ho provato a fare una versione con $r$ più piccolo, tipo $4$, ho tentato un'idea, ma non mi viene...

[axpgn]

Posto la risposta "finita" o aspetto ancora?

[gabriella127]

Assolutamente no!

Vabbe' non voglio essere antidemocratica, se altri la vogliono vedere postala.

[Quinzio]

"axpgn":Posto la risposta "finita" o aspetto ancora?

Noooo
aspetta

[Quinzio]

Per adesso quello che sono riuscito a "schematizzare" e' che per la sequenza $0, ..., 99$
ci sono solo 4 disposizioni che hanno le sotto-sequenze lunghe al massimo 10.
Si trovano cosi':
con $a\in{0, ..., 9}$ e $b\in{0, ..., 9}$
$m(10a+b) = a+10(9-b)$
$n(10a+b) = 9-a+10b$
$o(10a+b) = 10a+9-b$
$p(10a+b) = 10(9-a)+b$

Visivamente si puo' immaginare di prendere una scacchiera 10x10 e di scrivere i numeri da 0 a 99, partendo a scriverli dall'alto a sinistra.
Per trovare le 4 sequenze:
- partendo dall'angolo in alto a destra si precorre la prima riga (a ritroso) poi si scende di una colonna, si percorre la seconda riga e cosi' via.
- partendo dall'angolo in alto a destra si percorre prima la colonna e poi ci si sposta a sinistra di una colonna
- partendo dall'angolo in basso a sinistra si percorre prima la colonna e poi ci si sposta a destra di una colonna
- partendo dall'angolo in basso a sinistra si percorre prima la riga e poi ci si sposta in alto di una riga.

La cosa difficile da provare e' che tutte le altre disposizioni hanno almeno una sotto-sequenza monotona lunga (almeno) 11.

[axpgn]

Sforzo encomiabile, non c'è che dire

[Quinzio]

Vedo commenti molto utili
-------------------------------------------
-------------------------------------------
-------------------------------------------

"gabriella127":

Vabbuo', però questo è sempre il caso di infiniti cavalieri, il caso finito non lo abbiamo risolto.

'Sto quindicenne a risolvere non arriva, latita .

La soluzione e' in questo link, che e' gia' stato postato da ViciousGoblin.
https://en.wikipedia.org/wiki/Erd%C5%91 ... es_theorem

Pigeonhole principle
Given a sequence of length (r − 1)(s − 1) + 1, label each number ni in the sequence with the pair (ai, bi), where ai is the length of the longest monotonically increasing subsequence ending with ni and bi is the length of the longest monotonically decreasing subsequence ending with ni. Each two numbers in the sequence are labeled with a different pair: if i < j and ni ≤ nj then ai < aj, and on the other hand if ni ≥ nj then bi < bj. But there are only (r − 1)(s − 1) possible labels if ai is at most r − 1 and bi is at most s − 1, so by the pigeonhole principle there must exist a value of i for which ai or bi is outside this range. If ai is out of range then ni is part of an increasing sequence of length at least r, and if bi is out of range then ni is part of a decreasing sequence of length at least s.

Steele (1995) credits this proof to the one-page paper of Seidenberg (1959) and calls it "the slickest and most systematic" of the proofs he surveys.[2][6]

Con $r-1 = 2$ e $s-1 = 2$ prendiamo $(r − 1)(s − 1) + 1 = 5$ numeri:
$1,3,5,4,2$
Le coppie $(a_1, b_1)$ di cui si parla nella dimostrazione in questo caso sono:
$(1,1), (2,1), (3,1), (3,2), (2,3)$
e c'e' una sequenza lunga 3.
Quello che dice la dimostrazione e' che per pigeonhole, ci possono essere al massimo $2*2=4$ coppie di $(a_i, b_i)$ dove al massimo compare il numero 2, ovvero $(1,1), (1,2), (2,1), (2,2)$.
E quindi se aggiungi un 5° numero, deve necessariamente comparire una sequenza lunga 3.

[gabriella127]

"Quinzio":

La soluzione e' in questo link, che e' gia' stato postato da ViciousGoblin.
https://en.wikipedia.org/wiki/Erd%C5%91 ... es_theorem

Pigeonhole principle
Given a sequence of length (r − 1)(s − 1) + 1, label each number ni in the sequence with the pair (ai, bi), where ai is the length of the longest monotonically increasing subsequence ending with ni and bi is the length of the longest monotonically decreasing subsequence ending with ni. Each two numbers in the sequence are labeled with a different pair: if i < j and ni ≤ nj then ai < aj, and on the other hand if ni ≥ nj then bi < bj. But there are only (r − 1)(s − 1) possible labels if ai is at most r − 1 and bi is at most s − 1, so by the pigeonhole principle there must exist a value of i for which ai or bi is outside this range. If ai is out of range then ni is part of an increasing sequence of length at least r, and if bi is out of range then ni is part of a decreasing sequence of length at least s.

Steele (1995) credits this proof to the one-page paper of Seidenberg (1959) and calls it "the slickest and most systematic" of the proofs he surveys.[2][6]

Con $r-1 = 2$ e $s-1 = 2$ prendiamo $(r − 1)(s − 1) + 1 = 5$ numeri:
$1,3,5,4,2$
Le coppie $(a_1, b_1)$ di cui si parla nella dimostrazione in questo caso sono:
$(1,1), (2,1), (3,1), (3,2), (2,3)$
e c'e' una sequenza lunga 3.
Quello che dice la dimostrazione e' che per pigeonhole, ci possono essere al massimo $2*2=4$ coppie di $(a_i, b_i)$ dove al massimo compare il numero 2, ovvero $(1,1), (1,2), (2,1), (2,2)$.
E quindi se aggiungi un 5° numero, deve necessariamente comparire una sequenza lunga 3.

Come si può vedere, per ogni quindicenne inventare questa dimostrazione è una passeggiata, si dice che anche qualche bambino all'asilo nido ci sia arrivato facilmente.

[axpgn]

@Gabriella


Infatti anche per il caso infinito mi pare che ci sia una certa significativa differenza tra la soluzione che ho riportato e le altre (fermo restando che sono corrette)

[gabriella127]

Qual è la soluzione che hai riportato? Io non l'ho vista, pensavo non l'avessi detta la soluzione.

[axpgn]

Qua

[gabriella127]

Scusa axpgn, questo mi sembra per il caso infinito, come avevo detto, dove ha senso dire 'non c'è un cavaliere più piccolo di tutti', non nel caso finito dove un cavaliere più piccolo ci deve stare per forza.
Devo pensarci su per capire come funziona nel caso finito, non mi è affatto chiaro.

Riscrivo la soluzione che hai citato per chiarezza:

"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 )"

In un insieme finito siamo al Caso 2, ci deve stare per forza un cavaliere più piccolo.
Consideriamo il caso con $r=4$ e quindi con $10$ inumeri da $1$ a $10$.

Supponiamo che siano scritti così in sequenza inizialmente:

$4$ $5$ $7$ $10$ $2$ $3$ $9$ $8$ $6$ $1$

Il numero più piccolo esiste, ovviamente $1$. Lo togliamo dalla fila.
Alla sua destra non c'è un numero più piccolo, perché non c 'è un tubo.
Quindi però non torniamo caso 1 (che è comunque impossibile visto che i cavalieri sono finiti), e che facciamo?

[axpgn]

"gabriella127":Scusa axpgn, questo mi sembra per il caso infinito, ...

Sì, certo, mi riferivo a quello; per il caso finito non ho ancora postato la soluzione "da quindicenne", se così posso dire.

[gabriella127]

Ah vabbe', ma di quella finita stavamo parlando, non ci siamo capiti.

[Studente Anonimo]

Una soluzione che usa la teoria di Ramsey (del caso infinito) e che sicuramente un 15enne non troverebbe a meno che non conosca il Teorema di Ramsey

Teorema di Ramsey per i \(2\)-sets. Sia \(X\) un insieme infinito, allora per ogni colorazione finita di \(X^{(2)}\) esiste un insieme infinito \(Y\subseteq X\) tale che \(Y^{(2)}\) è monocromatico.

Dove \(X^{(2)} \) indica l'insieme di tutti i \(2\)-sets di \(X\), i.e. insiemi della forma \(\{x,y\} \) con \(x,y\in X\) e distinti.

Sia \((x_n)_{n\in \mathbb{N}}\) la successione delle altezze dei Cavalieri. Definiamo la seguente colorazione \( \chi: \mathbb{N}^{(2)} \to \{\text{rosso},\text{blu}\} \)
\[ \chi(\{n,m\}) \mapsto \left\{\begin{matrix}
\text{blu}& \text{ se } x_{\min(n,m)} < x_{\max(n,m)} \\
\text{rosso}& \text{ se } x_{\min(n,m)} > x_{\max(n,m)}
\end{matrix}\right. \]
NB: non possiamo avere che \(x_{\min(n,m)} = x_{\max(n,m)}\) perché le altezze sono supposte differenti.
Per il teorema di Ramsey esiste un sottoinsieme infinito \(Y \subseteq \mathbb{N} \) tale che \(Y^{(2)} \) è monocromatico, e sia \(n_1

Cita

Segnala

[Studente Anonimo]

Caso finito che un 15enne potrebbe arrivarci, ma non ci scommetteri

Sia \( n=10\) e \(m=10\) e siano \(b_1, b_2,\ldots,b_{nm+1}\) i numeri da \(1,\ldots,101\) scritti in qualunque ordine. Denotiamo con \( \ell_j \) la lunghezza della più lunga sotto-successione crescente partendo da \(b_j\) tra \(b_j , b_{j+1},\ldots ,b_{nm+1}\). Se esiste \( 1 \leq j \leq nm+1 \) tale che \( \ell_{j} \geq m+1\) abbiamo finito. Altrimenti abbiamo che per ogni \( 1 \leq j \leq nm+1\) risulta che \( \ell_j \leq m \). Per il principio dei piccioni esistono \(n+1\) valori di \( \ell_j\) che sono uguali. Risulta che i corrispondenti valori \(b_j\) sono in ordine decrescente e abbiamo finito. Infatti supponiamo che \(1 \leq i < j \leq nm+1 \) sono tale che \(b_i < b_j \) allora abbiamo per costruzione che \( \ell_i \geq \ell_j +1 \) e quindi non è possibile avere \( \ell_i = \ell_j\).

[axpgn]

"3m0o":Caso finito che un 15enne potrebbe arrivarci,

Tu

[Studente Anonimo]

Naaahhh, io no, ma mica dicevo con quel formalismo, solo che quell'idea è accessibile a molti 15enni secondo me!

Ps: non ho capito il bump

[axpgn]

"3m0o":Naaahhh, io no, ma mica dicevo con quel formalismo, ...

E allora come?
Comunque mi pare che la soluzione "ufficiale" (si fa per dire) sia più semplice ... ho scritto "mi pare" perché l'idea che hai scritto sarà pure accessibile ad un 15enne ma non a me

Ho "bumpato" perché aspetto ancora la soluzione "semplice" (si fa sempre per dire )