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, Lindsay Erickson 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.


Pažanga sprendžiant 40 m. senumo dėlionę

John Conway sukurta „Topswops“ dėlionė yra tokia: imame atsitiktinai nuo 1 iki n sunumeruotą kortų kaladę. Nuimkite juo jos kortų kiekį, kurį nurodo viršutinė korta, ir tas kortas perkelkite į apačią. Tada vėl ir vėl kartokite tą patį – tol, kol viršuje atsiras korta su numeriu 1. Reikia surasti minimalų ir maksimalų žingsnių skaičių priklausomai nuo pasirinkto n.

Kadaise D. Knutas eksponentinę viršutinę ribą ir teigė, kad tai gali būti įrodyta apatinei ribai. Tačiau dabar Dr. Hal Sudborough ir Dr. Linda Morales įrodė, kad apatinė riba yra gerokai geresnė, nei spėjo D. Knutas, kuris jų įrodymą pavadino „elegantišku“ ir „žaviu“.

Halas pacitavo ilgametį „Scientific American“ skyrelio vedėją Martin Gardner‘į: „Nelaikykime Conway kortų žaidimų trivialiais. Jie priklauso perstatų aibių teorijai ir ne tik verčia įrodyti giliaprasmes teoremas, bet atsiliepia ir praktiniams uždaviniams, kylančiais, kaip atrodytų, nesusijusiose srityse“.

Įrodymas pateikiamas ”Theoretical Computer Science“ 2010 m. spalio mėn. numerio straipsnyje “A Quadratic Lower Bound for Topswops”.

Martin Gardner knygoje „Time travel and other mathematical bewikderments“ aprašo eilė kortų dėlionių, priskiriamų J.H. Conway.

Amir D. Aczel

Išėjimai

2015 m. lapkričio 26 d. Nimo mieste*) (Prancūzijoje) mirė 65 m. amžiaus Amir D. Aczel’is (1950-2015), skaitytojus įvesdinęs į Ferma didžiosios teoremos sprendimo istoriją (1996), o taip pat parašęs dar tuziną populiarių knygų apie mokslą.

Jis gimė Izraelyje, jūrininko šeimoje, tad vaikystę praleido plaukiodamas laivais. Jam įspūdį padarė Monte Karlo kazino su magiškais, ornamentuotas skaičiais ant ruletės stalo – ir tai, galbūt, nulėmė jo, kaip matematiko ir statistiko karjerą.

Kai dėstė Aliaskos universitete, jis pasiskundė keliaujančiam vadovėlių pardavėjui, kad nėra kas parašo gerą statistikos vadovėlį – į ką pardavėjas atsakė: „Parašyk“. Ir taip pasirodė „Išsami verslo statistika“ (1989), kuri buvo gana gerai perkama. Tai davė naują impulsą ir pasirodė knygos apie tikimybių teoriją, švytuoklę bei ... Dievo egzistavimą.

Naujausia jo knyga buvo „Nulio paieškos: matematinė odisėja skaičių kilties paieškai“ (2015 m. sausis). Jos rašymas nuvedė į Kambodžą, ieškant 7 a. akmens plokštės, ant kurios buvo skaičius 605, nurodantis metų skaičių, praėjusį nuo Čaka eros pradžios (78 m.). Tai pirmas žinomas nulio panaudojimas, sustiprinantis argumentus, kad nulio koncepcija kilo Azijoje ir į Artimuosius rytus buvo atnešta arabų pirklių. A. Aczel‘is atsekė plokštės vietą esant netoli Angkor Wat.


*) Nimas - miestas pietų Prancūzijoje, dar vadinamas „Antrąja Roma“ dėl jame esančio amfiteatro ir kitų panašių dalykų kaip Romoje. Yra į šiaurės vakarus nuo Marselio.

Mirė Herbert Hauptman

2011 m. spalio 23 d., sekmadienį, mirė Nobelio premijos laureatas, 94 m. amžiaus Herbert Hauptman‘as (1917-2011). Amerikos žydiškos kilmės matematikas ir kristalografas, Nobelio premiją gavo 1985 m. chemijos srityje už matematinių metodų sukūrimą cheminių jumginių molekulinės struktūros nustatymui.

Gimė Niujorke, 1937 m. baigė Niujorko Miesto koledžą, o 1939 m. gavo matematikos magistro laipsnį Kolumbijos un-te. 1940 m., po audringo romano, vedė Edith Citrynell. Karo metu buvo pasiųstas tarnauti į Ramiojo vandenyno pietus. Tarnybos įspūdžiai taip paveikė jį, kad visą likusį gyvenimą aktyviai protestavo prieš visus JAV karinius veiksmus.

1970 m. ėmė dirbti Buffalo medicinos fonde ir vėliau tapo jo prezidentu.

Fiksuoto taško pažymėjimas

Jau 50 m. matematikai grumiasi su vadinamąja „fiksuoto taško“ teorema. 2008 m. buvo paskelbtas beveik 30 psl. Apimantis ir labai techninis straipsnis, nepaprastai priartėjęs prie jos įrodymo.

Padėkime akmenuką Katedros aikštėje Vilniuje, savo kieme ar ant palangės – ir visada žemėlapyje galėsite nurodyti tikslią vietą, kuriame jis turėtų būti. Akivaizdu, ar ne? Tačiau ne matematikams. Jie nuo 1963 m. negali susitvarkyti su vadinamąja (nors kiek ir sudėtingesne) „fiksuoto taško teorema“, kurią suformulavo Barry Edward Johnson (beje, ją bandęs įrodyti iki pat savo mirties 2002 m.). Tačiau EPFL (Ecole Polytechnique Federale de Lausanne), Lozanoje (Šveicarija) matematikų grupė rado elegantišką, viename puslapyje išdėstomą, sprendimą, atveriantį naujas perspektyvas fizikoje ir ekonomikoje. Jie tai pasiekė, kitaip ėmėsi spręsti uždavinį.

Įdomu, kad teorema pritaikoma įvairiausiems žemėlapiams, nuo planų iki metro schemų bei erdvių pavaizdavimo kvantinėje mechanikoje. Tačiau jos įrodymui yra būtina rasti fiksuotą tašką kiekvienu konkrečiu atveju. Kadangi galimų žemėlapių aibė yra begalinė, matematikai ieškojo universalaus metodo. Tai buvo panašu į svorio centro bet kokiame kūne paieškas. Ir tas taškas buvo surandamas, tačiau ... kitoje erdvėje, nei pradinė. Ir tai leido įrodyti teoremą
(žr. originalų straipsnį >>>>).

Gyvenimo gėlelė
Santykis ir proporcija
Monte-Karlo metodas
Sutramdytas lagaminas
Žmonės prieš kompiuterius
Scenoje - paprastos grupės
Atsidaro matematikos muziejus
Pi keliai ir klystkeliai
Linksmi nutikimai mokslininkams
J. Tate: Abelio premijos laureatas
Ar nepabandysite išpręsti uždavinį?
Algoritmų pirmeivis laimėjo Kyoto premiją
Laimėti pralaimint: „dviejų vokų“ paradoksas
Džordžas Birkhofas - matematikas ir meno matuotojas
Moksleivis „perkando“ I. Niutono uždavinį
Ar jau rūksta dūmai? Navier Stokes lygtys
Nėra paprastos visuotinės teorijos!
Simpsonų trauka ir žaidimas skaičiais
Omaras Chajamas: ne vien Rubijatai
Skaičiai B ir jų kvantinės sistemos
Nulaužtas 200 m. senumo šifras
P-NP: Ant sveiko proto svarstyklių
Kada statistika gali meluoti?
Da Vinči matematinė klaidelė
Revoliucija mazgų teorijoje
Matematikos pradžia Lietuvoje
Matematikai: Pjeras Ferma
Ar viskas čia taip?
Išmatavimų triauškintojas
Vunderkindo iššūkiai
Matematiniai anekdotai
Meilės sinusoidė
Ferma taškas
Vartiklis