Pile saltellanti in modo malo

[karlosson_sul_tetto]

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

[matpro98]

Si vince quando rimangono solo colonne da 1?

[karlosson_sul_tetto]

Si me n'ero scordato, sorry. Editato

[matpro98]

Adesso va meglio... poi ci provo

[BorisM]

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

[karlosson_sul_tetto]

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.

[BorisM]

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]

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]

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]

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?

[karlosson_sul_tetto]

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

[NoAnni]

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