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]

[Studente Anonimo]

"gabriella127":

Ti stiamo trascurando?

Sii...

[axpgn]

Non è vero!

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

[ViciousGoblin]

Cosa non è vero?

[axpgn]

Che 3m0o è trascurato, ho messo la prova

[gabriella127]

"gabriella127":[quote="axpgn"]Ma io no?

Ti stiamo trascurando?

[/quote]

"3m0o":[quote="gabriella127"]

Ti stiamo trascurando?

Sii... [/quote]

Vedo che siamo in un thread con carenze affettive

Ma è presto rimediato.

Facciamo ordine.

Riporto la soluzione di axpgn:

"axpgn":

Il primo passo consiste nello scomporre la sequenza originale in sottosequenze in questo modo:
Chiamo $a_1$ il primo numero della sequenza originale, chiamo $a_2$ il primo numero alla destra di $a_1$ e minore di $a_1$, chiamo $a_3$ il primo numero alla destra di $a_2$ e minore di $a_2$ e così via finché si può; poi ricomincio a costruire la seconda allo stesso modo ovvero chiamo $b_1$ il primo numero di quelli rimasti, chiamo $b_2$ il primo numero alla destra di $b_1$ e minore di $b_1$, chiamo $b_3$ il primo numero alla destra di $b_2$ e minore di $b_2$ e così via; così facendo spezzetto la sequenza originale in $m$ sottosequenze decrescenti.
Se almeno una delle $m$ sottosequenze è lunga almeno $11$, ho finito.
Fino a qui siamo tutti d'accordo, ok?

Se nessuna sottosequenza è lunga più di $10$ numeri allora significa che il numero delle sottosequenze è maggiore di $10$ ($m≥11$); questo perché essendo ogni sottosequenza lungo al massimo $10$, avremo $10 xx 10 =100$ e quindi occorre almeno un'altra sottosequenza per arrivare a $101$.

È sempre possibile estrarre un numero da ognuna di queste $m>=11$ sottosequenze in modo tale da costruire una sequenza crescente.
Perché? Perché ognuna delle sottosequenze così costruite contiene sempre il minimo assoluto dei numeri rimasti (tutti minimi diversi) perciò si avrà $a_(min)

La soluzione di axpgn mi torna (al momento) per cui gli diamo il bollino blu


Riporto la soluzione di 3m0o.

"3m0o":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\).

Non capisco, nonostante i piccioni, perché ci devono essere $n+1$ sottosuccessioni di uguale lunghezza: "esistono n+1 valori di $ℓ_j$ che sono uguali" (se ho ben capito il modo di prendere le successioni).

Ho fatto un esempio, a caso, con $n=m=4$ per cui i numeri sono in totale $10$, $(m-1)(n-1) +1$.

J'ai considéré la suite suivante, où il n'y a pas une sous-suite croissante de longueur $4$ (che padronanza delle lingue)

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

Prendendo le sottouccessioni crescenti viene:

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

Dove sono le $n+1$ sottosuccessioni di uguale lunghezza?

[ViciousGoblin]

@gabriella
Rispondo in nome di 3mOo sperando che non se ne abbia a male.

Nella successione che presenti.

$8−9−10−7−4−1−6−3−5−2$ hai:

$l_1=3$ (sottosuccessione crescente più lunga che inizia da $a_1$: $8-9-10$)

$l_2=$2 (sottosuccessione crescente più lunga che inizia da $a_2$: $9-10$ )

$l_3=1$ (sottosuccessione crescente più lunga che inizia da $a_3$: $10$)

$l_4=1$ (sottosuccessione crescente più lunga che inizia da $a_4$: $7$ )

$l_5=2$ (sottosuccessione crescente più lunga che inizia da $a_5$: $4-6$ oppure $4-5$ )

$l_6=3$ (sottosuccessione crescente più lunga che inizia da $a_6$: $1-3-5$ )

$l_7=1$ (sottosuccessione crescente più lunga che inizia da $a_7$: $6$)

$l_8=2$ (sottosuccessione crescente più lunga che inizia da $a_8$: $3-5$ )

$l_9=1$ (sottosuccessione crescente più lunga che inizia da $a_9$: $5$)

$l_{10}=1$ (sottosuccessione crescente più lunga che inizia da $a_{10}$: $2$ )

Non hai nessun $l_i\ge 4$ quindi non ci sono sottosequenze crescenti di lunghezza 4. Vedi però che $l_i=1$ per $i=3-4-7-9-10$
e quindi trovi la sottosequenza descente $10-7-6-5-2$

[ViciousGoblin]

"axpgn":Che 3m0o è trascurato, ho messo la prova

Non mi pare di aver detto che 3mOo è stato trascurato (né che è trascurato)

[axpgn]

Sei più serio di 3m0o (così adesso ne ho offesi due in un colpo solo)

Lo so che non è bello spiegare le battute ma tant'è ...

Per dimostrare a 3m0o che non era stato trascurato, ho riportato la tua frase in cui concordavi con lui, meglio di così

[ViciousGoblin]

"axpgn":Sei più serio di 3m0o (così adesso ne ho offesi due in un colpo solo)

Lo so che non è bello spiegare le battute ma tant'è ...

Per dimostrare a 3m0o che non era stato trascurato, ho riportato la tua frase in cui concordavi con lui, meglio di così

Agh - ho capito....
Scusa

[axpgn]

Non c'è niente di cui scusarsi

[gabriella127]

"ViciousGoblin":@gabriella
Rispondo in nome di 3mOo sperando che non se ne abbia a male.

Nella successione che presenti.

$8−9−10−7−4−1−6−3−5−2$ hai:

$l_1=3$ (sottosuccessione crescente più lunga che inizia da $a_1$: $8-9-10$)

$l_2=$2 (sottosuccessione crescente più lunga che inizia da $a_2$: $9-10$ )

$l_3=1$ (sottosuccessione crescente più lunga che inizia da $a_3$: $10$)

$l_4=1$ (sottosuccessione crescente più lunga che inizia da $a_4$: $7$ )

$l_5=2$ (sottosuccessione crescente più lunga che inizia da $a_5$: $4-6$ oppure $4-5$ )

$l_6=3$ (sottosuccessione crescente più lunga che inizia da $a_6$: $1-3-5$ )

$l_7=1$ (sottosuccessione crescente più lunga che inizia da $a_7$: $6$)

$l_8=2$ (sottosuccessione crescente più lunga che inizia da $a_8$: $3-5$ )

$l_9=1$ (sottosuccessione crescente più lunga che inizia da $a_9$: $5$)

$l_{10}=1$ (sottosuccessione crescente più lunga che inizia da $a_{10}$: $2$ )

Non hai nessun $l_1\ge 4$ quindi non ci sono sottosequenze crescenti di lunghezza 4. Vedi però che $l_i=1$ per $i=3-4-7-9-10$
e quindi trovi la sottosequenza descente $10-7-6-5-2$

Ah, avevo capito mnale come si prendono le sottosuccesioni crescenti, pensavo che si dovevano poi scartare, le prendevo come nel caso di axpgn.

Grazie.

[Studente Anonimo]

"axpgn":Non è vero!

[quote="ViciousGoblin"] Sono invece d'accordo sulla prova di 3mOo che direi essere una dimostrazione del teorema di E.S.

[/quote]

"gabriella127":[quote="gabriella127"][quote="axpgn"]Ma io no?

Ti stiamo trascurando?

[/quote]

"3m0o":[quote="gabriella127"]

Ti stiamo trascurando?

Sii... [/quote]

Vedo che siamo in un thread con carenze affettive

Ma è presto rimediato.

[...]
La soluzione di axpgn mi torna (al momento) per cui gli diamo il bollino blu



Non capisco, nonostante i piccioni, perché ci devono essere $ n+1 $ sottosuccessioni di uguale lunghezza: "esistono n+1 valori di $ ℓ_j $ che sono uguali" (se ho ben capito il modo di prendere le successioni).

Ho fatto un esempio, a caso, con $ n=m=4 $ per cui i numeri sono in totale $ 10 $, $ (m-1)(n-1) +1 $.

J'ai considéré la suite suivante, où il n'y a pas une sous-suite croissante de longueur $ 4 $ (che padronanza delle lingue)

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

[/quote]
Carenze affettive no dai, solo un pochino

Ma tutto rimediato ora!

Ottima padronanza della lingua, ma come giustamente ha spiegato ViciousGoblin qui

"ViciousGoblin":@gabriella
Rispondo in nome di 3mOo sperando che non se ne abbia a male.

Nella successione che presenti.

$ 8−9−10−7−4−1−6−3−5−2 $ hai:

$ l_1=3 $ (sottosuccessione crescente più lunga che inizia da $ a_1 $: $ 8-9-10 $)

$ l_2= $2 (sottosuccessione crescente più lunga che inizia da $ a_2 $: $ 9-10 $ )

$ l_3=1 $ (sottosuccessione crescente più lunga che inizia da $ a_3 $: $ 10 $)

$ l_4=1 $ (sottosuccessione crescente più lunga che inizia da $ a_4 $: $ 7 $ )

$ l_5=2 $ (sottosuccessione crescente più lunga che inizia da $ a_5 $: $ 4-6 $ oppure $ 4-5 $ )

$ l_6=3 $ (sottosuccessione crescente più lunga che inizia da $ a_6 $: $ 1-3-5 $ )

$ l_7=1 $ (sottosuccessione crescente più lunga che inizia da $ a_7 $: $ 6 $)

$ l_8=2 $ (sottosuccessione crescente più lunga che inizia da $ a_8 $: $ 3-5 $ )

$ l_9=1 $ (sottosuccessione crescente più lunga che inizia da $ a_9 $: $ 5 $)

$ l_{10}=1 $ (sottosuccessione crescente più lunga che inizia da $ a_{10} $: $ 2 $ )

Non hai nessun $ l_i\ge 4 $ quindi non ci sono sottosequenze crescenti di lunghezza 4. Vedi però che $ l_i=1 $ per $ i=3-4-7-9-10 $
e quindi trovi la sottosequenza descente $ 10-7-6-5-2 $

Il tuo controesempio non è un controesempio, ma vedo che avete già risolto!


Comunque axpgn mi hai anticipato perché io volevo postare questo da un po'...

Dei numeri interi positivi $b_1,b_2,\ldots,b_{nm+1}$ sono scritti e consegnati al mago, provare che il mago può selezionarne $n+1$ tale che nessuno dei quali divide gli altri oppure $m+1$ ciascuno dei quali divide il successivo.

[gabriella127]

Sì sì, avevo capito male come si dovevano prendere le sottosuccessioni.

[Mancini2002]

Ciao! Sono nuovo di questo forum, cerco amici e persone che condividano i miei hobby.
Potete dirmi in cosa consiste il gioco e se è ancora possibile partecipare?

[gabriella127]

Ciao Mancini2002 e benvenuto sul Forum!

Certo che è possibile partecipare, il thread è aperto a nuovi interventi.
Tieni presente però che non si tratta di un gioco in senso stretto, si tratta di un quesito a cui dare risposte, il cui testo è il primo messaggio di questo thead.

In questa sezione 'Giochi' abbiamo per lo più giochi nel senso di enigmi matematici, quella che si chiama matematica ricreativa.

Ancora benvenuto, ci farà piacere leggere tuoi interventi.