Nim — 9. Poker Nim

«Ora modifichiamo un po' le regole del gioco. Prendiamo uno di quei set per giocare a poker, con tanti gettoni colorati».

«Belli, mi piacciono».

«Abbiamo a disposizione una riserva di gettoni, diciamo 50, e giochiamo normalmente a Nim, con una regolina in più».

«Quale?».

«Possiamo aggiungere a una pila un qualunque numero di gettoni, purché li possediamo».

«Possiamo giocare anche quelli che togliamo giocando normalmente?».

«Certo. Allora, 50 gettoni a testa, sul tavolo tre pile che formano, uhm, diciamo un Nim (3,2,1). Vai, comincia tu».

«Allora, so che (3,2,1) è una situazione che mi è sfavorevole, perché è un gioco nullo».

«Quindi vincerei io».

«Sì. Allora provo a modificare la situazione. Uso 10 dei miei gettoni e li metto nella pila da 3: (13,2,1). Tocca a te».

«Bene, tolgo 10 gettoni dalla prima pila. Ecco qua: (3,2,1)».

«Mh, temo di essere stato fregato ancora una volta».

«Già».

«Avere a disposizione delle pedine in più non serve a niente, se un gioco era a tuo favore prima della mia mossa, lo sarà anche dopo, perché tu puoi cancellare tutte le mosse in cui io aggiungo dei gettoni».

«È così. La morale della storia è: è inutile poter aggiungere delle pedine».

«Bene. A cosa serve questa morale, oltre a farmi perdere un'altra volta?».

«Serve per una importante generalizzazione. Dobbiamo formalizzare un po' i ragionamenti fatti fino ad ora. Siamo d'accordo sul fatto che il Nim più semplice è quello composto da una sola pila, vero?».

«Naturalmente».

«Allora, utilizziamo questa notazione: un gioco rappresentato da una singola pila Nim viene scritto mettendo, tra parentesi graffe, l'elenco delle mosse possibili».

«Quindi quello che abbiamo sempre indicato con (3), cioè un Nim che ha una sola pila con tre pedine, come sarebbe scritto?».

«Sarebbe scritto così: (3)={*0, *1, *2}».

«Vedo che non hai scritto delle mosse, ma dei nimeri».

«Sì, ma praticamente è la stessa cosa. Significa che da (3) puoi prendere tutte e tre le pedine, arrivando a (0), il cui nimero è 0, o anche *0».

«Sì, ricordo che lo zero è sempre lo zero».

«Oppure puoi prendere due pedine, arrivando a (1)».

«Il cui nimero è *1, ho capito. Oppure posso prendere una sola pedina, arrivando a (2), cioè *2».

«Bene. Avrai notato che abbiamo scritto un nimero come l'insieme dei nimeri minori di esso».

«Veramente no».

«Ma sì, abbiamo appena scritto che (3) = *3 = {*0, *1, *2}».

«Ah, già».

«Ecco, se questo ti ricorda qualcosa sui numeri ordinali, non è un caso».

«Oh».

«Ma facciamo finta di niente, e andiamo avanti».

«Benissimo».

«Ora, Nim più complicati di quelli appena considerati, cioè con più pile, possono essere visti come somme di Nim più semplici».

«Per esempio?».

«Per esempio il nostro amico (3,2,1) può essere visto come G + H + K, dove G = {*0,*1,*2}, H = {*0,*1} e K = {*0}».

«Va bene, ma ancora non vedo l'utilità».

«Ci arriviamo subito. Supponi di avere un gioco fatto così: G = {*0, *1, *2, *5, *6}».

«Fammi capire».

«Tu puoi fare una delle mosse indicate tra parentesi, cioè puoi scegliere solo uno di quei nimeri».

«Ancora non mi è chiaro, ma che gioco è?».

«È come se tu avessi un Nim con una sola pila, con 3 elementi».

«In quel caso potrei togliere una, due oppure tre pedine».

«Giusto, arrivando a *2, *1 oppure *0. Poi hai a disposizione due mosse in più: potresti aggiungere delle pedine in modo da avere una pila da 5 elementi, oppure una da 6».

«Ah, ok, direi di aver capito la notazione».

«Bene, diciamo che il gioco G fa parte di un gioco più articolato, così come il Nim (3,2,1) è composto da (3) e da altri giochi, cioè (2) e (1)».

«Uhm, ok».

«Possiamo indicare il gioco più articolato con G + H + K +…, senza specificare cosa siano H, K e tutto quello che segue».

«Va bene».

«Ora supponi che io possieda una strategia per vincere in *3 + H + K +…, così come ce l'avevo per *3 + *2 + *1, il nostro amico Nim (3,2,1)».

«Sto seguendo».

«Bene, il ragionamento fatto poco fa sul Poker Nim ci fa capire che la mia strategia vincente funziona anche per G + H + K +…».

«Vediamo: il motivo è dovuto al fatto che se io faccio qualche mossa che sta in G ma non in *3, tu puoi sempre annullarla?».

«Benissimo! Per capire meglio, ti faccio un esempio. Giochiamo a G + *2 + *1. In pratica abbiamo un Nim (3,2,1) in cui sono disponibili due mosse in più: portare la prima pila a 5 oppure a 6 elementi».

«Immagino di dover cominciare io?».

«Certo».

«Ok, tanto questa volta so già come andrà a finire. Allora, da (3,2,1) passo a (5,2,1)».

«Bene. Questo significa che dall'insieme delle mosse possibili di G, cioè {*0, *1, *2, *5, *6}, tu hai scelto *5. Questa è la situazione che tu passi a me, cioè io devo giocare in *5 + *2 + *1».

«Ok».

«Allora scelgo di giocare in *5, che corrisponde all'insieme delle possibili mosse {*0, *1, *2, *3, *4}, e in particolare scelgo *3. In pratica sono passato da (5,2,1) a (3,2,1). Ora tocca a te giocare in *3 + *2 + *1».

«E mi hai fregato ancora».

«Sì, ho usato la strategia del Poker Nim, generalizzando un po' l'idea. Il concetto fondamentale che abbiamo imparato è questo: {*0, *1, *2, *5, *6} è equivalente a {*0, *1, *2}, cioè *3».

«Eh, sì, se io provo ad aumentare la pila tu la diminuisci subito».

«Ok. Ti lascio digerire un po' il tutto, la prossima volta scriviamo per bene la legge, che sarà una legge fondamentale per la teoria dei giochi».

«Wow».