HET SPI
E WEB
Wiskundige onderzoekers voor één dag Johan Deprez 1
Het (1, 2, 3)-spel Misschien ken je dit spel wel… Op de tafel liggen een aantal lucifers, bijvoorbeeld 17. Twee spelers mogen om de beurt 1, 2 of 3 lucifers wegnemen. Wie niets meer kan wegnemen, verliest. Bij dit spel speelt toeval geen rol (omdat er bijvoorbeeld niet met dobbelstenen gegooid moet worden). Winnen of verliezen hangt af van de aanpak van de spelers. Een winnende strategie is een aanpak die garandeert dat je het spel wint, zelfs als je tegenstander het even verstandig aan boord legt. Via backtracking, achteruitredeneren vanuit de eindpositie van het spel, komen we er hier snel uit. Als jij aan zet komt wanneer er nog 1, 2 of 3 lucifers op de tafel liggen, neem je ze natuurlijk allemaal weg. Dit zijn drie winstposities. Als er nog 4 lucifers liggen wanneer jij aan zet bent, wint je tegenstander gegarandeerd omdat jij door de spelregels gedwongen wordt om je tegenstander een van de voorgaande drie winstposities aan te bieden. We noemen 4 daarom een verliespositie. Liggen er nog 5, 6 of 7 lucifers op de tafel, dan kun je je tegenstander in een verliespositie brengen. Dat zijn dus weer winnende posities. Door op die manier verder te redeneren, zie je in dat je het spel met de 17 lucifers kunt winnen als jij eerst aan zet komt. Neem eerst 1 lucifer weg zodat je je tegenstander 16 lucifers aanbiedt. Reduceer het aantal lucifers bij je volgende zetten achtereenvolgens tot 12, 8 en 4. Dat is altijd mogelijk, welke zet je tegenstander ook doet. Ten slotte kun jij de laatste lucifers wegnemen. De winnende strategie lees je eenvoudig af uit de onderstaande overzichtelijke voorstelling van de winsten verliesposities (in de vorm van 1-en en 0-en). We noemen de opeenvolging van nullen en enen de winstrij. aantal lucifers winst/verlies
0 0
1 1
2 1
3 1
4 0
5 1
6 1
7 1
8 0
9 10 11 12 13 14 15 16 17 1 1 1 0 1 1 1 0 1
Vangt het spel aan met 16 i.p.v. 17 lucifers, dan kan de beginnende speler niet winnen (tenzij de andere speler onverstandig speelt of een vergissing maakt).
Wiskundige onderzoekscompetenties, leerlingen als onderzoeker Het analyseren (en eerst spelen!) van het (1, 2, 3)-spel was een van de ‘opwarmopdrachten’ van de editie 2011 van de Wiskunde B-dag. Op een dag in november werken teams van drie of vier leerlingen uit de derde graad gedurende een hele dag in hun eigen school aan een wiskundige onderzoeksopdracht. Elk jaar ontwerpt de Wiskunde B-dagcommissie een dergelijke onderzoeksopdracht (zie www.wiskundebdagvlaanderen.be voor de volledige opdracht). Die van 2011 handelde dus over winnende strategieën bij spellen. 1
Met dank aan Ferdi Mattys, Lambert Vandeweert en hun leerlingen voor hun bijdrage aan de tekst en voor de foto’s.
2
het spinnenweb
Alle leerlingen in de derde graad aso moeten onderzoekscompetentie verwerven in de disciplines die verbonden zijn aan hun studierichting. In studierichtingen (natuur)wetenschappen moeten leerlingen bijvoorbeeld zelf een stukje natuurwetenschappelijk onderzoek uitvoeren: een onderzoeksvraag stellen, die beantwoorden door een geschikt experiment uit te voeren (of op een andere manier) en daarover rapporteren. Onderzoekscompetenties opbouwen ligt niet in alle studierichtingen even zeer voor de hand. Denk bijvoorbeeld aan talen. Ook voor wiskunde is het niet evident om leerlingen een onderzoek te laten opzetten dat recht doet aan wat wiskundig onderzoek eigenlijk is. Wiskundige onderzoekers bouwen nieuwe kennis op door voorbeelden te onderzoeken, eigenschappen te ontdekken en te bewijzen, nieuwe begrippen te construeren, nieuwe voorstellingswijzen uit te vinden… Met de wiskunde B-dag proberen we leerlingen dat ook te laten doen. Dat is niet gemakkelijk. Je moet een onderwerp vinden dat aanleiding geeft tot interessante vragen en waar leerlingen op hun niveau op een wiskundige manier aan de slag mee kunnen. De ene editie lukt dat al beter dan de andere…
Wegneemspellen Een echte wiskundige voelt na de inleiding natuurlijk een onweerstaanbare drang om aan de slag te gaan met allerlei varianten van het (1, 2, 3)-spel: wegneemspellen met een andere pakset dan {1, 2, 3}. En zo kom je al gauw terecht in een uitgebreid domein waarin de onderzoeksvragen voor het grijpen liggen, ook voor de leerlingen. Natuurlijk moet je hen wel wat stimuleren met voorbeelden, met concrete vragen en met suggesties voor onderzoeksvragen. Dat is ook wat in de opgave van de Wiskunde B-dag gebeurt. We geven je een inkijk op wat er op dit terrein zoal te beleven valt. Voor het wegneemspel met pakset {3, 4} (elke speler neemt dus 3 of 4 lucifers weg), begint de winstrij met meer nullen (zie onderstaande tabel). Omdat je nooit minder dan 3 lucifers mag wegnemen, kun je al geen zet meer doen zodra het aantal lucifers kleiner dan 3 geworden is. aantal lucifers winst/verlies
0 0
1 0
2 0
3 1
4 1
5 1
6 1
7 0
8 0
9 10 11 12 13 14 15 16 … 0 1 1 1 1 0 0 0 …
7 1
8 1
9 10 11 12 13 14 15 16 … 1 1 1 1 1 0 0 0 …
Voor pakset {6, 8} is de winstrij hieronder gegeven. aantal lucifers winst/verlies
0 0
1 0
2 0
3 0
4 0
5 0
6 1
Het verband met het vorige spel is duidelijk, zowel op het niveau van de pakset, die ‘verdubbeld’ is ( 6 2 3 en 8 2 4 ), als op het niveau van de tabel met de winstrij, waarin elke kolom als het ware ‘ontdubbeld’ is. Naast elke witte kolom heb je nu ook een overeenkomstige grijze kolom met hetzelfde winst- of verliesgetal op de tweede rij. Je krijgt als het ware een witte en een grijze versie van het oorspronkelijke spel. Begint het spel bijvoorbeeld op een witte positie, dan blijft het verder op de witte posities verlopen. Zes of acht lucifers wegnemen, komt overeen met drie of vier witte kolommen naar links opschuiven. Start je op een grijze positie, dan speel je het oorspronkelijke spel binnen de grijze kolommen. Deze mooie redenering komt van een van de deelnemende teams. Je kunt ze zonder meer veralgemenen naar grotere paksets en grotere factoren.
Periodiciteit Alle winstrijen die we tot nu toe gezien hebben, zijn periodiek. Dat de winstrij altijd periodiek is (tenminste als de pakset eindig is), kun je bewijzen. In de onderzoeksopdracht is hiervoor een voorzet gegeven, maar geen van de leerlingen heeft dit effectief kunnen bewijzen. Wellicht vergt zo’n redenering meer ervaring met eindige wiskunde.
3
Uitwiskeling 28/3 (zomer 2012)
Noem k het grootste getal in de pakset. Verdeel de winstrij vervolgens in opeenvolgende blokken van k posities, zoals hieronder aangegeven. aantal lucifers winst/verlies
0 …
… …
k–1 …
k …
… …
2k–1 2k … …
… …
3k–1 3k … …
… …
4k–1 … … …
Er zijn maar 2k mogelijkheden om nullen en enen in zo’n blok te plaatsen. Tussen de eerste 2k 1 blokken zitten er dus alleszins twee gelijke. Laten we die twee blokken A en B noemen. Veronderstel nu dat we het spel ontvangen in de positie die onmiddellijk volgt op blok A. Omdat we lucifers moeten wegnemen, maar nooit meer dan k, komen we onvermijdelijk ergens in blok A terecht. Of de positie die onmiddellijk op A volgt een winst- of verliespositie is, wordt daarom uitsluitend bepaald door de nullen en enen in blok A. Hetzelfde geldt voor de positie die onmiddellijk volgt op blok B. Omdat blok A en blok B gelijk zijn, zijn de posities volgend op A en B ofwel beide winstposities, ofwel beide verliesposities. Je kunt hetzelfde argument nu gebruiken om aan te tonen dat ook de twee daaropvolgende posities allebei winstposities of allebei verliesposities zijn. Enzovoort. Hiermee is aangetoond dat er inderdaad periodiciteit optreedt.
Periode We vinden meteen ook een bovengrens voor de periode: de maximale afstand tussen de beginposities van de twee gelijke blokken is k 2 k (de lengte van één blok maal het maximale aantal blokken tussen de beginposities). Voor het eerste voorbeeld hierboven is de bovengrens 24 terwijl de periode in werkelijkheid 4 is. Ook voor het tweede voorbeeld valt de bovengrens 64 veel groter uit dan de werkelijke periode 7. Je zou dus op zoek kunnen gaan naar een betere bovengrens, of in het beste geval zelfs naar een formule, voor de periode. Dat is geen sinecure, zoals blijkt uit de volgende twee voorbeelden. Voor het spel met pakset {1, 3}, is de winstrij gegeven door de onderstaande tabel. De periode 2 is korter dan je vooraf misschien verwacht had. aantal lucifers winst/verlies
0 0
1 1
2 0
3 1
4 0
5 1
6 0
7 1
8 0
9 10 11 12 13 14 15 16 … 1 0 1 0 1 0 1 0 …
Als je het spel moet beginnen op een even positie, dan ben je de klos. Dat kun je ook inzien zonder de winstrij uit te rekenen. Omdat beide getallen in de pakset oneven zijn, wisselt de pariteit van de positie bij elke zet. Je tegenstrever komt alleen op oneven posities en jij alleen op even posities. Omdat 1 in de pakset zit, zijn er geen oneven verliesposities. Je tegenstrever kan dus niet op een verliespositie terechtkomen. Omdat jij steeds naar een kleinere even positie gemanoeuvreerd wordt, eindig je onvermijdelijk op 0. Op basis van dit inzicht kun je snel veralgemenen: de paksets {1, 5}, {1, 107}, {1, 3, 7}, {1, 3, 5, …}, … hebben allemaal dezelfde winstrij (en dus ook dezelfde kleine periode) als hierboven. Met pakset {2, 5, 7} hebben we een langer stuk van de winstrij nodig (zie hieronder). De periode is nu immers 22, veel meer dan je op het eerste gezicht zou verwachten. aantal lucifers 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 winst/verlies 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 aantal lucifers 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 … winst/verlies 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 … Merk op dat we er zeker van kunnen zijn dat de periode inderdaad 22 is, ook al hebben we de tweede periode niet helemaal weergegeven. We hebben immers een blok van lengte 7 gevonden dat herhaald wordt en de afstand tussen de beginposities van die blokken is 22. Omdat 7 het grootste getal in de
4
het spinnenweb
pakset is, worden alle nullen en enen op de posities die volgen op de grijze blokken volledig bepaald door die in de grijze blokken. Als een algemene formule moeilijk ligt (en die hebben we in de literatuur overigens ook niet gevonden), dan is er ruimte voor deelresultaten. Veel teams zijn er bijvoorbeeld in geslaagd om dergelijke deelresultaten te vinden: een formule voor de periode als de pakset van de vorm {1, n}, {2, n} of {m, n} is, al dan niet met bijbehorend bewijs.
Eigenschappen van winstrijen Je kunt ook een andere toer opgaan en zoeken naar eigenschappen van winstrijen. Je kunt bijvoorbeeld beredeneren dat het maximale aantal opeenvolgende verliesposities gelijk is aan het kleinste getal in de pakset. Veronderstel immers dat er in de winstrij k verliesposities na elkaar voorkomen, waarbij k het kleinste getal in de pakset is. Dan is de volgende positie zeker een winstpositie. Immers, als je k lucifers wegneemt, ga je in de winstrij k plaatsen naar links. Volgens het gegeven is dat een verliespositie en zet je je tegenstander dus op een verliespositie. Analoog kun je beredeneren dat het maximale aantal opeenvolgende enen in verband staat met het grootste getal in de pakset. Een andere manier om eigenschappen van een winstrij op het spoor te komen, is je de omgekeerde vraag te stellen: als je een rij met nullen en enen hebt, is die dan altijd de winstrij van een wegneemspel? Aan welke voorwaarden moet ze eventueel voldoen?
Een niet-periodieke aanloop Als je het bewijs van de periodiciteit aandachtig bekijkt, dan merk je dat we enkel aangetoond hebben dat de winstrij vanaf een bepaald punt periodiek wordt. De vraag blijft dus of alle winstrijen effectief periodiek zijn dan wel of er ook een niet-periodieke ‘aanloop’ kan zijn (analoog aan de decimale voorstelling van rationale getallen). Sommige teams hebben voorbeelden gezocht en gevonden van winstrijen met een dergelijke niet-periodieke aanloop.
Wiskundig onderzoek op een moderne en aantrekkelijke manier Manueel opstellen van de winstrij van een wegneemspel vergt wel wat tijd. Daarom hadden de leerlingen een Excelbestandje ter beschikking dat de winstrij opstelde en de periode aanduidde als je de pakset ingaf. Zo werden ze van dat routinewerk verlost en konden ze snel vermoedens testen door voorbeelden te onderzoeken. We merkten dat teams ook nu en dan zelf de computer inschakelden bij hun onderzoek. Zo hebben verschillende teams een programma’tje geschreven voor de verliesposities
5
Uitwiskeling 28/3 (zomer 2012)
bij het ‘koninginnenspel’ dat hieronder nog aan bod komt. Denkwerk en computergebruik hoeven elkaar dus niet in de weg te zitten! Wel proberen we ervoor te zorgen dat leerlingen de oplossing van hun problemen niet (gemakkelijk) op het internet kunnen vinden, want dan komen de wiskundige onderzoeksmethoden natuurlijk niet meer tot hun recht. Leerlingen die in team werken, vinden meer dan individuele leerlingen. Dat ze dat teamwerk appreciëren, blijkt bijvoorbeeld uit de volgende getuigenissen van twee van de deelnemende teams: ‘De opdrachten waren leuk maar tegelijkertijd geen lachertje. Het lijkt ons bijna onmogelijk om deze opdrachten alleen af te werken, maar gelukkig mochten we deze opdracht in groepjes van 3-4 leerlingen afwerken zodat we elkaar konden motiveren en samen op zoek gaan naar de juiste oplossing. […] We hebben heel de dag hard mogen nadenken en hoewel we het niet helemaal gevonden hebben, vonden we het toch een geslaagde dag. Het onderwerp van het vraagstuk was alledaags en sprak ons zeker aan. Kortom, het was zeker voor herhaling vatbaar.’ ‘… De opdrachten waren interessant, het onderwerp was werkelijk boeiend en we hebben het met plezier onderzocht. Elk individu van onze groep heeft zijn steentje bijgedragen, waardoor we de hele dag vlot hebben kunnen werken… We hadden het gevoel dat we onze kennis steeds meer opbouwden, en daardoor kregen we de moed om voort te werken… Uiteindelijk voelt het zeer goed om een mooi verslag, dat werkelijk inhoud bevat, te kunnen inleveren en we zijn blij dat we ook dit jaar weer hebben kunnen meedoen aan deze unieke en zeer leerrijke activiteit.’ Een andere manier waarmee we de motivatie van de leerlingen verder proberen te verhogen, is door een (facultatieve) wedstrijd te verbinden aan de Wiskunde B-dag. Elke deelnemende school mag één of twee ‘werkstukken’ insturen voor de wedstrijd. Na een selectie op Vlaams niveau worden twee Vlaamse werkstukken ingestuurd voor de internationale wedstrijd, samen met twee Duitse en zes Nederlandse werkstukken (de aantallen zijn in verhouding tot het aantal deelnemende scholen). Op de prijsuitreiking in Utrecht wordt nog even ingegaan op de opdracht en de antwoorden, geïllustreerd met fragmenten uit de oplossingen van de teams en wordt de uiteindelijke volgorde bekendgemaakt. Ook dit jaar deden de Vlaamse inzendingen het weer erg goed, met een eerste en een zevende plaats.
Wegneemspellen met twee hopen lucifers in een meetkundig kleedje Je kunt wegneemspellen ook spelen met meer dan één hoop lucifers. Eerst bekijken we het wegneemspel met twee hopen en waarbij je 1 lucifer mag nemen van de ene hoop, van de andere hoop of van elk van beide hopen. Het spel is niet zo moeilijk om te analyseren, maar het gaat wel gemakkelijker als je het meetkundig voorstelt. De X in de figuur linksonder toont dat de eerste hoop 5 en de tweede hoop 7 lucifers telt. De meetkundige interpretatie van de spelregels is dat je de X één vakje naar links, één vakje naar boven of één vakje diagonaal naar linksboven mag verplaatsen (zie de middelste figuur). Je mag dus bewegen zoals een koning op een schaakbord, zij het dat je alleen in de richting van de linkerbovenhoek mag bewegen. Ook nu heb je winst- en verliesposities en speelt periodiciteit een rol (zie de figuur rechtsonder).
6
0 1 2 3 4 5 6 7
1
aantal tweede hoop 2 3 4 5 6
7
X
0
aantal eerste hoop
aantal eerste hoop
0
0 1 2 3 4 5 6 7
1
aantal tweede hoop 2 3 4 5 6
7
X X
X X
aantal eerste hoop
het spinnenweb
aantal tweede hoop 0 1 2 3 4 5 6 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 2 0 1 0 1 0 1 0 3 1 1 1 1 1 1 1 4 0 1 0 1 0 1 0 5 1 1 1 1 1 1 1 6 0 1 0 1 0 1 0 … … … … … … … …
… … … … … … … … …
Ook wanneer je in de richting van de linkerbovenhoek mag bewegen m.b.v. paardensprongen kun je de winst- en verliesposities vrij gemakkelijk achterhalen en treedt een eenvoudig periodiek patroon op.
Een van de slotopdrachten van de opgave was de studie van het ‘koninginnenspel’. Daarbij mag je een onbeperkt aantal vakjes naar links, naar boven of diagonaal naar linksboven. Dat bleek andere koek te zijn! Er zijn niet veel verliesposities (zie de grijze vakjes in de onderstaande figuur) en ze liggen allemaal in de omgeving van twee rechten. Geen enkel team heeft een volledige beschrijving kunnen geven van het bijzonder intregerende patroon van de verliesvakjes, maar dat kon ook niet verwacht worden. Bijna alle teams uit de finale van de wedstrijd hebben echter een of ander facet van dit patroon ontdekt. Sommigen concentreerden zich op de helling van de twee rechten. Anderen gingen op zoek naar periodiciteit en meenden die ook te vinden. Hoewel dat knap gezien was, treedt er echter ‘net geen’ periodiciteit op. Nu en dan zijn er kleine afwijkingen van het periodieke patroon. Eén groep legde zich toe op de ‘verschilvectoren’ tussen opeenvolgende verliesvakjes en ontdekte dat die een mooie fractale structuur bezitten. Maar die verklappen we niet, want we willen je het plezier niet ontzeggen om er zelf naar op zoek te gaan. 0 1 2 3 4 5 6 7 8 9 10 … 0 0 1 1 1 1 1 1 1 1 1 1 … 1 1 1 0 1 1 1 1 1 1 1 1 … 2 1 0 1 1 1 1 1 1 1 1 1 … 3 1 1 1 1 1 0 1 1 1 1 1 … 4 1 1 1 1 1 1 1 0 1 1 1 … 5 1 1 1 0 1 1 1 1 1 1 1 … 6 1 1 1 1 1 1 1 1 1 1 0 … 7 1 1 1 1 0 1 1 1 1 1 1 … 8 1 1 1 1 1 1 1 1 1 1 1 … 9 1 1 1 1 1 1 1 1 1 1 1 … 10 1 1 1 1 1 1 0 1 1 1 1 … … … … … … … … … … … … … …
7
