Pagina 1 di 1

Monete in riga

Inviato: mer dic 28, 2011 6:56 pm
da Gianfranco
Cari amici,
Posto qui un problema che presto metterò anche nel sito.

Su un tavolo c'è una riga di 10 monete, tutte in euro ma di valori non tutti uguali.
La figura allegata è soltanto un esempio.

Immagine

Alice prende una moneta da uno dei due estremi della fila.
Bob prende una moneta da uno dei due estremi della fila rimasta.
La pesca alternata di monete continua allo stesso modo fino a quando Bob prende l'ultima moneta.

Dimostrate che Alice può giocare in modo tale da garantirsi, alla fine, una somma di denaro non minore di quella di Bob.
Non si chiede di trovare la strategia migliore ma una strategia semplice, intutitiva, quasi immediata da realizzare e valida per un qualunque numero pari di monete.

Ho trovato questo problema nel libro di Peter Mann Winkler, Mathematical Puzzles: A connoisseur's collection, 2003.

Buon anno a tutti
Gianfranco

Re: Monete in riga

Inviato: sab dic 31, 2011 5:35 pm
da Admin
Ciao Gianfranco,
ti ringrazio ancora per aver postato il problema, che trovo molto ricreativo.

Bene, dopo aver percorso un pò di stradine tortuose di montagna, mi pare di aver visto l'autostrada.

L' "illuminazione" consiste nel rendersi conto che Alice può sempre prendere tutte le monete di posizione dispari o tutte quelle di posizione pari, indipendentemente dalle scelte di Bob.
Infatti, indicando per comodità con $D$ le monete di posizione dispari, e con $P$ quelle di posizione pari, si ha che all'inizio, i due estremi sono di tipo $(D , P)$.
Se Alice sceglie $D$, i nuovi estremi saranno di tipo $(P , P)$, per cui Bob dovrà scegliere per forza $P$.
I nuovi estremi saranno quindi di nuovo di tipo $(D, P)$ e Alice potrà scegliere di nuovo $D$.
E così via fino alla fine delle monete.
Stesso discorso, ovviamente, se Alice sceglie $P$ all'inizio.

Pertanto, ad Alice basterà effettuare la somma delle monete di posizione dispari e la somma delle monete di posizione pari;
dopo di che sceglierà di prendere il gruppo di monete con somma maggiore.

SE&O
Admin

Re: Monete in riga

Inviato: lun gen 02, 2012 6:21 pm
da David
Ah i controlli di parità! Così semplici ma così profondi!

Re: Monete in riga

Inviato: lun gen 02, 2012 6:43 pm
da Gianfranco
Complimenti Admin, risposta esatta e spiegazione ottima!
Non so se c'entrano i controlli di parità.

In effetti, dato un qualunque insieme di numeri formato da un numero pari di elementi, in qualunque modo lo si suddivida in due sottoinsiemi equipotenti (formati dallo stesso numero di elementi) succederà banalmente sempre che la somma dei numeri di uno dei due sottoinsiemi sarà >= di quella dell'altro.
In questo gioco bisogna trovare una suddivisione che obblighi l'avversario a prendere l'insieme con somma <=.
La suddivisione proposta da Admin va bene a questo scopo.

Ciao
Gianfranco

Re: Monete in riga

Inviato: mar gen 03, 2012 4:01 am
da Pasquale
Una breve osservazione:

se la fila è più lunga, restando di pezzi pari,
se i valori maggiori sono sistemati in posizioni più centrali,
se, per esempio, resta più favorevole la serie dei dispari, ma non soltanto per un soffio,

il primo a giocare può permettersi anche il lusso di sbagliare la prima mossa, senza subirne alcuna conseguenza.

Abbiamo visto che se il primo prende dispari alla prima mossa, lascia due estremi pari, per cui resta in grado di continuare a prendere successivamente sempre dispari, mentre il secondo potrà prendere solo e sempre pari, ove il primo continui a prendere sempre dispari al suo turno.

Se però il primo prende pari alla prima mossa, può comunque prendere sempre dispari dalla seconda mossa in poi; non si ripete la situazione precedente, perché lasciando due dispari, il secondo pur prendendone uno, ne lascerà un altro a disposizione.

Nella prima situazione, dopo la prima mossa, vengono lasciati due pari su una quantità dispari di monete; nella seconda, vengono lasciati due dispari su una quantità dispari di monete.

Penso proprio che entri nel gioco la questione delle parità, anche se trattasi di un concetto che non ho mai fissato bene nella mente.