Il nim con gli ordinali
Inviato: 14 ago 2009, 17:35
Alberto e Barbara (e chi sennò?) si sono stufati di giocare al nim classico, perciò ora si dedicano ad una nuova versione molto più emozionante.
Ci sono sul tavolo $ n $ pile di monete, con $ n\in\mathb{N} $, ma mentre nel nim classico ogni pila contiene una quantità finita di monete, stavolta ogni pila è un insieme ben ordinato di monete, quindi può contenere anche infinite monete (ma d'altra parte lo sapevamo che Alberto e Barbara non hanno davvero problemi economici, sennò non passerebbero tutto il loro tempo a giocare).
I giocatori muovono alternativamente a cominciare da Alberto. Una mossa consiste nello scegliere una pila non vuota, scegliere una moneta all'interno della pila ed eliminare quella moneta e tutte le monete più in alto. Vince chi toglie l'ultima moneta.
1) Dimostrare che prima o poi il gioco finisce, ovvero non esiste una sequenza infinita di mosse.
2) Deteminare una strategia vincente nel caso in cui tutte le pile hanno un numero finito di monete (il nim classico)
3) Determinare una strategia vincente nel caso generale (il nuovo nim).
Per eventuali dubbi consultare
http://it.wikipedia.org/wiki/Buon_ordinamento
e anche la voce correlata sui numeri ordinali (ma perché non riesco a inserire due collegamenti a due siti diversi? Se lo faccio scompare tutto il messaggio).
Ci sono sul tavolo $ n $ pile di monete, con $ n\in\mathb{N} $, ma mentre nel nim classico ogni pila contiene una quantità finita di monete, stavolta ogni pila è un insieme ben ordinato di monete, quindi può contenere anche infinite monete (ma d'altra parte lo sapevamo che Alberto e Barbara non hanno davvero problemi economici, sennò non passerebbero tutto il loro tempo a giocare).
I giocatori muovono alternativamente a cominciare da Alberto. Una mossa consiste nello scegliere una pila non vuota, scegliere una moneta all'interno della pila ed eliminare quella moneta e tutte le monete più in alto. Vince chi toglie l'ultima moneta.
1) Dimostrare che prima o poi il gioco finisce, ovvero non esiste una sequenza infinita di mosse.
2) Deteminare una strategia vincente nel caso in cui tutte le pile hanno un numero finito di monete (il nim classico)
3) Determinare una strategia vincente nel caso generale (il nuovo nim).
Per eventuali dubbi consultare
http://it.wikipedia.org/wiki/Buon_ordinamento
e anche la voce correlata sui numeri ordinali (ma perché non riesco a inserire due collegamenti a due siti diversi? Se lo faccio scompare tutto il messaggio).