Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Winnende strategie Nimble

Hallo allemaal,

Voor een opdracht van school moet ik de winnende strategie van het Chinese spelletje Nimble kunnen vertellen. Maar deze weet ik dus niet meer. Kan iemand hier mij verder helpen?

Mvg,
Leerling VWO+2

Sander
Leerling onderbouw vmbo-havo-vwo - zaterdag 24 januari 2004

Antwoord

Beste Sander,

Bij het spelletje Nimble heb je een aantal schijfjes op een speel"bord" van een rij van vakjes liggen. In een vakje mag meer dan één schijfje liggen. Je speelt met twee personen. De bedoeling is dat je om de beurt één van de schijfjes een aantal vakjes naar links verplaatst, wie het laatste schijfje verplaatst naar het meest linkse vakje heeft gewonnen.

Bekijk nu het volgende "speelbord":

q19369img2.gif

We kijken naar hoeveel plaasten de schijfjes nog verplaatst kunnen worden. De twee schijfjes op het derde vakje van links kunnen bijvoorbeeld nog twee plaatsen naar links worden geschoven.

Zo bekeken hebben we in totaal
  • twee schijfjes die twee plaatsen verschoven kunnen worden,
  • één die drie verschoven kan worden,
  • één die vier verschoven kan worden en
  • één die vijf verschoven kan worden.
Die aantallen plaatsen die nog verschoven kunnen worden zetten we om in binaire getallen, voor het gemak met allemaal even veel binaire cijfers:

2 = 010
2 = 010
3 = 011
4 = 100
5 = 101

We kijken nu naar de "kolommen" van 0-en en 1-en. De achterste kolom bevat twee enen, de middelste kolom drie enen, de voorste kolom twee enen.

Een "winnende" zet maakt het aantal enen in elke kolom even. Er zijn soms meer mogelijkheden, zoals hierboven.
  1. Je zou hier dus een van de twee schijfjes op de derde plek van links helemaal naar links kunnen plaatsen,
  2. of het schijfje op de vierde plaats zou je naar de tweede plaats kunnen doen.
Controleer dat zelf maar eens.

Waarom is zo'n strategie altijd winnend?? Wel, als je een situatie voor je krijgt die allemaal even aantallen in de kolommen heeft, dan verander je door een schijfje te verplaatsen in minimaal één kolom precies één plek. Die kolom verandert dus van even in oneven.

En als er kolommen zijn met een oneven aantal, dan kun je dat weer altijd herstellen. Laten we bijvoorbeeld de volgende situatie eens bekijken:

Aantallen plaatsen die nog geschoven kunnen worden:

2 = 0010
13= 1101
14= 1110
8 = 1000
12= 1100

We schrijven even de kolommen waarin een oneven aantal is met een *, en even met een 0. Hier is dat dus 0*0*. Dat is alleen voor de duidelijkheid.
Je moet nu een schijfje zoeken waarmee je precies op de plaatsen van de * een 0 in een 1 of een 1 in een 0 kan veranderen. Bovendien moet het getal er kleiner van worden, anders zou je naar rechts schuiven.

Bijvoorbeeld, het schijfje met waarde 1100 (12), kun je veranderen in 1001 (9).

Het maakt niet uit welk schijfje je neemt om te verplaatsen. Je zag in het eerste voorbeeld al dat er meerdere mogelijkheden waren!

Zo'n schijfje kun je altijd vinden. Elk schijfje dat in de grootste oneven kolom een 1 heeft (dus in de 0100 positie in het voorbeeld) werkt. Er is altijd in elk geval één getal met een 1 in die kolom, want het aantal 1-en in die kolom was oneven.
Als je nu die 1 in een 0 verandert, en de andere posities ook aanpast, dan is het getal dat je krijgt altijd kleiner dan het getal dat het was. Dat betekent een verplaatsing naar links.

Zie Cut the knot: Nimble

FvL
zondag 25 januari 2004

©2001-2024 WisFaq