Monete finite, quadrati infiniti..

[jordan]

Supponiamo di aver una riga infinita di quadrati e di aver posizionato un numero finito di monete su di esso. Una mossa lecita consiste nello scegliere un quadrato con piu di una moneta, prenderne 2 da esso, e spostarle una al quadrato subito a sinistra e una al quadrato subito a destra.
Questo gioco finisce quando le mosse lecite sono finite (cioè quando ogni quadrato contiene al massimo una moneta).

Mostrare che, data la configurazione iniziale, il gioco termina sempre, indipendentemente dalle mosse lecite scelte, cioè nella stessa configurazione finale.

[Tibor Gallai]

Bonus question: mostrare che anche la lunghezza di ogni partita non dipende dalla scelta delle mosse, ma solo dalla configurazione iniziale.

[jordan]

Esatto TG, il bello è che ci devi passare per forza a dimostrarlo

Edit: @Haile, si..

[Haile]

Mostrare che, data la configurazione iniziale, il gioco termina sempre, indipendentemente dalle mosse lecite scelte, cioè nella stessa configurazione finale.

Si deve dimostare che il gioco termina sempre con una sequenza di quadrati con 0 o 1 monete (se è ovvio, non lo è per me) oppure che, data una certa situazione di partenza, termina sempre nella stessa posizione finale?

C'è quel "cioè" che non capisco... il fatto che termini sempre non implica che termini con una configurazione che non dipende dalle mosse. Oppure si?

"Mostrare che, data la configurazione iniziale, il gioco termina sempre nella stessa configurazione finale, indipendentemente dalle mosse lecite scelte."

Sarebbe così?

[Tibor Gallai]

Esatto TG, il bello è che ci devi passare per forza a dimostrarlo

Ah ok, ottimo!
Allora immagino che la parola "quadrati" non sia messa lì a caso...?

[Haile]

Grazie per il chiarimento... mi interessa come esercizio, vediamo se riesco a tirarne fuori qualcosa

[Tibor Gallai]

Il problema si trova anche qui, dove c'è una soluzione di (credo) jordan.
Questa soluzione coincide con la mia fino al punto in cui dimostra che non esistono partite infinite.
Poi però non la capisco più, complici un inglese e una notazione non precisissimi... Qualcuno la sa interpretare?

[jordan]

Già sapevo che la notazione degli $ \{h_i\} $ e $ \{H_i\} $ non era precisa..il resto dov'è che non si capisce?

[Tibor Gallai]

Mah, a me sembra l'unica cosa precisa.
Tutto il resto non capisco cosa sia, per esempio S è un numero, ma poi dici "reaches a new minimum in S" come se fosse un insieme o chissà cos'altro. Poi dici "Then we can choose $ $\{a_i\}_{0 \le i \le n + 2y + 1} $", ma se gli $ $a_i $ sono fissati una volta per tutte all'inizio, cosa c'è da scegliere?
Boh, non ho la più vaga idea di cosa significhi tutta l'ultima parte della soluzione.

[jordan]

[...] Then we can choose $\{a_i\}_{0 \le i \le n + 2y + 1}$ s.t. $S: = \min\{\sum{h_i},\sum{H_i}\}$ reaches minimum. Since the initial configuration is the same by assumption, then there exist $0 < j <n> 1$, but now the $n + 2y + 2$ upla of non negative integers $(a_0,a_1,\ldots,a_{j - 1} + 1,a_j - 2,a_{j + 1} + 1,\ldots,a_{n + 2y - 1})$ reaches a new minimum in S, contradiction.

..Supposto per assurdo che esistano due sequenze $ \{h_i\} $ e $ \{H_i\} $ distinte, visto che stiamo parlando di interi non negativi di cui almeno uno è positivo sempre, se fissiamo $ \{a_i\}_{0 \le i \le n + 2y + 1} $ allora possiamo anche definire $ S(\{a_i\}):=\min\{\sum{h_i},\sum{H_i}\} $. Adesso, a patto di non partire da una configurazione iniziale di $ \{a_i\} $ in cui non è possibile muovere, esisterà sempre una sequenza di $ \{a_i\} $ per cui $ S(\{a_i\}) $ assume minimo(visto che è a valori in $ \mathbb{N}_0 $). Ma se invece di partire da $ (a_1,a_2\ldots,a_n) $ partiamo adesso da $ (a_0,a_1,\ldots,a_{j - 1} + 1,a_j - 2,a_{j + 1} + 1,\ldots,a_{n + 2y - 1}) $ si contraddice la minimalità di S. Non funziona?

[Tibor Gallai]

Non funziona?

Non saprei, io continuo a non capire, perché mi sembra una traduzione in italiano di ciò che già non capivo in inglese...

Allora, se interpreto giusto, S ora è una funzione. Apparentemente, da sequenze di $ $a_i $ a $ $\mathbb N $. Questa funzione prende 2 sequenze distinte di mosse a caso fattibili a partire dagli $ $a_i $ (a patto che esistano) e ne calcola la lunghezza minima. O forse calcola la minima lunghezza tra tutte le possibili partite? O forse vuoi definire S solo sulle configurazioni che hanno almeno 2 partite distinte, e calcolare la minima lunghezza di tutte le possibili partite? Assumiamo l'ultima ipotesi, che mi pare la più sensata/promettente.

Dopo prendi una configurazione di $ $a_i $ per cui S è minimo. Poi fai la prima mossa della partita più corta, cosa che non dici esplicitamente ma credo di poter interpretare così. Arrivi in una nuova configurazione, e se lì S è definita, allora si contraddice la minimalità. Quindi lì S non è definita, e allora da lì in poi esiste un unico modo di terminare la partita. E poi? Non è mica finita... O è errata la dimostrazione, o non ho capito niente della notazione.

Al di là del formalismo, volevo capire l'idea di fondo, poi i dettagli si sistemano da soli.

[jordan]

Allora, se interpreto giusto, S ora è una funzione. Apparentemente, da sequenze di $ $a_i $ a $ $\mathbb N $.

Ok.

Questa funzione prende 2 sequenze distinte di mosse a caso fattibili a partire dagli $ $a_i $ (a patto che esistano) e ne calcola la lunghezza minima.

E' questa..S inoltre è definita solo sulle sequenze degli $ a_i $ che hanno almeno due partite distinte (altrimenti non c'è nulla da fare..).

... O forse vuoi definire S solo sulle configurazioni che hanno almeno 2 partite distinte, e calcolare la minima lunghezza di tutte le possibili partite? Assumiamo l'ultima ipotesi, che mi pare la più sensata/promettente.

Appunto: tra tutti gli S definiti, prendiamo quello più piccolo (questo possiamo farlo).

Dopo prendi una configurazione di $ $a_i $ per cui S è minimo. Poi fai la prima mossa della partita più corta, [...] Non è mica finita...

Perchè no? Il minimo di S non può essere 1. Assumi che il minimo tra tutti gli S sia 2, lo possiamo ottenere da una configurazione iniziale di $ \{a_i\} $ fissati. Allora potrebbe essere anche 1 dopo che eliminiamo la prima mossa?Ma 1 non può essere.. Allora il minimo è almeno 3: ma sempre se partiamo dalla "prima mossa fatta" dovrebbe essere 2..cosi andando (potresti obiettare che partendo già dalla prima mossa fatta allora partiresti da altre caselle, ma a noi ci interessa solo il calcolo della somma degli $ h_i $ sotto il vincolo che $ a_i+h_{i+1}-2h_i+h_{i+1} \in \{0,1\} $ per ogni i, ma che viene rispettato indipendentemente da quando fai la mossa..)
Ok, oltre l'inglese non sono chiaro neanche in italiano

[Tibor Gallai]

Assumi che il minimo tra tutti gli S sia 2, lo possiamo ottenere da una configurazione iniziale di $ \{a_i\} $ fissati. Allora potrebbe essere anche 1 dopo che eliminiamo la prima mossa?

Cosa vuol dire "eliminiamo la prima mossa"? Vuol dire che fai una opportuna mossa (che sarà la prima della partita più corta) e vai in un'altra configurazione? Ok, da questa configurazione c'è una partita lunga 1, che è anche unica. Allora qui S non è definita. In che modo contraddici la minimalità di S?

[jordan]

...Allora qui S non è definita. In che modo contraddici la minimalità di S?

Appunto che non è definita, significa che le sequenze di h_i e H_i devono essere uguali (in altre parole la configurazione finale è unica indipendentemente dalle mosse fatte), cioè, il minimo non può essere 2, ma è almeno 3..

E' qui il punto della discordia?
Edit: te come l'hai dimostrata la tua "bonus question"?

[Tibor Gallai]

Uno dei punti della discordia (poi passerò agli altri) è perché consideri solo 2 sequenze di mosse per ogni configurazione, oltretutto arbitrarie, e minimizzi solo su quelle 2. Questo crea evidenti problemi e complicazioni, non puoi minimizzare su tutte le partite che iniziano in quella configurazione?? Che impedimento c'è??