Nim

Fra Wikipedia, den frie encyklopedi

Nim er et spill for to personer. Det er ikke spesielt interessant å spille det, siden det fra enhver posisjon er enkelt å finne et vinnende trekk, hvis et slikt eksisterer, men teorien om nim er svært viktig i kombinatorisk spillteori, som er en gren av matematikk.

En posisjon i nim består av noen hauger med objekter (for eksempel fyrstikker). Et trekk består av å fjerne en eller flere fyrstikker fra én haug. Man kan gjerne fjerne hele haugen. Den som tar den siste fyrstikken vinner.

En optimal strategi for dette spillet ble funnet av C. L. Bouton ved Harvard University i USA i 1902. Gitt en posisjon, skriver man antall fyrstikker i hver haug i det binære tallsystemet, og legger sammen alle tallene, uten å ta med tall i mente. Hvis resultatet blir null, kan man ikke vinne. Hvis resultatet er forskjellig fra null, kan man vinne ved å flytte til en posisjon med verdi null.

Har man for eksempel tre hauger med henholdsvis tre, fire og fem fyrstikker, blir resultatet slik:

3 011
4 100
5 101
_____
  010

Resultatet blir 010, som er lik 2 i titallssystemet. Det finnes derfor et vinnende trekk, som vil være å redusere haugen med tre fyrstikker til én.