OliForum Matematico

Ho una stringa infinita numerata con $0,1,2...$
All'inizio ci sono $2013$ palline nella casella $1$. Una mossa consiste nel spostare due palline da una casella alle due adiacenti (1 a destra e 1 a sinistra). Alla casella zero non possono essere applicate mosse. Il gioco finisce quando nessuna casella (esclusa lo $0$) ha almeno $2$ palline.
Mostrare che il gioco prima o poi finisce e che la disposizione finale delle palline non dipende dalle mosse fatte. Determinare inoltre tale disposizione.

Uppo, visto che è passata una settimana

Dovrebbero bastare 3 osservazioni e ci sono due invarianti abbastanza comuni

Butto giù un paio di idee velocemente poi torno su filosofia:

È anche abbastanza semplice dimostrare che il gioco ha termine: basta notare che la somma dei quadrati dei valori delle palline aumenta di 2 a ogni mossa, e per le limitazioni dette da Simone non può assumere valori infiniti (al massimo $2013^2$), tuttavia non ho la più pallida idea di come mostrare qual è la configurazione finale: se mi viene in mente metterò giù la dimostrazione per bene.

@simone256
la 1) non mi convince molto, a volte facendo delle mosse ti precludi delle mosse successive e non sempre puoi fare lo scambio (credo, se ho capito bene)
la 2) invece è molto interessante


@auron95
Ok, quella parte va bene!


In pratica le due invarianti a cui mi riferivo erano quelle...

Ora bisogna osservare una particolarità che forse si nota dopo un bel po' di casi piccoli.

Una cosa carina è che non possiamo avere mai 2 caselle vuote adiacenti e poi una casella successiva occupata (cioè se ho due caselle vuote consecutive, allora tutte le successive sono vuote). Altrimenti vorrebbe dire che non si sono mai riempite (se io ho due caselle di cui una vuota, allora per svuotarne una devo riempire l'altra, e viceversa, quindi non posso svuotarle contemporaneamente) e quindi non si capisce come la pallina nelle caselle più avanzate sia arrivata a quel punto.
Inoltre analizzando un po' di casi piccoli si può notare che alla fine ho sempre le prime $k$ caselle piene a parte eventualmente 1. Dimostrando questo fatto potrei trovare facilmente la configurazione finale per 2013 palline.

xXStephXx ha scritto:@simone256
la 1) non mi convince molto, a volte facendo delle mosse ti precludi delle mosse successive e non sempre puoi fare lo scambio (credo, se ho capito bene)
la 2) invece è molto interessante

Ok nella migliore delle ipotesi mi sono spiegato male e nella peggiore ho sbagliato...
In effetti salto il passaggio che tutti i modi si attuano con lo stesso numero di mosse! In quel caso possiamo affermare che da ogni sequenza 1, 2, 3, ..., n posso raggiungere una qualsiasi altra sequenza di n elementi mediante semplici trasposizioni. Lascio comunque il compito a qualcun'altro di spiegarlo meglio... Oggi davvero non ho tempo

@simone256: se ho capito bene con la prima frase intendi che a prescindere dalle mosse che faccio mi blocco sempre dopo aver fatto lo stesso numero di mosse? Ok, è vero, sarebbe stato interessante aggiungere questo fatto alla tesi del problema iniziale. Ma come lo dimostri? A me viene in mente solo una dimostrazione che però passa già per la tesi del problema. Può darsi che lo puoi dimostrare anche senza passare da quel fatto e magari non me ne sto accorgendo, ma in ogni caso non mi sembra una cosa troppo scontata (può essere che mi sbaglio)

@auron95: mi sa che ti manca poco per concludere

Supponiamo per assurdo che io abbia alla fine una configurazione del tipo
$\begin{equation} \begin{array}{cccccccccc} \dots & 1 & 1 & 0 & 1 & \dots & 1 & 0 & 1 & \dots \end{array} \end{equation}$
ossia con due caselle vuote non terminali. Ragioniamo al contrario: per muovere posso prendere due palline in due caselle separate da una terza e metterle nella casella in mezzo.
Se le caselle non si riempiono, allora non posso portare le palline in fondo fino alla casella iniziale, in quanto le palline si spostano di una casella per volta. In particolare, nelle $k$ caselle tra i due zeri rimarranno sempre $k$ palline. Infatti se io sposto le palline adiacenti in una casella vuota, si crea una casella vuota adiacente e quindi avrò sempre 2 caselle vuote che bloccano $k-1$ palline in $k-1$ caselle. Inoltre, se io provo a fare mosse all'interno delle due caselle vuote, si creano due mini-configurazioni come quella iniziale. Infatti si creano 2 caselle vuote, e quindi la configurazione diventa così:

$\begin{equation} \begin{array}{cccccccccc} \dots & 1 & 0 & 1 & \dots & 1 & \dots & 1 & 0 & 3 & 0 & 1 & \dots & 1 & 0 & 1 & \dots \end{array} \end{equation}$

quindi avrò ai lati del 3 due configurazioni come quelle iniziali. Se ho una configurazione così non posso mai tornare all'inizio, se io continuo a retrocedere prima o poi avrò una configurazione con due 0 vicini (la stessa configurazione critica nel caso limite: due zeri che bloccano zero palline in zero caselle) e quindi non posso più portare le palline dall'altra parte della barricata.

Quindi avrò al massimo uno 0 in mezzo: quindi devo scrivere 2013 come somma dei primi $n$ addendi meno uno: in particolare
$2013 = \sum_{i=1}^{63}i - 3$ quindi avrò le prime 63 caselle piene eccetto la 3a.

Ok Dai vai col prossimo