Pile saltellanti in modo malo

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
karlosson_sul_tetto
Messaggi: 1435
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Pile saltellanti in modo malo

Messaggio da karlosson_sul_tetto » 13 mag 2014, 07:48

Tratto da un problema dei kangourou 2014, versione letta male da me e kfp che non mi vuole bene e inizialmente da dandav EDIT$ _2 $: anche da NoAnni. Da tutto il male insomma.

Sono date alcune pile di monete con alcune monete dentro (tutto generico). Una mossa consiste nel scegliere una pila, togliere una moneta da quella pila e dividere la pila in due parti, con la condizione che ciascuna delle due pile deve avere almeno una moneta. (Quindi una mossa può essere pila da 8---> pila da 2 e pila da 5).
"Discutere delle possibili strategie vincenti"
EDIT: giustamente non si sa come si vince ergo le strategie possono essere qualunque. Si perde quando non si può muovere
Ultima modifica di karlosson_sul_tetto il 18 mag 2014, 12:30, modificato 2 volte in totale.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

matpro98
Messaggi: 454
Iscritto il: 22 feb 2014, 18:42

Re: Pile saltellanti in modo malo

Messaggio da matpro98 » 13 mag 2014, 08:08

Si vince quando rimangono solo colonne da 1?

Avatar utente
karlosson_sul_tetto
Messaggi: 1435
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Pile saltellanti in modo malo

Messaggio da karlosson_sul_tetto » 13 mag 2014, 21:32

Si me n'ero scordato, sorry. Editato :oops:
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

matpro98
Messaggi: 454
Iscritto il: 22 feb 2014, 18:42

Re: Pile saltellanti in modo malo

Messaggio da matpro98 » 14 mag 2014, 07:59

Adesso va meglio... poi ci provo ;)

BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Re: Pile saltellanti in modo malo

Messaggio da BorisM » 14 mag 2014, 21:25

Ma le due colonne ottenute da una pila spezzata possono essere aggiunte ad un altra pila?

Avatar utente
karlosson_sul_tetto
Messaggi: 1435
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Pile saltellanti in modo malo

Messaggio da karlosson_sul_tetto » 15 mag 2014, 12:37

BorisM ha scritto:Ma le due colonne ottenute da una pila spezzata possono essere aggiunte ad un altra pila?
No, una volta che hai diviso una colonna in due parti poggi a terra due colonne e non puoi unirle con niente.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Re: Pile saltellanti in modo malo

Messaggio da BorisM » 15 mag 2014, 17:20

Allora se ho ho ben capito il problema dice che abbiamo $m$ pile ciascuna avente un numero di monete e si vince quando si ottengono tutte colonne con una moneta.
Distinguiamo due casi:
- il numero delle monete di una colonna è dispari $2n+1$;
- il numero delle monete di una colonna è pari $2n$.
1° caso: $2n+1$
Analiziamo i "casi base"
per n=0 ho vinto perchè ho una sola monetina
per n=1 posso spezzare la pila da 3 in due togliendo la seconda moneta dall' alto o dal basso, ottenere cosi 2 pile da 1 e vincere.
per n=2 posso anche qui spezzare la pila da 5 in due togliendo la seconda moneta dall' alto o dal basso ed ottenendo quindi una pila da 1 e una da 3 per la quale possiamo ripetere il passaggio gia descritto in precedenza.
Dimostriamo per induzione che si può vincere se il numero di monete contenute in una pila è dispari.
ipotiziamo che per $2n+1$ si può vincere. Prendiamo allora una fila di $2n+3$ monete. Se noi eseguiamo la mossa "togli la seconda moneta dall' alto o la seconda dal basso" otteniamo una pila da $1$ ed una pila da $2n +3-2=2n+1$ quindi utilizzando l' ipotesi si può dire che anche questa pila può essere scomposta in pile da uno.
2° caso: $2n$
Ogni qualvolta dividiamo una pila otteniamo una pila avente un numero dispari di monete ed una avente un numero pari di monete. Per quanto detto in precedenza la pila avente un numero dispari di monete può essere scoposta in pile da $1$. Concentriamoci allora sulla pila avente numero pari di monete: $2n$.
Notiamo che in qualsiasi modo la dividiamo otteniamo sempre una colonna pari ed una dispari. Alla fine quindi ripetendo il procedimento arriveremmo ad una pila da $4$ essa può essere scomposta in una pila da $2$ ed una da $1$. Ma la pila da $2$ non è divisibile.
CONCLUSIONE:
La strategia è quella di togliere la seconda moneta dall' alto o dal basso e ripetere questa mossa alla colonna maggiore di quelle ottenute fintanto che non avremmo ottenuto solo pile da $1$ moneta. Tuttavia questa strategia ci permette di vincere se e solo se tutte le $m$ colonne sono composte da un numero dispari di monete. Nel caso in cui anche una sola colonna contenga un numero pari di monete essa non sarà scomponibile e quindi non si potrà vincere.

matpro98
Messaggi: 454
Iscritto il: 22 feb 2014, 18:42

Re: Pile saltellanti in modo malo

Messaggio da matpro98 » 15 mag 2014, 18:45

Non ho letto tutto, ma mi pare che non funzioni: vinci anche se lasci solo colonne da 2, l'obiettivo è lasciare colonne da 1 e da 2, non esclusivamente da 1 ;)

BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Re: Pile saltellanti in modo malo

Messaggio da BorisM » 15 mag 2014, 19:38

matpro98 ha scritto:Non ho letto tutto, ma mi pare che non funzioni: vinci anche se lasci solo colonne da 2, l'obiettivo è lasciare colonne da 1 e da 2, non esclusivamente da 1 ;)
Allora il mio metodo funziona perchè alla fine otterremo sempre tutte colonne da 1 per numeri dispari e tutte colonne da 1 più una da 2 per numeri pari

matpro98
Messaggi: 454
Iscritto il: 22 feb 2014, 18:42

Re: Pile saltellanti in modo malo

Messaggio da matpro98 » 16 mag 2014, 07:01

Aspetta... prima una domanda: ma ci sono due giocatori, di cui quello che non può muovere perde, o è un solo giocatore? Perché in quest ultimo caso, il gioco secondo me non ha senso... comunque, sempre nel caso di un solo giocatore, non c'è una vera e propria strategia: qualsiasi mossa faccia, si arriva a un punto in cui ci sono solo colonne da 1 e da 2... o mi sbaglio?

Avatar utente
karlosson_sul_tetto
Messaggi: 1435
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Pile saltellanti in modo malo

Messaggio da karlosson_sul_tetto » 16 mag 2014, 12:51

matpro98 ha scritto:Aspetta... prima una domanda: ma ci sono due giocatori, di cui quello che non può muovere perde, o è un solo giocatore? Perché in quest ultimo caso, il gioco secondo me non ha senso... comunque, sempre nel caso di un solo giocatore, non c'è una vera e propria strategia: qualsiasi mossa faccia, si arriva a un punto in cui ci sono solo colonne da 1 e da 2... o mi sbaglio?
Si, ci sono due giocatori...se vuoi puoi generalizzare a n :)
Comunque la cosa che lo rende bastardo è che la mossa non consiste nel dividere una colonna di n in $ n-2 $ e 1: se ogni giocatore facesse questo dipenderebbe dalla parità. Metti invece che siamo arrivati ad una pila di 5. Se io tolgo una e la divido in 3 e 1, perdo poiché l'avversario stacca il 3. Allora divido in 2 e 2 vincendo, nel caso di una pila. Se invece abbiamo due pile da 5, l'avversario farà la mossa simmetrica vincendo, ergo non mi conviene. Con il crescere di pile e monete la parità va abbastanza a farsi fottere...
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

NoAnni
Messaggi: 215
Iscritto il: 12 feb 2011, 14:32
Località: Roma

Re: Pile saltellanti in modo malo

Messaggio da NoAnni » 18 mag 2014, 10:22

Lo avevo letto anche io così all'inizio... Per fortuna ci ho perso solo un'oretta, poi ho capito bene.
Certo dovrebbero stare attenti nell'uso dei pronomi...
"Problem solving can be learned only by solving problems"

Rispondi