Giocare con le monete

Pasquale · Messaggio da **Pasquale** » gio apr 13, 2006 12:23 am

Abbiamo N monete da 2€ ed N-1 monete da 1€ disposte alternativamente sul tavolo (es: 2-1-2-1-2-1-2) : una mossa consiste nello spostare una coppia di monete adiacenti ad un capo della riga di monete, facendo quindi slittare e così riunire tutte le monete. Qual è il numero minimo di mosse necessario per sistemare tutte le monete da 2€ da un lato e tutte quelle da 1€ dall'altro?

Immagine

jepa · Messaggio da **jepa** » mar mag 02, 2006 10:34 pm

Scusa Pasquale, non ho ben capito cosa intendi per mossa, cioè come intendi possibile lo spostamento delle monete.

Pasquale · Messaggio da **Pasquale** » mer mag 03, 2006 2:53 am

Bisogna prendere 2 monete adiacenti con due dita e farle scivolare in cima, a destra o a sinistra; quindi il vuoto che resta va riempito, accostando tutte le monete le monete.

es:

situazione iniziale

dopo la prima mossa

dopo la seconda mossa

Se ancora non ti è chiaro, farò un disegno più dettagliato, con freccette, ecc.

jepa · Messaggio da **jepa** » mer mag 03, 2006 7:52 am

Chiarissimo grazie!

Messaggio da **Admin** » mer mag 03, 2006 9:54 pm

Questa è la mia soluzione in 6 mosse:

Immagine

non saprei come dimostrare che il numero di mosse sia minimo, ammesso che lo sia.

Ciao
Admin

jepa · Messaggio da **jepa** » mer mag 03, 2006 11:26 pm

Ho ricavato due formule che dipendono dal fatto che in numero n di monete da 2 € siano pari o dispari:
Per un numero n pari ho che il numero di minimo mosse M è dato da:
M=1+3*(n-2)/2
Per un numero n dispari di monete da 2 € si ha
M=2+3(n-3)/2

Ho infatti ottenuto in base al numero di monete da 2 € i seguenti risultati:
n=2 M=1
n=3 M=2
n=4 M=4
n=5 M=5
n=6 M=7
n=7 M=8
n=8 M=10
n=9 M=11

La mia soluzione da 5 monete da 2 € in 5 mosse è:

2 1 2 1 2 1 2 1 2 muovo le monete 7 e 8 a dx
1) 2 1 2 1 2 1 2 2 1 muovo le monete 4 e 5 a dx
2) 2 1 2 1 2 2 1 1 2 muovo le monete 2 e 3 a dx
3) 2 1 2 2 1 1 2 2 1 muovo le monete 2 e 3 a sx
4) 2 2 2 1 1 1 2 2 1 muovo le monete 7 e 8 a sx
5) 2 2 2 2 2 1 1 1 1

Per lo meno così mi pare che sia,saluti a tutti!

Messaggio da **Admin** » gio mag 04, 2006 1:13 pm

Ciao jepa,
non mi trovo con la tua soluzione in 5 mosse, ma probabilmente l'ho mal compresa;
potresti spiegarla meglio?

Ciao
Admin

jepa · Messaggio da **jepa** » gio mag 04, 2006 6:23 pm

Allora, immaginiamo di numerare le monete da sinistra verso destra con numeri da 1 a 9 per indicarne la posizione:

La situazione iniziale è:
2 1 2 1 2 1 2 1 2

1° mossa muovo le monete che occupano la posizione 7 e 8 a destra e ottengo

2 1 2 1 2 1 2 2 1

2° mossa muovo le monete che occupano la posizione 4 e 5 a destra e ottengo

2 1 2 1 2 2 1 1 2

3° mossa muovo le monete che occupano la posizione 2 e 3 a destra e ottengo

2 1 2 2 1 1 2 2 1

4° mossa muovo le monete che occupano la posizione 2 e 3 a sinistra e ottengo

2 2 2 1 1 1 2 2 1

5° mossa muovo le monete che occupano la posizione 7 e 8 a sinistra e ottengo

2 2 2 2 2 1 1 1 1

Chiedo scusa ma non sono capace di postare immagini e schemi, ma imparerò presto, spero di essere stato più chiaro, a presto.

Messaggio da **Admin** » gio mag 04, 2006 7:57 pm

jepa ha scritto:2 1 2 1 2 2 1 1 2

3° mossa muovo le monete che occupano la posizione 2 e 3 a destra e ottengo

2 1 2 2 1 1 2 2 1

qui c'è un errore.
O sbaglio?

Ciao
Admin

jepa · Messaggio da **jepa** » gio mag 04, 2006 8:04 pm

Non mi pare ci sia errore, ho

2 1 2 1 2 2 1 1 2
se sposto le monete in posizione 2 e 3 a destra, ottengo

2 1 2 2 1 1 2 2 1

scusa ma non vedo l'errore.

Messaggio da **Admin** » ven mag 05, 2006 8:05 am

se abbiamo supposto le monete numerate da 1 a 9, allora le monete in posizione 2 e 3 sono quelle in rosso:

2 1 2 1 2 2 1 1 2

spostandole a destra, cioè in coda alla stringa ottengo:

2 1 2 2 1 1 2 1 2

e non

2 1 2 2 1 1 2 2 1

Mi sembra ovvio, ma forse ho frainteso.

Ciao
Admin

jepa · Messaggio da **jepa** » ven mag 05, 2006 8:08 am

Hem le monete 3 e 4 e non 2 e 3 scusami.

jepa · Messaggio da **jepa** » ven mag 05, 2006 8:10 am

E anche nella successiva sono le monete 3 e 4 e non 2 e 3, boh devo avere qualche forma di dislessia visiva....
le guardavo e le vedevo come 2 e 3, bah cmq lo spostamento è giusto.
Chiedo venia.

Messaggio da **Admin** » ven mag 05, 2006 9:24 pm

Ok;
in pratica il problema si riduce a dimostrarne l'impossibilità con sole 4 mosse.

Ciao
Admin