I Cavalieri e il Mago

[gabriella127]

Ma io no?

Ti stiamo trascurando?

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!

[axpgn]

[3m0o]

Ti stiamo trascurando?

Sii...

[axpgn]

Non è vero!

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]

Ma io no?

Ti stiamo trascurando?

Ti stiamo trascurando?

Sii...

Vedo che siamo in un thread con carenze affettive

Ma è presto rimediato.

Facciamo ordine.

Riporto la soluzione di axpgn:

Testo nascosto, fai click qui per vederlo

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)<b_(min)<...$.

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


Riporto la soluzione di 3m0o.

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

Testo nascosto, fai click qui per vederlo

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]

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ì