Nim (igra)
Nim je matematička strateška igra koja se igra između dva igrača koji naizmenično povlače poteze. Na početku igre su žetoni (šibice, novčići i sl.) raspoređeni po stubovima (kolonama). Pri svakom potezu, igrač koji povlači potez uzima žetone (bar jedan), samo sa jednog stuba. Postoji više varijanti ove igre poput normalnog nima (pobednik je onaj igrač koji uzme poslednji žeton), mizernog nima (gubitnik je onaj igrač koji uzme poslednji žeton), Fibonačijevog nima...
Varijante Nima su se igrale od davnina. Nim kakav danas poznajemo kao i njegovo ime skovao je Čarls Leonard Bouton sa Univerziteta Harvard, koji je takođe razvio kompletnu teoriju igre 1901. godine.[1]
Na Svetskoj izložbi 1940. godine u Njujorku prikazana je mašina Nimatron koja je igrala nim.[2][3] Od 11. maja do 27. oktobra 1940. godine samo je nekolicina ljudi uspela da pobedi mašinu u tom periodu od šest nedelja. Oni koji su to uspeli, kao nagradu su dobili novčić na kojem je pisalo Nim Šampion. To je ujedno i jedna od prvih ikad elektronskih kompjuterizovanih igara.
Prema teoriji igara nim spada među matematički rešene igre, za bilo koji počenti broj kolona i žetona u kolonama, zato što se može izračunati koji igrač će pobediti i koji su pobednički potezi koje on treba da povuče.
Primer igre uredi
Ovo je prikaz partije normalnog nima u kojoj je cilj igrača da uzmu poslednji predmet kako bi pobedili. Partija se odvija između zamišljenih igrača Alekse i Baneta koji igru počinju sa tri kolone (A, B i V) sa po tri, četiri i pet žetona u kolonama redom.
А Б В Потези 3 4 5 Бане узме 2 жетона из А 1 4 5 Алекса узме 3 жетона из В 1 4 2 Бане узме 1 жетон из Б 1 3 2 Алекса узме 1 из Б 1 2 2 Бане узме преостали жетон из А, уклањајући на тај начин колону А 0 2 2 Алекса узме 1 из Б 0 1 2 Бане узме 1 из В, остају две колоне са једним жетоном (У мизерном ниму би узео 2 из В и победио) 0 1 1 Алекса узме 1 из Б 0 0 1 Бане узме једини преостали жетон из В и на тај начин побеђује
Različite vrste nima uredi
Fibonačijev nim uredi
U Fibonačijevom nimu igrači uzimaju objekte iz kolona na isti način kao u nimu samo što igrač koji prvi igra ne može uzeti sve objekte iz kolone u prvom potezu. Još jedan uslov je da u svakom narednom potezu broj uzetih objekata može biti bilo koji broj, ali manji od dvostruke vrednosti uzimanja iz prethodnog poteza.[4] I ova vrsta nima se takođe može igrati na mizeran i normalan način.
Druga varijacija Fibonačijevog nima je ona u kojoj igrači mogu ukloniti bilo koji Fibonačijev broj objekata iz kolone pri svakom potezu.[5][6]
Grundijeva igra uredi
U Grundijevoj igri, još jednoj varijaciji nima, svi objetki se nalaze u jednom stubu. Igrači naizmenično dele gomilu na dve neprazne gomile različitih veličina. Na primer gomila od 6 objekata se može podeliti na gomile od 5+1 ili 4+2, ali ne i 3+3. Grundijeva igra se takođe može igrati na mizeran i normalan način.
„21” uredi
„21“ se igra kao mizerna igra sa bilo kojim brojem igrača koji redom izgovaraju broj. Prvi igrač kaže „1“, a svaki igrač zauzvrat povećava broj za 1, 2 ili 3, ali ne može biti veći od 21; igrač primoran da kaže „21“ gubi. Ovo se može modelirati kao igra oduzimanja sa gomilom 21– n objekata. Pobednička strategija za verziju ove igre sa dva igrača je da uvek kažete broj koji je deljiv četvorkom. Tada je zagarantovano da će drugi igrač na kraju morati da kaže 21 - tako da u standardnoj verziji gde se prvi igrač otvara sa „1“, počinje gubitničkim potezom.
Igra „21“ se takođe može igrati sa različitim brojevima, poput „Dodajte najviše 5; izgubite na 34“.
Primer igre u kojoj drugi igrač sledi pobedničku strategiju:
Играч Број 1 1 2 4 1 5, 6 or 7 2 8 1 9, 10 or 11 2 12 1 13, 14 or 15 2 16 1 17, 18 or 19 2 20 1 21
Reference uredi
- ^ Bouton, Charles L. (1901). „Nim, A Game with a Complete Mathematical Theory”. Annals of Mathematics. 3 (1/4): 35—39. ISSN 0003-486X. doi:10.2307/1967631.
- ^ „1940: Nimatron” (na jeziku: engleski). Pristupljeno 2020-03-07.
- ^ Flesch, Rudolf (1951). The Art of Clear Thinking. New York: Harper and Brothers Publishers. str. 3.
- ^ Vajda, Steven (2008-01-01). Mathematical Games and How to Play Them (na jeziku: engleski). Courier Corporation. ISBN 978-0-486-46277-6.
- ^ Alfred, Brother U. (1963), „Exploring Fibonacci numbers” (PDF), Fibonacci Quarterly, 1 (1): 57—63. See "Research project: Fibonacci nim", p. 63.
- ^ Pond, Jeremy C.; Howells, Donald F. (1963), „More on Fibonacci nim” (PDF), Fibonacci Quarterly, 1 (3): 61—62.
Spoljašnje veze uredi
- Nim and 2-dimensional SuperNim at cut-the-knot
- Classic Nim - Implementation of Nim for iOS.
- Matchstick Nim - Implementation of Nim for Android devices.