Nim (peli)

Nim on peli, jossa kaksi pelaajaa poimii vuorotellen tavaroita, jotka on jaettu useisiin pinoihin. Yhdellä siirrolla yhdestä pinosta voidaan ottaa mikä tahansa määrä esineitä (suurempi kuin nolla). Pelaaja, joka ottaa viimeisen esineen, voittaa. Pelin klassisessa versiossa pinojen lukumäärä on kolme.

Erikoistapaus, jossa on vain yksi pino, mutta vuoroa kohden otettavien esineiden enimmäismäärä on rajoitettu, tunnetaan Bachen pelinä . Nim on täydellinen tiedon rajallinen peli . Klassinen Nîmes-peli on Sprague-Grundy-lauseen perusta . Tämä lause sanoo, että tavallinen puolueettomien pelien summan peli vastaa tavallista Nim-peliä. Samanaikaisesti jokainen puolueeton pelitermi vastaa Nim-pinoa, jossa olevien esineiden määrä on yhtä suuri kuin Sprague-Grundy-funktion arvo tämän pelin peliasemalle.

Pelihistoria

Eurooppalaiset mainitsivat kiinalaisen pelin jo 1500-luvulla. Nimen "nim" antoi pelille amerikkalainen matemaatikko Charles Bouton , joka kuvaili vuonna 1901 pelin voittostrategiaa . Pelin nimen alkuperälle on useita vaihtoehtoja:

saksan verbistä nehmen tai vanhan englannin verbistä Nim , joka tarkoittaa "ottaa";
Anonyymi englannin verbistä Win ("voittaa").

"Dr. Nim" -lelu, pieni pallotietokone, joka keksittiin 1960-luvulla, ei pelannut siinä, vaan Basche-pelissä .

Pelistrategia

Yleisessä tapauksessa otetaan huomioon joukko esineitä, joissa on esineitä. Pelaajat vuorottelevat. Siirto on, että pelaaja ottaa kasasta esineitä. Jokaiselle pelin paikalle on määritetty tämän paikan nim-summa - tulos, kun lisätään binäärilukujärjestelmän kaikkien kasojen koot ottamatta huomioon bittien siirtoa, eli numeroiden binäärinumeroiden lisääminen kenttään jäännöksistä modulo 2 : $s$ ${\displaystyle N_{1},N_{2},\cdots N_{p))$ $i\in [1,p]$ $n\in [1,N_{i}]$ ${\displaystyle S=N_{1}\oplus N_{2}\oplus \cdots \oplus N_{p))$

Voittava strategia on jättää asema hänen kanssaan - summa on yhtä suuri kuin nolla siirtosi jälkeen. Se perustuu siihen tosiasiaan, että mistä tahansa asennosta, jonka nim-summa ei ole yhtä suuri kuin nolla, voidaan yhdellä liikkeellä saada asema, jonka nim-summa on nolla, ja paikasta, jonka nim-summa on nolla, mikä tahansa liike johtaa asemaan, jonka nim-summa on nollasta poikkeava .

Esimerkki : oletetaan, että pelissä on kolme pinoa, jotka sisältävät 2 (0010 binäärimuodossa), 8 (1000) ja 13 (1101) kohdetta. Tämän paikan nim-summa on 7 (0111). Siksi voittostrategia on ottaa kolme kohdetta kolmannesta pinosta - jäljelle jää 10 (1010) kohdetta ja paikan nim-summaksi tulee 0 (0000). Oletetaan, että vuorosi jälkeen vastustaja ottaa kaikki esineet ensimmäisestä kasasta - voittostrategia olisi ottaa kaksi esinettä kolmannesta kasasta. Tässä tapauksessa paalut sisältävät muuton jälkeen 0 (0000), 8 (1000) ja 8 (1000) kohdetta, nim-summa on edelleen 0.

Vaihtoehdot

Käännä se toisinpäin

Pelaajat täydentävät kasoja tiettyyn määrään asti . Saatavilla tehtävänä tietokonepelissä " Space Rangers ". Peli vastaa tavallista tilallista nimiä . $N$ ${\displaystyle \{N-N_{i}\}_{i=1}^{p))$

Nim-Bashe

Et voi ottaa enempää tavaroita. Peli vastaa tavallista tilallista nimiä $k$ ${\displaystyle \{N_{i}\operaattorin nimi {mod} (k+1)\}_{i=1}^{p))$

Suklaa

Siellä on suklaapatukka , yksi siivu "myrkyttynyt". Pelaaja itse rikkoo suklaan linjaa pitkin ja syö myrkyttömän osan. Se, jolle jää myrkytetty viipale, häviää. Peli vastaa nimiä neljällä paalulla. $m\ kertaa n$

Miser

Tässä versiossa viimeisen esineen ottanut pelaaja häviää. Voittostrategia on sama kuin tavallisen pelin voittostrategia siihen hetkeen asti, jolloin pelaajan liikkeen seurauksena pöydälle jää tietty määrä pinoja, joista jokaisessa on yksi esine. Miserin tapauksessa pelaajan on jätettävä pariton määrä paaluja, kun taas tavallisen pelin voittostrategia edellyttää parillisen määrän paalujen jättämistä siten, että neem-summa on nolla. Tämä voidaan muotoilla seuraavasti: jos on täsmälleen yksi pino, joka sisältää useamman kuin yhden esineen, ota siitä kaikki tavarat tai kaikki yhtä lukuun ottamatta, jotta jäljelle jää pariton määrä yksittäisiä pinoja; muuten pysy normaalin pelin voittostrategiassa.

Multinym

Eliakim Moore ehdotti yleisempää Nîmes-pelin tapausta . Pelissä pelaajat saavat ottaa tavaroita enintään pinoista. On helppo nähdä, että tavallinen peli on hän . Sen ratkaisemiseksi on tarpeen kirjoittaa jokaisen kasan koot binäärilukujärjestelmään ja summata nämä luvut -ary-lukujärjestelmässä ilman tavutusta. Jos luku on 0, nykyinen sijoitus on häviämässä, muuten se on voittava ja siitä siirrytään nolla-arvoon. $Nim_{i}$ $i$ $Nim_{1}$ $(i+1)$

Forked-nim

Toista versiota pelistä ehdotti Matvey Bernstein. Siinä voit mielivaltaisesti jakaa minkä tahansa kasan kahdeksi mielivaltaiseksi kasoksi siirron sijaan. Muilta osin peliä pelataan tavanomaisten sääntöjen mukaan.

Elokuvassa ja televisiossa

Tämä peli toimii vertauskuvana elokuvassa " Viimeinen vuosi Marienbadissa " [1] .

Katso myös

Muistiinpanot

↑ Oliver Knill. Math in Movies : Viime vuonna Marienbadissa . Matematiikka elokuvissa . Matematiikan laitos Harvardin yliopistossa. Käyttöpäivä: 22. kesäkuuta 2009. Arkistoitu alkuperäisestä 21. helmikuuta 2012.

Kirjallisuus

Ball W., Coxeter G. Mathematical Recreations and Essays. - M .: Mir, 1986. - S. 47-51.
Fomin SV Numerojärjestelmät . - 5. painos - M .: Nauka, 1987. - S. 48.
Gardner M. Tic-tac-toe. —M.: Mir, 1988. ISBN 5-03-001234-6 .
Jean-Paul Delahaye . Stratégies magiques au pays de Nim // Pour la science: Journal. - Paris: Belin, 2009. - T. 377 , nro 3 . - S. 88-93 . Arkistoitu alkuperäisestä 10. kesäkuuta 2013.