28. Gioco con 2013 palline

[xXStephXx]

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.

[xXStephXx]

Uppo, visto che è passata una settimana

Dovrebbero bastare 3 osservazioni e ci sono due invarianti abbastanza comuni

[simone256]

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

Testo nascosto:

1)L' ordine come anticipato è indifferente... Facile dimostrare che se scambiamo l'ordine di due mosse il risultato non cambia; da qui possiamo estendere il ragionamento su tutte le mosse. Mi pare ci fosse qualcosa di simile nel video di Combinatoria 2 del Basic 2012;
2)Invariante curioso (non so dove possa portare):
una pallina in una casella i assume "valore i"; chiamiamo t la somma dei valori di tutte le palline. Si nota facilmente che mossa dopo mossa t è invariante e uguale a 2013

[auron95]

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

[xXStephXx]

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

[auron95]

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.

[simone256]

@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

[xXStephXx]

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

Testo nascosto:

Dopo aver dimostrato che la configurazione finale è unica, so che è unica anche la quantità finale $\sum x^2p(x)$ dove $x$ è l'indice di una posizione e $p(x)$ il numero di palline su quella posizione. (quello che ha detto auron). Io conosco quanto vale all'inizio $\sum x^2p(x)$ e sapendo che aumenta di $2$ ad ogni mossa, è unico anche il numero di mosse che mi servono per raggiungere la quantità finale

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

[auron95]

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.

[xXStephXx]

Ok Dai vai col prossimo