{"id":2342,"date":"2010-10-15T22:30:36","date_gmt":"2010-10-15T20:30:36","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2342"},"modified":"2022-10-10T21:59:54","modified_gmt":"2022-10-10T19:59:54","slug":"nim-e-gioco-di-wythoff","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2010\/10\/15\/nim-e-gioco-di-wythoff\/","title":{"rendered":"Nim e gioco di Wythoff"},"content":{"rendered":"

Il gioco del Nim<\/strong><\/a> \u00e8 probabilmente l’archetipo dei giochi matematici in senso stretto; quelli cio\u00e8 a cui si pu\u00f2 giocare penso fino a non oltre i sette anni d’et\u00e0 e che per\u00f2 sono amati dai matematici perch\u00e9 possono far vedere quanto sono bravi a risolverlo. Spero che abbiate qualche figlio o nipotino dell’et\u00e0 giusta, per potere apprezzare appieno il gioco, e che siate abbastanza seri da lasciarlo vincere qualche volta, anche se conoscete la strategia perfetta.<\/p>\n

Il Nim si gioca ponendo sul tavolo alcune pile di monete, bastoncini, fagioli o quello che vi pare. Ci pu\u00f2 essere un numero qualunque di pile, anche se con meno di tre il gioco \u00e8 troppo semplice, e ciascuna pila pu\u00f2 avere un numero qualunque di oggetti. A ogni mossa, ciascun giocatore toglie un certo numero di oggetti a sua scelta da una delle pile, anch’essa a sua scelta; se vuole pu\u00f2 anche prenderseli tutti. Vince chi raccatta l’ultimo oggetto oppure, nella versione mis\u00e8re<\/i>, chi \u00e8 costretto a prenderlo perde. Per la cronaca, in questo tipo di giochi la strategia nella versione mis\u00e9re \u00e8 generalmente pi\u00f9 complicata di quella del gioco standard.<\/p>\n

Per trovare la strategia vincente, il passaggio \u00e8 semplice, ma richiede di conoscere la numerazione binaria, quella cio\u00e8 dei computer che usa solo le cifre 0 e 1. Bisogna convertire in formato binario il numero di oggetti nelle varie pile e poi sommare (in base 10, stavolta) i numeri ricavati. Se con la vostra mossa riuscite a fare in modo che le cifre di questa somma siano tutte pari, allora siete in una botte di ferro, e vincerete. L’unica differenza nella versione mis\u00e9re \u00e8 che se rimangono solo pile con un elemento allora ce ne devono essere un numero dispari; diciamo per\u00f2 che ci si pu\u00f2 ricordare di questa eccezione. Esempio pratico: partendo da tre pile di 7, 11 e 13 oggetti, i numeri corrispondenti in base 2 sono rispettivamente 111, 1011 e 1101 la cui somma \u00e8 2223. Per arrivare a un numero pari baster\u00e0 togliere un singolo oggetto da una pila qualunque, visto che in tutti e tre i casi i numeri binari finiscono per 1 e quindi non c’\u00e8 nessun riporto da fare.<\/p>\n

\"Tabellina<\/a>
Tabellina per la somma Nim<\/figcaption><\/figure>Il bello del Nim – beh, almeno dal punto di vista di un matematico – \u00e8 l’essere il mattone fondamentale nella teoria delle partite a due persone; seondo il teorema di Sprague\u2013Grundy<\/a> ogni gioco a due persone in formato standard (cio\u00e8 dove chi non pu\u00f2 muovere ha perso) pu\u00f2 essere visto come la somma di varie partite a Nim, giocate su tavoli diversi. Detto in altro modo, ogni giocatore al suo turno sceglie su quale tavolo giocare e fa la sua mossa, e vince chi raccoglie l’ultimo oggetto nell’ultimo tavolo. (Tra l’altro noi in italiano siamo fregati con il nome; gli americany parlano di “play”, solo che nel nostro caso dire “gioco” ci fa cascare nella teoria dei giochi che si studia in economia, e che \u00e8 tutta un’altra cosa). Si parla addirittura di addizione Nim; indicata dal simbolo ⊕, \u00e8 associativa e commutativa proprio come quella usuale, ma ha in pi\u00f9 la caratteristica che a<\/i> ⊕ a<\/i> \u00e8 sempre uguale a zero. Come ricordate, nella strategia i numeri pari contano zero, e per definizione sommare (in base dieci) un numero (scritto in base due) a s\u00e9 stesso d\u00e0 tutte cifre pari a zero o due. Qui a fianco c’\u00e8 una tabellina di addizione Nim; un po’ strana, ma perlomeno coerente. Gli anglofoni chiamano nimbers<\/a><\/i> i numeri Nim; a quanto pare nessun italiano ha parlato di “nimeri”, il che \u00e8 triste perch\u00e9 dimostra che non ci sono abbastanza persone seriamente giocose… a parte naturalmente i Rudi Mat(h)ematici<\/a>.<\/p>\n

\"\"<\/a>
Posizioni vincenti nel gioco di Wythoff<\/figcaption><\/figure>Il gioco di Wythoff<\/strong>, dal nome di un matematico olandese<\/a> assolutamente ignoto a chi non fa matematica ricreativa e il cui cognome sbaglio sempre a scrivere, \u00e8 simile ma non uguale al Nim. Le pile sono infatti solo due; in compenso per\u00f2 le mosse a disposizione sono di tre tipi fondamentalmente diversi. Si pu\u00f2 prendere quanti oggetti si vuole dalla prima pila, oppure se ne possono prendere quanti se ne vuole dalla seconda, o ancora si possono prendere oggetti da entrambe le pile, ma in questo caso occorre prenderne in numero uguale. Un modo alternativo per giocare \u00e8 immaginare di avere una scacchiera (m<\/i>+1)·(n<\/i>+1) dove si mette nell’angolo in alto a destra una pedina; le mosse sono quelle della regina, ma ci si pu\u00f2 muovere solo a sinistra o verso il basso.<\/p>\n

La strategia vincente non \u00e8 cos\u00ec semplice come nel Nim. Il modo pi\u00f9 semplice per definirla \u00e8 quello di indicare le posizioni che garantiscono la vittoria al giocatore che riesce a raggiungerle; le prime sono (0, 0), (1, 2), (3, 5), (4, 7), e (6, 10), oltre naturalmente alle simmetriche come (2, 1), (5, 3) e cos\u00ec via. Nella figura qui a fianco si vede come si possono trovare graficamente e ricorsivamente le posizioni vincenti; scelte le due posizioni pi\u00f9 a sinistra e pi\u00f9 in basso rimaste ancora libere, si disegnano tre semirette che partono da quelle posizioni e si cancellano tutte le caselle toccate, continuando a piacere con un minimo di pazienza. In realt\u00e0 esiste una formulazione diversa per calcolare le posizioni vincenti; ma per spiegarla devo prima raccontarvi varie altre cose. Prima o poi ce la faremo, fidatevi.<\/p>\n","protected":false},"excerpt":{"rendered":"

Due giochi della serie “prendi i gettoni” dalle caratteristiche a prima vista simili; ma mentre per il Nim \u00e8 facile trovare una strategia vincente il gioco di Whytoff \u00e8 un po’ pi\u00f9 ostico.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2342","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-BM","jetpack-related-posts":[{"id":2464,"url":"https:\/\/xmau.com\/ilpost\/2011\/12\/09\/morra\/","url_meta":{"origin":2342,"position":0},"title":"Morra","author":".mau.","date":"09\/12\/2011","format":false,"excerpt":"Il gioco della morra, compresa la sua variante \"morra cinese\" che a dire il vero c'entra ben poco con l'originale, nasconde alcune interessanti considerazioni matematiche.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"regole della morra, con lucertola e Spock","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2011\/12\/morra.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":184,"url":"https:\/\/xmau.com\/ilpost\/2010\/11\/13\/il-paradosso-di-penney\/","url_meta":{"origin":2342,"position":1},"title":"Il paradosso di Penney","author":".mau.","date":"13\/11\/2010","format":false,"excerpt":"In generale nei giochi a due persone \u00e8 chi fa la prima mossa a essere avvantaggiato; ma ci sono alcuni casi in cui \u00e8 meglio giocare per secondo, soprattutto se puoi conoscere in anticipo la prima mossa dell'avversario. E questo vale anche se si lancia una moneta!","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"[con che probabilit\u00e0 vince il secondo giocatore?]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2010\/11\/penney-prob.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":190,"url":"https:\/\/xmau.com\/ilpost\/2010\/07\/16\/il-paradosso-di-san-pietroburgo\/","url_meta":{"origin":2342,"position":2},"title":"Il paradosso di san Pietroburgo","author":".mau.","date":"16\/07\/2010","format":false,"excerpt":"Da un banale gioco a testa o croce non solo si pu\u00f2 arrivare a una vincita potenzialmente infinita, ma addirittura la vincita media \u00e8 infinita!","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2458,"url":"https:\/\/xmau.com\/ilpost\/2011\/11\/16\/non-mi-piace-la-fisica\/","url_meta":{"origin":2342,"position":3},"title":"Non mi piace la fisica","author":".mau.","date":"16\/11\/2011","format":false,"excerpt":"Matematici e fisici sono come cani e gatti (di Schr\u00f6dinger?). Ecco il mio punto di vista.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1441,"url":"https:\/\/xmau.com\/ilpost\/2019\/03\/07\/la-dimostrazione-matematica-piu-lunga\/","url_meta":{"origin":2342,"position":4},"title":"La dimostrazione matematica pi\u00f9 lunga","author":".mau.","date":"07\/03\/2019","format":false,"excerpt":"\u00c8 impossibile che qualche essere umano la possa leggere.","rel":"","context":"In \"combinatoria\"","block_context":{"text":"combinatoria","link":"https:\/\/xmau.com\/ilpost\/tag\/combinatoria\/"},"img":{"alt_text":"un esagono colorato di rosso e blu","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/03\/esagono-300x248.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2275,"url":"https:\/\/xmau.com\/ilpost\/2010\/06\/10\/ci-sono-infiniti-piu-infiniti\/","url_meta":{"origin":2342,"position":5},"title":"Ci sono infiniti “pi\u00f9 infiniti”!","author":".mau.","date":"10\/06\/2010","format":false,"excerpt":"Il metodo diagonale di Cantor mostra che ci sono diversi tipi di infiniti, e ne costruisce esplicitamente uno, se si ha una pazienza infinita. Ma non tutti sono d'accordo che la cosa sia lecita!","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"il metodo diagonale di Cantor","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2010\/06\/cantor-diagonale.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2342","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2342"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2342\/revisions"}],"predecessor-version":[{"id":2343,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2342\/revisions\/2343"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2342"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}