I Cavalieri e il Mago

[gabriella127]

Ok

[ViciousGoblin]

A me l'argomento di axpng non torna .

Testo nascosto, fai click qui per vederlo

Prima si scompone 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; altrimenti significa che $m>=11$ e quindi basta prendere un numero da ciascuna sottosequenza per ottenere una sequenza crescente lunga almeno $11$

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.

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

Testo nascosto, fai click qui per vederlo

Mi pare che l'idea chiave sia di prendere per ogni elemento $x$ la sottosequenza decrescente più lunga che comincia da $x$ (che non è necessariamente costruita con la procedura di axpng).

[gabriella127]

A me l'argomento di axpng non torna .

Testo nascosto, fai click qui per vederlo

Prima si scompone 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; altrimenti significa che $m>=11$ e quindi basta prendere un numero da ciascuna sottosequenza per ottenere una sequenza crescente lunga almeno $11$

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.

[ViciousGoblin]

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

Testo nascosto, fai click qui per vederlo

Invece, è vero che ogni successiva sottosequenza contiene un elemento più grande del minimo della sequenza precedente (se no farebbe parte della sequenza precedente).

Quello che hai scritto mi torna. Però per costruire la sottosequenza crescente $(y_n)$ non vedo ancora chiaro.

Se ti seguo devo prendere come $y_1$ il minimo della prima sottosequenza $(a_n)$. Poi trovo un $b_i$ che è maggiore di $y_1$. Potrei porre $y_2=b_i$. Continuando troverei un $c_j$ maggiore del minimo dei $b_i$, ma questo non mi dice che $c_j\ge y_2$.

Mah

[axpgn]

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

[gabriella127]

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

Testo nascosto, fai click qui per vederlo

Invece, è vero che ogni successiva sottosequenza contiene un elemento più grande del minimo della sequenza precedente (se no farebbe parte della sequenza precedente).

Quello che hai scritto mi torna. Però per costruire la sottosequenza crescente $(y_n)$ non vedo ancora chiaro.

Se ti seguo devo prendere come $y_1$ il minimo della prima sottosequenza $(a_n)$. Poi trovo un $b_i$ che è maggiore di $y_1$. Potrei porre $y_2=b_i$. Continuando troverei un $c_j$ maggiore del minimo dei $b_i$, ma questo non mi dice che $c_j\ge y_2$.

Mah

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

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 ...

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)<...$.

Ok?

Cordialmente, Alex

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

[gabriella127]

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

[ViciousGoblin]

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

Testo nascosto, fai click qui per vederlo

Invece, è vero che ogni successiva sottosequenza contiene un elemento più grande del minimo della sequenza precedente (se no farebbe parte della sequenza precedente).

Quello che hai scritto mi torna. Però per costruire la sottosequenza crescente $(y_n)$ non vedo ancora chiaro.

Se ti seguo devo prendere come $y_1$ il minimo della prima sottosequenza $(a_n)$. Poi trovo un $b_i$ che è maggiore di $y_1$. Potrei porre $y_2=b_i$. Continuando troverei un $c_j$ maggiore del minimo dei $b_i$, ma questo non mi dice che $c_j\ge y_2$.

Mah

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

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...

Hai ragione! Così funziona.

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

[axpgn]

Ma io no?