Paviliota senovinio žaidimo
Šiaurės Dakotos valstijos un-to matematikos doktorantę Lindsay Erickson sužavėjo senovinis nimo žaidimo. Jis yra pilnos informacijos žaidimas, nes abu žaidėjai žino,
ką daro jo oponentas kiekvieno žingsnio metu ir jame nėra atsitiktinumo elementų.
Šiame universitete Lindsay gavo matematikos bakalauro laipsnį 2006 m. Kaip iškili studentė, gavo NSF paramą, o taip pat kelias stipendijas daktarinei. Vieną vasarą matematiką studijavo Vengrijoje.
Lindsay yra nebloga nimo žaidėja, o savo darbe panaudojo grafų teoriją. Jos 60 psl. daktarinė disertacija parodo, kad įvairūs sprendimai priklauso nuo grafų struktūros. Ji panaudojo pilnuosius, dvidalius Petersono grafus, hipekubus. Ji kiekvienai briaunai, išeinančiai iš pasirinktos viršūnės, priskyrė sveikas reikšmes, atitinkančias šūsnį akmenukų, naudojamą nimo žaidime.
Nimas - žaidimas
Nimas yra matematinis strateginis žaidimas, kuriame žaidėjai paeiliui šalina objektus iš skirtingų krūvų. Žaidėjas privalo pašalinti bent vieną objektą ir gali pašalinti bet kokį objektų kiekį iš tos pačios krūvos.
Nuo senų laikų žaidžiami keli nimo variantai. Laikoma, kad jis atsirado Kinijoje (ir primena kinų džianšizi, akmenų nuėmimo žaidimą), tačiau tiksli jo kilmė nėra nustatyta. Europoje ankstyviausi žaidimo paminėjimai yra iš 16 a. Dabartinį jo pavadinimą davė Charles L. Bouton iš Harvardo, 1901 m. sukūręs pilną jo teoriją, tačiau pavadinimo nepaaiškino. Galbūt, jis yra iš vokiečių nimm, paimti ar pasenusio anglų žodžio nim, reiškiančio tą patį. Verta atkreipti dėmesį, kad pasukus žodį NIM 180o kampu gausime WIN (laimėti).
Nimas dažniausiai žaidžiamas kaip misere, t.y., pralaimi paėmęs paskutinį objektą. Bet kartais žaidžiamas taip, kad laimi tas, kuris paima paskutinį objektą (vadinamasis normalus žaidimas). Normalusis nimo žaidimas yra principinis Sprague-Grundy teoremai, teigiančiai, kad normaliame žaidimas kiekvienas objektyvus žaidimas yra ekvivalentiškas nimo krūvai, kuri garantuoja vienodą baigtį, kai žaidžiama lygiagrečiai su kitais objektyviais žaidimais.
Paprastai žaidžia du žaidėjai su trimis akmenukų krūvomis. Žaidimas matematiškai išspręstas bet kokiam pradiniam krūvų ir objektų kiekiui. Pvz., turint tris pradines krūvas su 3, 4 ir 5 objektais, pirmasis žaidėjas, žaisdamas optimaliai, laimi tiek normalųjį, tiek misere variantą. Žaidimo teorijos pagrindas yra dvejetainė krūvų objektų suma moduliu du (xor). Kombinatorinių žaidimų teorijoje ji dažnai vadinama nim- suma. Pvz., minėtu atveju 3+4+5=011 + 100 + 101 = 010
Normalaus žaidimo atveju laiminti strategija yra siekti, kad nim-suma kiekviename žingsnyje būtų 0. Tai visada įmanoma, jei suma prieš tai nebuvo lygi 0.
Misere žaidimo atveju reikia siekti, kad būtų paliekamas tik nelyginis skaičius krūvų, kuriose yra po 1 objektą.
Pastaba: Nimo žaidimas žaistas prancūzų naujosios bangos filme Praeiti metai Marienbade (1961).
Variantai
1. Vietoje bet kokio objektų pašalinimo, leidžiama pašalinti tik tam tikrą kiekį (1, 2, k). Dažniausiai šis variantas žaidžiamas tik su viena krūva.
2. 21 yra misere žaidimas su bet kokiu žaidėjų kiekiu, kurių kiekvienas sulig kiekvienu žingsnius pasako skaičių. Kitas žaidėjas turi padidinti skaičių 1, 2 arba 3-imis, tačiau negalima viršyti 21; pralošia tas, kuris priverstas pasakyti 21.
3. Viename variante leidžiama vienodą objektų kiekį išimti iš kiekvienos krūvos.
4. Apvalusis nimas. Krūvos sudėliojamos ratu ir du žaidėjai paeiliui pašalina 1, 2 arba 3 gretimus objektus
5. Grundy variante du žaidėjai pradinę krūvą paeiliui dalija į dvi netuščias skirtingų dydžių krūvas.
Pitagoro teorema
Matematika ir muzika
Scenoje - paprastos grupės
G. Perelmanas: neįmanoma suprasti keistuolį?
J. Tate: Abelio premijos laureatas
Algoritmų pirmeivis laimėjo Kyoto premiją
Laimėti pralaimint: dviejų vokų paradoksas
Džordžas Birkhofas - matematikas ir meno matuotojas
Nėra paprastos visuotinės teorijos!
Omaras Chajamas: ne vien Rubijatai
Nulaužtas 200 m. senumo šifras (nauja)
P-NP: Ant sveiko proto svarstyklių
Da Vinči matematinė klaidelė
Revoliucija mazgų teorijoje
Matematikos pradžia Lietuvoje
Premija už duomenų minkymą
Matematikai: Pjeras Ferma
Skaičiuojantys gyvūnai ir kt.
Ar viskas čia taip?
Išmatavimų triauškintojas
Vunderkindo iššūkiai
Matematiniai anekdotai
Vartiklio naujienos