problema 6 cesenatico 2008

[bestiedda]

dato che non ho trovato una sezione "teoria dei giochi" lo posto qui:

Francesca e Giorgia fanno il seguente gioco. Sul tavolo ci sono inizialmente alcune colonne di monete. Ogni colonna può contenere un certo numero di monete, che può eventualmente variare da colonna a colonna. A turno, ogni giocatrice fa una e una sola delle seguenti mosse:
1)sceglie una colonna contenente un numero pari non nullo 2k di monete e la sostituisce con due colonne contenenti k monete
2)leva dal tavolo tutte le colonne contenenti un numero dispari di monete
Nel caso non fosse possibile effettuare una mossa del primo tipo, la giocatrice ne farà necessariamente una del secondo tipo, e viceversa. Inizia francesca. Vince chi prende dal tavolo l'ultima moneta.
a) se inizialmente sul tavolo c'è una sola colonna, la quale contiene $ 2008^{2008} $monete, quale giocatrice ha la strategia vincente?
b)per quali configurazioni iniziali Francesca ha una strategia vincente?


in questo esercizio solo 3 persone hanno fatto 7 punti e la stragrande maggioranza (me compreso ) ha fatto 0 punti

EDIT: spostato in combinatoria: questa teoria dei giochi è olimpicamente [e gobbinianamente] considerata combinatoria (visto che non rientra né in algebra né in geometria né in teoria dei numeri )

[Gargantua]

Provo a rispondere al quesito a.

Affinché il gioco finisca devono rimanere sul tavolo solo una o più colonne dispari; per ottenere ciò si parte dalla mossa obbligata: spaccare in due la prima colonna, che evidentemente è pari (essendo la potenza di un numero pari); le due colonne figlie, se pari, devono a loro volta essere spaccate, per dare origine a 4 colonne di seconda generazione; queste ancora, se pari, devono essere spaccate per dare origine a 8 colonne di terza generazione; questo processo va avanti finché non si giunge alla generazione n di colonne tutte dispari; poiché

$ 2008= 2^3 \cdot 251 2008^{2008} = (2^3 \cdot 251)^{2008} = 2^{6024} \cdot 251^ {2008} $

è evidente che la generazione di colonne tutte dispari è la 6024-esima.
Affinché il gioco finisca è obbligatorio che tutte le colonne pari delle generazioni precedenti ad n vengano spaccate (non è necessario che ciò avvenga in ordine, ma è indispensabile che avvenga); ogni spaccamento è una mossa di primo tipo; una mossa di secondo tipo è possibile solo quando una colonna della generazione n-1 è spaccata per dare origine a due colonne della generazione n.
Il numero di colonne da spaccare per arrivare alla generazione n-1, che è anche il numero di mosse del primo tipo obbligatorie per arrivare fino a quel punto, vale


$ 1+ \sum_{k=0}^{6022}{2^{6024-k} $

Questo numero è dispari, quindi, se non esitessero mosse del secondo tipo, l'ultima mossa del primo tipo fino ad n-1 spetterebbe al giocatore che fa la prima mossa; quando tutte quste mosse sono consumate, il giocatore che si ritrova a giocare è costretto a spaccare una colonna di n-1, generando due colonne dispari di n; in questo modo permette all'altro di scegliere se compiere una mossa di primo o di secondo tipo; se questo scieglie la mossa di secondo tipo, il processo continua identico a sé stesso finché non si consumano le colonne e questo giocatore vince; per cui lo scopo del giocatore che inizia a giocare per primo, che chiamremo giocatore A, è quello di costringere B a eliminare una dietro l'altra le colonne di n-1; abbiamo visto che questo è possibile quando i due giocatori fanno fuori tutte le colonne fino a n-1 senza intaccare n-1; se invece il giocatore B decidesse di intaccare una colonna di n-1 prima di elimiare quelle delle generazoni precedenti, A raccoglie i frutti dello spaccamento con la mossa di secondo tipo e la condanna di B è solo rimandata; per cui in ogni caso, se A rispetta questa semplice regola ha la vittoria in tasca: "non spaccare mai colonne di n-1 e quando lo fa l'avversario fai sempre una mossa di secondo tipo"
Poiché A è il primo a giocare e ha la strategia vincente, B può vincere solo se A commette un errore (non rispettato il precetto che ho enunciato) e lui sa approfittarne.

Se ho commesso degli errori o sono stato poco chiaro dite pure!!