OliForum Matematico

Tibor Gallai ha scritto:..Questo crea evidenti problemi e complicazioni, non puoi minimizzare su tutte le partite che iniziano in quella configurazione?? Che impedimento c'è??

Ah, si, si, nessun impedimento, io dicevo che ne esistevano almeno due distinte.. volendo puoi prenderle tutte, non cambia nulla..

Invece cambia un bel po', perché se ne prendi solo 2 non sai come "correlare" gli S tra una configurazione ed una successiva. Per esempio, parti da una configurazione A, fai una mossa della partita più corta (tra le 2) e raggiungi A'. Tu vorresti che, qualora S(A) e S(A') siano definiti, valga S(A) > S(A'). Ma come fa a valere, se hai preso sequenze di mosse completamente a casaccio?

Tibor Gallai ha scritto:Tu vorresti che, qualora S(A) e S(A') siano definiti, valga S(A) > S(A'). Ma come fa a valere, se hai preso sequenze di mosse completamente a casaccio?

E' quello che ti dicevo prima.. infatti stiamo guardando solo alla somma finale dei possibili h_i.
Allora, cerco di riassumere:
$ t_i:=a_i+h_{i+1}-2h_i+h_{i-1} $ deve essere in $ \{0,1\} $ per ogni i (*), è condizione necessaria e sufficiente per far terminare il gioco (che come detto, termina in un numero finito di mosse) ($ h_i $ sono il numero totale di mosse applicate sulla casella i a fine partita).

Supponiamo che per una data configurazione di $ a_i $ esistano sequenze $ h_{i,1} $, $ h_{i,2} $, ..., $ h_{i,j} $ distinte in almeno un elemento e che rispettano tutte la (*). Vogliamo mostrare che j=1.
Per ogni t in {1,2,...,j} definiamo $ R(h_{i,t}) $ come la somma di tutti i suoi elementi. Definiamo anche $ S(\{a_i\}) $ come il minimo dei possibili $ R(h_{i,t}) $.
Prendiamo il minimo di S che lo assume in una sequenza fissata di $ \{a_i\} $ in un particolare $ h_{i,t_0} $.
Allora prendiamo la sequenza delle mosse di $ h_{i,t_0} $, e partiamo dalla sequenza che ha la prima mossa già fatta. Allora S avrà un nuovo minimo (il discorso di quale mossa scegliere non regge, visto che quest'ultima sequenza da cui calcoliamo il nuovo minimo dovrebbe essere già stata conteggiata quando S è stato calcolato la prima volta..).
In attesa di tue notizie, spero che stavolta sia chiaro quello che volevo intendere..
Comunque ripeto la domanda del mio post precedente: la tua com'era?

jordan ha scritto:Allora prendiamo la sequenza delle mosse di $ h_{i,t_0} $, e partiamo dalla sequenza che ha la prima mossa già fatta. Allora S avrà un nuovo minimo (il discorso di quale mossa scegliere non regge, visto che quest'ultima sequenza da cui calcoliamo il nuovo minimo dovrebbe essere già stata conteggiata quando S è stato calcolato la prima volta..).

Il lungo discorso che precede questo era chiaro e assodato, e (permettimi di dire) potevi evitare la fatica di ripeterlo...
Il punto cruciale è nella frase che ho quotato, che contiene l'unica idea della dimostrazione, e che sembri voler tirare via senza spiegare in modo umanamente comprensibile. Giuro che non capisco il senso, proprio a livello linguistico.

Comunque ripeto la domanda del mio post precedente: la tua com'era?

La dico dopo, altrimenti si fa casino.

Tibor Gallai ha scritto:Il lungo discorso che precede questo era chiaro e assodato, e (permettimi di dire) potevi evitare la fatica di ripeterlo...

Lo so, era solo per riassumere, visto che j>2 non l'avevo mai nominato..

Tibor Gallai ha scritto:Il punto cruciale è nella frase che ho quotato, che contiene l'unica idea della dimostrazione, e che sembri voler tirare via senza spiegare in modo umanamente comprensibile.

Non ho mai escluso che sia proprio sbagliato quello che sto dicendo..
comunque provo a parafrasarlo di nuovo scegliamo la configurazione iniziale di $ a_1,a_2,....,a_n $ tale che S sia minimo (e S è un minimo che viene calcolato al variare di tutte le possibili configurazioni iniziali che hanno almeno due sequenze di mosse). Prendiamo quella sequenza di mosse che fanno il minimo di S.
La prima mossa per ottenere il minimo è fatta su $ a_\ell $.
Adesso prendiamo in considerazione la sequenza $ a_1,a_2,...,a_{\ell-1}+1,a_\ell-2,a_{\ell+1}+1,...,a_n $ (Anche questa ha almeno due sequenze distinte di mosse, è sufficiente prendere quell'altra di prima e toglierne una (anche se non è la prima) in $ a_\ell $, credo sia questo il punto). Continuando ad applicare la stesse mosse di prima abbiamo che il numero di mosse necessarie a concludere il gioco è minore del "vecchio" S, che per definizione doveva essere il minimo.

Tibor Gallai ha scritto:La dico dopo, altrimenti si fa casino.

Ok..

jordan ha scritto:(Anche questa ha almeno due sequenze distinte di mosse, è sufficiente prendere quell'altra di prima e toglierne una (anche se non è la prima) in $ a_\ell $, credo sia questo il punto)

Credo anch'io che fosse quello il punto. Però capisci che dal non dirlo, al dirlo senza dimostrarlo, al dimostrarlo, ci passa un po' di differenza.
Supponendo di aver dimostrato che questa cosa si possa fare sempre, e che tutti i dettagli si possano sistemare (che, per inciso, è pure vero), restano da dire 2 parole sulla finitezza delle partite. Come mai è ovvio che esiste un limite alla "distanza" percorribile da una moneta, fissata la configurazione di partenza?

Per discutere la mia soluzione della seconda parte, possiamo spostarci su questa piccola generalizzazione del problema:
viewtopic.php?p=109080#109080
Il mio metodo si applica senza modifiche anche a questo caso generale, ora vorrei capire se col tuo metodo cambia qualcosa...

Tibor Gallai ha scritto:Però capisci che dal non dirlo, al dirlo senza dimostrarlo, al dimostrarlo, ci passa un po' di differenza.

E' solo che mi sono espresso male, non era nelle mie intenzioni non essere chiaro..

Tibor Gallai ha scritto:... restano da dire 2 parole sulla finitezza delle partite. Come mai è ovvio che esiste un limite alla "distanza" percorribile da una moneta, fissata la configurazione di partenza?

Questo lo lascio a qualche altro user.

Tibor Gallai ha scritto:Per discutere la mia soluzione della seconda parte, possiamo spostarci su questa piccola generalizzazione del problema. Il mio metodo si applica senza modifiche anche a questo caso generale, ora vorrei capire se col tuo metodo cambia qualcosa...

Bello Ci penserò, questo è sicuro..