Nim-spel

Dit forum is voor het voortgezetonderwijs (of 2de/3de graad ASO), als je in de bovenbouw zit. We gaan er vanuit dat je een Grafische Rekenmachine hebt.
Plaats reactie
xxxmoi
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 26 jan 2006, 19:28

Nim-spel

Bericht door xxxmoi » 29 jan 2006, 11:17

Hier ben ik dan weer, we moeten namelijk voor een werkstuk over speltheorieën ook nog een onderdeel maken over een nim-spel. Het gaat hierbij om een variant met de beginstand van 1-3-5-7. Degene die de laatste lucifer pakt wint. Er zijn hierbij drie stellingen, die we moeten uitleggen/bewijzen, maar eigenlijk snappen we er geen snars van. De stellingen zijn:

Stelling 1. De verliezer van het spel eindigt met een even positie (0-0-0-0).

Stelling 2. Een even positie wordt altijd veranderd in een oneven positie (en nooit in een even positie)

Stelling 3. Elke oneven positie kan altijd met een geldige zet in een even positie veranderd worden.

Weet iemand misschien hoe deze stellingen te bewijzen zijn?
Het zou ons echt heel erg helpen!!!

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Bericht door Sjoerd Job » 29 jan 2006, 15:24

Ik merk dat je veel vragen stelt over spellen, in verband met je werkstuk. Niet alle leden van dit forum zijn bekend met de spellen, en dus zou het een goed idee zijn om even wat te vertellen over het spel.

Het Nim-Spel wordt gespeeld met twee spelers. Benodigdheden zijn: Een aantal stapeltjes met lucifers, of een ander soort fiches. De spelers pakken om de beurt een aantal fiches van één stapel, niet meer dan dat er zijn, natuurlijk.

Bijvoorbeeld, bij het 1-3-5-7, kan ik 3 van de 4e stapel halen, en dan hebben we 1-3-5-4...

Verder snap ik ook weinig van dit spel, ik heb zojuist wat op internet gezocht.
Het bewijzen laat ik wel aan iemand anders over ;)
``Life is complex. It has real and imaginary parts.''

xxxmoi
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 26 jan 2006, 19:28

Bericht door xxxmoi » 29 jan 2006, 15:31

Sjoerd Job schreef:Ik merk dat je veel vragen stelt over spellen, in verband met je werkstuk. Niet alle leden van dit forum zijn bekend met de spellen, en dus zou het een goed idee zijn om even wat te vertellen over het spel.

Het Nim-Spel wordt gespeeld met twee spelers. Benodigdheden zijn: Een aantal stapeltjes met lucifers, of een ander soort fiches. De spelers pakken om de beurt een aantal fiches van één stapel, niet meer dan dat er zijn, natuurlijk.

Bijvoorbeeld, bij het 1-3-5-7, kan ik 3 van de 4e stapel halen, en dan hebben we 1-3-5-4...

Verder snap ik ook weinig van dit spel, ik heb zojuist wat op internet gezocht.
Het bewijzen laat ik wel aan iemand anders over ;)
Dat is waar inderdaad, ik had wat meer moeten vertellen. Bedankt ervoor. Hopelijk kan iemand iets vertellen over de stellingen! Ik ben zelf inmiddels ook iets verder, maar helemaal duidelijk is het nog niet.

Gebruikersavatar
Marco
Beheerder
Beheerder
Berichten: 831
Lid geworden op: 19 feb 2005, 12:50
Locatie: Leeuwarden
Contacteer:

Bericht door Marco » 29 jan 2006, 17:25

Maar wat wordt er bedoelt met een even of oneven positie? Dat vat ik niet helemaal ;)
Groeten, Marco

xxxmoi
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 26 jan 2006, 19:28

Bericht door xxxmoi » 29 jan 2006, 18:05

Marco schreef:Maar wat wordt er bedoelt met een even of oneven positie? Dat vat ik niet helemaal ;)
Dat heeft te maken met de binaire getallen. De beginpositie is 1-3-5-7, dat is dan in binaire getallen 1-11-101-110. Opgeteld is dat dan een getal. Als er een oneven getal in de 'Nim-som' zit is het een oneven positie en anders een even. (dat weet ik nog :wink: )

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Bericht door Sjoerd Job » 29 jan 2006, 18:17

Ah! Ik zie het al!

Er zijn twee soorten posities: Even, en oneven.

Om hier achter te komen moet je de elke stapel verdelen in zulke groot mogelijke blokken van machten van 2...

11 wordt bijvoorbeeld een blok van 8, een blok van 2, en een blok van 1. 12 wordt een blok van 8, en een blok van 4.

Wanneer je deze blokken hebt gemaakt, zet je voor elke elke macht van 2 een colom, en dan zet je daaronder het aantal dat hier van voorkomt. Wanneer onder elke macht een even aantal staat, spreken we over een even positie, anders over een oneven.

Makkelijker is, om al deze aantallen binair op te schrijven, en dan te XOR'n, als het resultaat 0 is, is het een even positie. Heel erg simpel.

EDIT: Even om te melden dat ik dit heb gepost zonder het voorgaande antwoord van xxxmoi te lezen.
``Life is complex. It has real and imaginary parts.''

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Bericht door Sjoerd Job » 29 jan 2006, 19:48

Ok, nu ga ik even de stellingen aanpakken...
  1. De verliezer van het spel eindigt met een even positie (0-0-0-0).
  2. Een even positie wordt altijd veranderd in een oneven positie (en nooit in een even positie)
  3. Elke oneven positie kan altijd met een geldige zet in een even positie veranderd worden.
We hebben 4 stapels: a, b, c en d.

Om te kijken of het even of oneven is, kijken we naar ( De driehoek duidt hier op de "XOR"-operatie.

1: Van deze bewoording snap ik niet zo veel... ik kan hier dus ook nog niet op antwoorden.

2: Omdat wij een rij aanpassen, passen wij ook de nim-sum aan. Welke combinatie van groepen van machten van 2 wij ook weghalen, we maken de nim-som altijd oneven. Laten wij eens aannemen dat wij de som niet aanpassen... In ons bewijsje maakt het niet uit welke we aanpassen.

Laten wij dit versimpelen. Laten wij zeggen p = . Dan komen we op:

Dit is alleen mogelijk als , oftewel wanneer niks verwijderd is, en dat is in tegenstelling met het feit dat er iets moet worden weggenomen. Q.E.D.

3: Weer moeten wij eerst de "nim-som" vinden, ofwel de XOR van alle heaps. Deze noemen we q.
Als q 0 is, dan hebben we een even positie, dus daar hoeven we niet aan te denken bij dit bewijs.
Nu moeten we een stapel zo aanpassen dat de nim-som 0 wordt. Dit kan alleen als we een stapel XOR-en met q. want q XOR q = 0...
Wij kijken daarvoor naar de XOR's van alle stapels met q...
a XOR q = ...
b XOR q = ...
enzovoorts.
één of meer van deze uitkomsten is kleiner dan de oorspronkelijke waarde. Zorg bij een van de geldige stapels dat de waarde stapel XOR q wordt, en de stapel is nu wederom 0.
``Life is complex. It has real and imaginary parts.''

Plaats reactie