Soluzione:
Testo nascosto:
Allora, per prima cosa numeriamo i nostri quadretti con i numeri interi, poniamoci sulla retta reale e definiamo posizione $p$ di una moneta l'intero su cui si trova ad un certo istante ( volendo possiamo anche chiamarlo valore temporaneo ). Sia inoltre $m$ il numero di monete presenti ed $M$ l'insieme di tutte le monete. Equivalentemente al testo, il gioco termina quando sui nostri numeri interi ci sono soltanto pile con $1$ moneta , non necessariamente in tutti.
Definiamo inoltre sequenza fantastica (ogni riferimento al problema 4 è puramente casuale), una successione massima di pile di monete priva di due o più pile vuote consecutive ( con massima intendo che l'intero precedente alla prima pila è vuoto e l'intero successivo all'ultima pila è vuoto). Quindi in questo nostro insieme vi sono al massimo due pile piene separate da una pila vuota.
La cosa fighissima di questa nostra sequenza è che ha tante proprietà controllabili:
$\bullet $ Una sequenza fantastica non può suddividersi in due sequenze fantastiche poiché non posso creare due pile vuote consecutive con una mossa.
$\bullet$ Due sequenze fantastiche possono unirsi tra loro e divenire un'unica sequenza super fantastica ( o soltanto fantastica).
$\bullet$ Il numero di sequenze fantastiche è debolmente decrescente ( poiché non posso creare sequenze fantastiche ma soltanto unirle)
Troviamo ora un invariante ed un monovariante che saranno utili nella nostra soluzione:
Invariante 1: $\sum _{m \in M} p(m)$
Cioè la somma delle posizioni delle monete non varia mai. Ciò si giustifica abbastanza intuitivamente dicendo che ad ogni mossa che agisce su due monete $m_h,m_k$ , la posizione di una aumenta di $1$ e la posizione dell'altra diminuisce di $1$ , mentre il resto delle monete rimane fermo al suo posto.
Monovariante 1: $\sum_{m \in M} (p(m))^2$
Cioè la somma dei quadrati delle posizioni delle monete varia in modo controllato. In particolare, il nostro monovariante cresce ad ogni mossa di $2$ , infatti
$2p(m)^2 \longrightarrow (p(m)-1)^2 +(p(m)+1)^2= 2p(m)^2 +2$ e tutte le altre monete rimangono ferme al loro posto.
(Ammetto che questo modo fighissimo di trovare un monovariante l'avevo già visto usato in un altro esercizio
)
Grazie all' invariante trovato si può affermare che il centro di massa di $M$ rimane sempre costante mossa dopo mossa ( sostanzialmente il baricentro di tutte le monete è sempre fisso in un certo punto della nostra retta)
Ora, osserviamo che quando due sequenze si uniscono, il nuovo punto di massa sarà compreso tra i punti di massa precedenti. Considerando quindi la sequenza fantastica più a destra, il suo centro di massa può soltanto spostarsi a sinistra o rimanere fermo. Analogamente per la sequenza più a sinistra.
Ora, grazie al monovariante trovato ed all'osservazione precedente, si giungerà ad un punto in cui la quantità non potrà più crescere poiché significherebbe spostare il baricentro di una sequenza fantastica oltre un certo limite, quindi la quantità sarà costante da un punto in poi, ovvero non si potranno effettuare più mosse e si sarà raggiunta la configurazione finale di tante pile con una sola moneta.
Abbiamo finalmente ottenuto che, presa una certa configurazione, esisterà un naturale $l$ tale che non è possibile raggiungere la configurazione finale con $l+1$ mosse o più, ma al massimo con $l$. Ora, visto che siamo nei naturali, prendo il minimo $l$ e lo chiamo $A$ .
Manca da dimostrare che la configurazione finale è unica ed il numero di mosse è fissato. Dimostrata l'unicità, per il nostro bellissimo monovariante che cresce di $2$ in $2$ ad ogni mossa , il numero di mosse è fissato e si può anche calcolare nota la configurazione iniziale e quella finale(che ci sono per ipotesi). Ora per dimostrare l'unicità si procede per induzione su $A$ e si finisce senza troppi sforzi.
Faccio soltanto il passo base (se volete lo completo dopo oppure qualcuno lo faccia al posto mio) perché la mia povera tastiera sta friggendo dopo questo lunghissimo messaggio ) .
Passo base: $A=0$ . Allora la configurazione iniziale è costituita da tante pile con una sola moneta e quindi coincide con quella finale.
Passo induttivo: ai posteri !
Definiamo inoltre sequenza fantastica (ogni riferimento al problema 4 è puramente casuale), una successione massima di pile di monete priva di due o più pile vuote consecutive ( con massima intendo che l'intero precedente alla prima pila è vuoto e l'intero successivo all'ultima pila è vuoto). Quindi in questo nostro insieme vi sono al massimo due pile piene separate da una pila vuota.
La cosa fighissima di questa nostra sequenza è che ha tante proprietà controllabili:
$\bullet $ Una sequenza fantastica non può suddividersi in due sequenze fantastiche poiché non posso creare due pile vuote consecutive con una mossa.
$\bullet$ Due sequenze fantastiche possono unirsi tra loro e divenire un'unica sequenza super fantastica ( o soltanto fantastica).
$\bullet$ Il numero di sequenze fantastiche è debolmente decrescente ( poiché non posso creare sequenze fantastiche ma soltanto unirle)
Troviamo ora un invariante ed un monovariante che saranno utili nella nostra soluzione:
Invariante 1: $\sum _{m \in M} p(m)$
Cioè la somma delle posizioni delle monete non varia mai. Ciò si giustifica abbastanza intuitivamente dicendo che ad ogni mossa che agisce su due monete $m_h,m_k$ , la posizione di una aumenta di $1$ e la posizione dell'altra diminuisce di $1$ , mentre il resto delle monete rimane fermo al suo posto.
Monovariante 1: $\sum_{m \in M} (p(m))^2$
Cioè la somma dei quadrati delle posizioni delle monete varia in modo controllato. In particolare, il nostro monovariante cresce ad ogni mossa di $2$ , infatti
$2p(m)^2 \longrightarrow (p(m)-1)^2 +(p(m)+1)^2= 2p(m)^2 +2$ e tutte le altre monete rimangono ferme al loro posto.
(Ammetto che questo modo fighissimo di trovare un monovariante l'avevo già visto usato in un altro esercizio
)Grazie all' invariante trovato si può affermare che il centro di massa di $M$ rimane sempre costante mossa dopo mossa ( sostanzialmente il baricentro di tutte le monete è sempre fisso in un certo punto della nostra retta)
Ora, osserviamo che quando due sequenze si uniscono, il nuovo punto di massa sarà compreso tra i punti di massa precedenti. Considerando quindi la sequenza fantastica più a destra, il suo centro di massa può soltanto spostarsi a sinistra o rimanere fermo. Analogamente per la sequenza più a sinistra.
Ora, grazie al monovariante trovato ed all'osservazione precedente, si giungerà ad un punto in cui la quantità non potrà più crescere poiché significherebbe spostare il baricentro di una sequenza fantastica oltre un certo limite, quindi la quantità sarà costante da un punto in poi, ovvero non si potranno effettuare più mosse e si sarà raggiunta la configurazione finale di tante pile con una sola moneta.
Abbiamo finalmente ottenuto che, presa una certa configurazione, esisterà un naturale $l$ tale che non è possibile raggiungere la configurazione finale con $l+1$ mosse o più, ma al massimo con $l$. Ora, visto che siamo nei naturali, prendo il minimo $l$ e lo chiamo $A$ .
Manca da dimostrare che la configurazione finale è unica ed il numero di mosse è fissato. Dimostrata l'unicità, per il nostro bellissimo monovariante che cresce di $2$ in $2$ ad ogni mossa , il numero di mosse è fissato e si può anche calcolare nota la configurazione iniziale e quella finale(che ci sono per ipotesi). Ora per dimostrare l'unicità si procede per induzione su $A$ e si finisce senza troppi sforzi.
Faccio soltanto il passo base (se volete lo completo dopo oppure qualcuno lo faccia al posto mio) perché la mia povera tastiera sta friggendo dopo questo lunghissimo messaggio
) .Passo base: $A=0$ . Allora la configurazione iniziale è costituita da tante pile con una sola moneta e quindi coincide con quella finale.
Passo induttivo: ai posteri !