Tag archieven: wiskundig spel

Opgave 29

Geplaatst op door

n spelers spelen n spelen en winnen om de beurt. Telkens een speler wint, verdubbelt hij het bezit van zijn n-1 tegenspelers. Op het einde hebben ze allemaal evenveel. Hoeveel hadden ze in het begin?

Antwoord

  • Laten we eenvoudig beginnen met 3 spelers, die in het begin a,b en c bezitten. Het rijtje tussen resultaten van de eerste speler is (a, a-b-c,2(a-b-c),4(a-b-c)). Het rijtje voor de tweede speler is (b,2b,3b-a-c,2(3b-a-c)). tenslotte voor de derde speler (c,2c,4c,7c-a-b). Als ze allemaal evenveel hebben op het laatst dan moet 4(a-b-c)=2(3b-a-c)=7c-a-b.. Dit stelsels is gelijkwaardig met : 4b=7c en 4a=13c. Hieruit volgt dat a=13, b=7 en c=4.
  • Deze manier van werken wordt moeilijk voor willekeurige n.
  • Noteer met s het totaal bezit van alle spelers. Op het einde hebben ze dan allemaal \frac{s}{n}.
  • Na het eerste spel heeft de eerste speler a_1-a_2-\cdots-a_n=2a_1-s.
  • Al de volgende keren wordt zijn bedrag verdubbeld zodat hij op het einde 2^{n-1}(2a_1-s)=\frac{s}{n} heeft. Hieruit volgt dat n2^na_1=s(2^{n-1}n+1).
  • Een analoge redenering voor speler 2 geeft :n2^na_2=s(2^{n-2}n+1). Idem voor alle andere spelers.
  • Hieruit volgt dat ze allen op het einde 2^n bezitten en dat in het begin speler k een som van 2^{n-k}n+1 heeft

Nog een luciferspel

Geplaatst op door

Een willekeurig aantal lucifers is op willekeurige wijze verdeeld over twee stapels. Twee spelers nemen om de beurt lucifers weg: ofwel van één van de hopen 1,2,of 3 lucifers ofwel van beide hopen een zelfde aantal lucifers en dan ook 1,2 of 3. De speler die de laatste lucifer(s) wegneemt, wint.

We zoeken naar gunstige situaties. Met (a,b) noteren we de situatie waarbij er a lucifers op één hoop liggen en b lucifers op de andere stapel. De situaties (a,b) en (b,a) zijn identiek.

  • Met 1 lucifer hebben we enkel de situatie (1,0) en die is natuurlijk ongunstig want de tegenstrever kan gewoon die lucifer wegnemen en wint alzo het spel.
  • Met twee lucifers heb je (2,0), en (1,1) en beiden zijn ongunstig .
  • Met 3 lucifers heb je (3,0) en (2,1). De eerste situatie is zeker ongunstig maar (1,2) of (2,1) is wel degelijk gunstig, want wat de tegenstrever ook doet, hij komt terecht in een ongunstige toestand.
  • De situaties (2,2)  en (3,1) zijn ongunstig. Bij de eerste situatie kan de tegenstrever gewoon alles wegnemen en in het tweede geval kan hij door 1 lucifer weg te nemen terechtkomen in de winnende positie (2,1). Verder  is (4,0) uiteraard gunstig.

De situaties (4k,4l) en (4k+1,4l+2) zijn altijd gunstig. De winnende strategie bestaat erin elke gegeven spelsituatie om te zetten in een gunstige situatie. In sommige spelsituaties heb je de keuze  tussen twee of zelfs drie goede zetten. Zo kan je bijvoorbeeld (8,9) omzetten in de winnende situaties (8,8) en (6,9) door respectievelijk 1 lucifer weg te nemen van de stapel met 9 lucifers ofwel door er 2 weg te nemen van de andere stapel. Kies dan nu eens de ene en dan weer de andere voortzetting om de spelstrategie minder transparant te maken voor de tegenstrever. Als de winnende spelstrategie niet kan worden uitgevoerd, bestaat de optimale strategie erin 1 lucifer weg te nemen van de hoop met het meest aantal lucifers.

De Nederlandse wiskundige W.A. Wythoff  (6 oktober 1865 – 21 mei 1939) publiceerde in 1904 een analyse van dit spel.

Lucifers rapen

Geplaatst op door

Men legt drie hopen  voorwerpen op tafel. Er zijn twee spelers. Iedere speler moet om de beurt in één hoop ten minste 1 en ten hoogste alle voorwerpen wegnemen. Wie het laatste voorwerp opraapt wint. Bestaat er een mogelijke winststrategie?

Antwoord

  1. We gaan op zoek naar winstposities. Nu  zijn (0,0,0) en (1,1,0)  duidelijk winstposities. De combinaties (1,1,1) en (2,1,0) zijn verliessituaties, want de tegenstrever kan door 1 voorwerp weg te nemen steeds in een winstsituatie komen.
  2. Het idee groeit dat een binaire notatie ons kan helpen.  Vanaf nu wordt alles dus binair genoteerd!
  3. Dus (10,1,0) , maar ook (10,1,1) zijn verliessituaties. Maar (10,10,0) en is een winstsituatie, want als de tegenstrever de hele eerst hoop weghaalt, doe jij dat met de tweede hoop en win je dus. Neemt de andere speler slechts 1 voorwerp weg van de eerste hoop, doe jij dat ook bij de tweede hoop en kom je terecht bij (1,1,0) en dat is een winstsituatie.
  4. We vermoeden dat het totaal aantal enen op elke positie steeds even moet zijn voor een winstsituatie. Bij (10,10,0) heb je 0 enen op de laatste positie en 2 enen op de eerste positie. Dus dat zal een winstsituatie zijn.
  5. De speler die het eerst ervoor kan zorgen dat het totaal aantal enen op elke positie even is, zal ( als hij of zij maximaal speelt) steeds winnen. immers: als het aantal enen op elke positie even is, dan zal bij het wegnemen van een aantal voorwerpen, ten minste één cijfer 1 in een nul veranderen en dus zal de pariteit van die positie veranderen, zodat niet op elke positie het totaal aantal enen nog even is. Als omgekeerd bij bepaalde posities het aantal enen oneven is kan je steeds ervoor zorgen dat door het wegnemen van een aantal voorwerpen de pariteit op elke positie terug even is.

Het spel (of varianten daarvan) werd vermoedelijk al duizenden jaren gespeeld in het Verre Oosten. Het werd onder de naam Nim voor het eerst beschreven in 1901 door C. L. Bouton van de Harvard-universiteit, die ook de volledige theorie van het spel ontwikkelde. De naam komt wellicht van het Duitse woord nimm! hetgeen “neem!” betekent.

Het spel kan uiteraard, met dezelfde strategie, ook gespeeld worden met meer dan drie hopen.

Wie honderd zegt wint!

Geplaatst op door

Twee spelers zijn in competitie. De eerste speler A noemt een natuurlijk getal tussen 0 en 12 ( dus 1,2,…of 11). De tweede speler B telt er een getal tussen 0 en 12 bij op. Dan is het weer de beurt aan A die er weer een getal tussen 0 en 12 bij optelt. De speler die als eerste, binnen die spelregels, het getal 100 bereikt is de winnaar.

Antwoord

  1. We doen aan ‘back-tracking’: we zoeken van achter naar voren naar de winstposities.
  2. Wie 99 zegt verliest, want de andere speler doet er 1 bij en eindigt zo als eerste bij 100. Dus 99 is een verliespositie.
  3. Zo zijn 98,97,…89 ook allemaal verliesposities.
  4. Maar 88 is een winstpositie, want de volgende speler moet er een getal bij optellen uit {1,2,…,11}. Hij/zij kan nooit de 100 bereiken, maar als jij de terug aan beurt wel, kan je dat altijd. Niet toevallig is 88 = 100 – 12
  5. Zet je dit idee verder, dan zijn uiteraard ook 76,64,52,40,28,16,4 allemaal winstposities.
  6. Wie het spel begrepen heeft en eerst 4 ( of een andere winstpositie ) zegt wint het spel. Je moet, na de beurt van de tegenstrever, er voor zorgen dat je terug op een volgende winstpositie terecht komt.