telematica unimi 1

[enomis_costa88]

Questo secondo me è il più bel problema dell'ultima telematica (su su fate lo sforzo di leggere il testo del problema)

Consideriamo il seguente problema, vagamente ispirato al gioco africano chiamato
Mancala.
Abbiamo varie scatole contenenti dei semi disposte intorno ad una circonferenza.
Ogni mossa consiste nel prendere tutti i semi di una scatola e distribuirli, uno alla volta, nelle scatole successive, muovendosi in senso orario intorno alla circonferenza.
Per esempio, se abbiamo 3 scatole contenenti rispettivamente 5,4 e 3 semi se scegliamo la scatola con i 5 semi dopo la ridistribuzione le scatole conterranno rispettivamente 1,6 e 5 semi.

Dimostrare questi due fatti:

a) se decidiamo di scegliere sempre la scatola dove è stato messo l’ultimo seme della ridistribuzione precedente allora dopo un certo numero di mosse si ritrova la distribuzione iniziale.

b) se ad ogni mossa si è liberi di scegliere la scatola per la successiva ridistribuzione allora partendo da una distribuzione qualsiasi possiamo ottenere, dopo un numero opportuno di mosse, una qualsiasi altra distribuzione, per esempio dalla distribuzione con 5,4 e 3 semi possiamo ottenere la distribuzione 6,0 e 6 semi come possiamo ottenere 12,0,0.

Buon lavoro!

[rand]

Sarei curioso di sapere se la soluzione è basata sul fatto che la mosse sono "invertibili" o si può fare qualcosa di più intelligente. Invertibili nel senso che da due distribuzioni distinte non si può arrivare nella stessa effettuando una mossa che mette l'ultimo seme nella stessa scatola.

[moebius]

Per il primo punto direi che la soluzione è quella e mi sembra che sia abbastanza "elegante"... per il secondo non credo che basti, ma ci devo ancora pensare.

[enomis_costa88]

Per il primo punto l'idea è quella..magari se qualcuno la scrivesse per bene..

Per il secondo da sola non basta..bè sforzatevi su che è veramente bello

[Marco]

Per il secondo da sola non basta..bè sforzatevi su che è veramente bello

Sono d'accordo con E.C.: è veramente bello.
Punto 2:

E' facile dimostrare che da ogni configurazione posso ammucchiare tutte le pietre nel bussolotto più a destra: ad esempio basta muovere sempre pescando dal bussolotto più a sinistra che contiene pietre. A questo punto, per il punto 1, è anche vero che dalla posizione con le pietre tutte a destra si può raggiungere qualunque configurazione, dato che le mosse sono reversibili. Quindi da una qualunque configurazione, è possibile raggiungere qualunque altra. []