Speltheorie

[Physics]

Stel er liggen een aantal munten op de tafel... Er zijn twee spelers die om beurten een hoeveelheid munten mogen wegnemen. Winnaar is degene die de laatste munten wegneemt. De spelers kunnen per beurt kiezen hoeveel munten ze wegnemen. Die keuzemogelijkheden zijn vastgelegd in een verzameling, die we 'substraction sets' noemen. Bij elke hoeveelheid munten die op tafel ligt zijn er 2 gevallen mogelijk: Namelijk de N-positie of de P-positie. Een P-positie houdt in dat degene die nu aan zet is als hij optimaal speelt, het spel wint. Een N-positie houdt in dat degene die nu niet aan zet is, als hij optimaal speelt, het spel wint.

Ik heb nu vragen:

1) Geef de verzameling van de P-posities als de substraction set is: {1,3,5,7}

2) Geef de verzameling van de P-posities als de substraction set is: {1,3,6}

3) Geef de verzameling van de P-posities als de substraction set is: {1,2,4,8,16,32,...} (machten van 2)

Voor alle vragen zou ik ook nog graag willen weten wie er wint als je met 100 munten begint...

[oscar2]

Hoi,

Leuk probleem. Een handige formule heb ik nog niet gevonden. Maar, als je de N- een P-posities gaat opzoeken zie je snel genoeg dat er een patroon in zit. Dan moet je alleen nog bewijzen (met inductie) dat dat patroon ook klopt. de patronen zijn veel simpeler dan je misschien in eerste instantie zou denken.

Kijk maar even naar de 1e. {1,3,5,7}

Bij n=1 (1 muntje) verliest degene die begint: N

Bij n=2 wint degene die begint: P (1 muntje weghalen. dan is er nog 1 over en verliest de volgende)

Bij n=3 verliest degene die begint: N (je kunt alleen 1 muntje weghalen en dan heeft de volgende P (n=2).

etc.

Groet. Oscar