WIE NIET ZOEKT, NIET VINDT. HEURISTIEKEN OM WISKUNDIGE PROBLEMEN OP TE LOSSEN SYLLABUS DAG VAN DE WISKUNDE 22 NOVEMBER 2014 MICHEL ROELENS (UC LEUVEN-LIMBURG; MARIA-BOODSCHAPLYCEUM; UITWISKELING)
ABSTRACT “Wie zoekt, die vindt” zegt het spreekwoord. In wiskunde is dit niet altijd het geval. Maar zonder te zoeken, vind je niet; anders is de opgave voor jou geen ‘probleem’ maar een ‘routinetaak’. Het Grieks voor ‘vinden’ is ‘heuriskein’. Heuristieken zijn zoekstrategieën zoals omgekeerd werken, een tekening maken, een patroon zoeken... Om een oplossing te vinden voor een wiskundig probleem, heb je naast heuristieken zeker ook wiskundige kennis nodig. Bovendien moet je in staat zijn om je eigen zoekproces te sturen en beschik je best over een beetje zelfvertrouwen. Maar in deze workshop focussen we op de heuristieken. We lossen enkele problemen op en we analyseren de heuristieken die van toepassing zijn. In de syllabus krijg je per heuristiek nog meer gelijkaardige problemen mee.
INHOUD VAN DE SYLLABUS Deze syllabus bevat de 10 problemen van de workshop; 12 extra problemen met oplossing en verder twee besprekingen uit Uitwiskeling als bijlagen. De eerste bespreking gaat over een boekje van Terence Tao, winnaar van de Fieldsmedaille, geschreven toen hij 15 jaar was, over hoe hij het aanpakt om problemen aan te pakken. De tweede bespreking gaat over een film van de jaren 1970 waarop de legendarische G. Pólya een probleem voorlegt aan een groep studenten. Deze film staat online.
SITUERING IN TELEGRAMSTIJL -
-
Problem solving is een essentieel aspect van wiskunde. Problem solving staat op de leerplannen. Een ‘probleem’ is een vraag waar je niet meteen een oplossingsmethode voor kent. Ook de gewone leerstof aanbrengen als ‘probleem’ aanbrengen. Schoenfeld (1985): liet ‘experts’ luidop denken bij het oplossen van problemen en concludeerde dat je de volgende vier zaken nodig hebt om problemen op te lossen: - kennis, - heuristieken, - zelfsturing, - ‘beliefs’. We focussen hier op de heuristieken.
Michel Roelens, Wie niet zoekt, niet vindt.
1
DE PROBLEMEN VAN DE WORKSHOP 1 AANTAL PALINDROOMGETALLEN (Posamentier & Krulik, 2008)
Hoeveel palindroomgetallen zijn er in {1, 2, 3, … , 1000}?
2 DE SNELHEID VAN DE AUTO (Posamentier & Krulik, 2008)
Een auto rijdt op een autoweg tegen 110 km/h. De chauffeur ziet een tweede auto, exact 1 km achterop. Exact 1 minuut later haalt de tweede auto de eerste in. Hoe snel reed de tweede auto, in de veronderstelling dat zijn snelheid constant is?
Michel Roelens, Wie niet zoekt, niet vindt.
2
3 PIZZA IN STUKKEN Voor je ligt een grote pizza. Die mag je door rechte lijnen (volledige koorden) in stukken snijden. Hoeveel stukken kun je maximaal maken als je langs 10 rechte lijnen mag snijden?
4 SOM VAN DE COËFFICIËNTEN (Posamentier & Krulik, 2008)
Bereken de som van de coëfficiënten van (𝑥 + 𝑦)8 .
Michel Roelens, Wie niet zoekt, niet vindt.
3
5 VIERKANTEN IN HET SCHAAKBORD Hoeveel vierkanten kan ik maken in een schaakbord? Een schaakbord heeft 8x8 vakjes en je mag geen lijnen bijtekenen.
6 HOEK TUSSEN DE WIJZERS Op deze klok is het ongeveer tien vóór twee. De wijzers staan dan zo dat ze elkaars spiegelbeeld zijn ten opzichte van de as 12u-6u. Bepaal voor deze situatie de exacte grootte van de hoek tussen de twee wijzers.
Michel Roelens, Wie niet zoekt, niet vindt.
4
7 HET 64-SPEL Twee spelers noemen om beurten een getal van 1 tot 8. Alles wordt opgeteld. Wie het laatste getal zegt zodat de som juist 64 wordt, wint. Je mag beginnen. Is er een strategie om altijd te winnen?
8 DE LENGTE VAN DE TUNNEL Je staat 100 m vóór de ingang van een tunnel. Je ziet de diameter van de ingang van de tunnel drie keer zo groot als de diameter van de uitgang. Hoe diep is de tunnel?
Michel Roelens, Wie niet zoekt, niet vindt.
5
9 DE KIKKER (Posamentier & Krulik, 2008)
Een kikker zit op de bodem van een waterput die 10 meter diep is. Elke dag klimt de kikker 50 cm, maar ’s nachts valt hij in slaap en zakt hij weer 40 cm. Hoe lang duurt het voor de kikker uit de put geraakt?
10 DE KOMKOMMERS Gegeven: 500 kg komkommers, die voor 99% uit water bestaan. Na een week bevatten ze nog 98% water. Hoeveel wegen ze nog?
Michel Roelens, Wie niet zoekt, niet vindt.
6
EXTRA PROBLEMEN 1 EI KOKEN (Posamentier & Krulik, 2008)
Hoe kun je een ei exact 15 minuten laten koken als je beschikt over twee timers, één van 7 minuten en één van 11 minuten? Het gaat hier over timers die enkel op het einde een belsignaal geven, maar waarop de tussentijd niet af te lezen is. 15 = 11 + 4, dus als we een manier vinden om 4 minuten af te meten met die twee timers, dan is het probleem opgelost. Nu is 4 = 11 − 7. We kunnen beide timers tegelijk aanzetten, en intussen zorgen dat het water al kookt. Nadat de timer van 7 minuten afgaat, doen we het ei in het water. Tegen dat de timer van 11 minuten afgaat, zitten we al aan 4 minuten kooktijd. We zetten dan meteen de timer van 7 minuten weer op en wanneer die rinkelt, halen we het ei uit het water. Heuristiek: omgekeerd werken.
2 EMMERS VULLEN Je hebt twee emmers zonder merkstreepjes (het zijn dus géén maatbekers), één van 9 liter en één van 4 liter. Hoe kun je hiermee precies 6 liter water uit een waterput afmeten?
Om 6 liter in de emmer van 9 liter over te houden, willen we die helemaal vullen en er 3 liter uit wegnemen. Dit lukt als we in de kleine emmer 1 liter water hebben staan.
Hoe kunnen we 1 liter ‘maken’ met deze twee emmers? 1 liter = 9 liter − 4 liter − 4 liter.
Heuristiek: omgekeerd werken. Michel Roelens, Wie niet zoekt, niet vindt.
7
3 ZWAARTELIJNEN (Posamentier & Krulik, 2008)
Construeer een driehoek waarvan de lengten van de zwaartelijnstukken gegeven zijn. Met zwaartelijnstuk bedoel ik het stuk van een zwaartelijn dat binnen de driehoek valt, anders gezegd het lijnstuk tussen een hoekpunt en het midden van de overstaande zijde. Het probleem is dat we van de zwaartelijnstukken enkel de lengten kennen, niet de hoeken waaronder ze elkaar snijden. We vertrekken van een schets van de oplossing: een driehoek 𝐴𝐵𝐶 met de drie zwaartelijnen [𝐴𝑀], [𝐵𝑁] en [𝐶𝑃] die elkaar snijden in het zwaartepunt 𝑍.
We weten dat |𝐴𝑍| = 2|𝑍𝑀| (en onze leerlingen leren dit in het derde jaar). Als we dus [𝑍𝑀] verlengen tot een lijnstuk [𝑍𝑄] dat twee keer zo lang is, dan is |𝐴𝑍| = |𝑍𝑄|. Bovendien is 𝐵𝑍𝐶𝑄 dan een vierhoek met diagonalen die elkaar middendoor snijden. Een dergelijke vierhoek is altijd een parallellogram (dat weten wij, en onze leerlingen leren dit in het tweede jaar).
Nu is de driehoek 𝐶𝑍𝑄 te construeren op basis van de gegeven lengten van de zwaartelijnstukken: elke van de 2
drie zijden is immers 3 van een zwaartelijnstuk, en een driehoek met drie gegeven zijden is construeerbaar met passer en liniaal! Als deze driehoek geconstrueerd is, lukt de rest ook! Heuristieken: omgekeerd werken, een tekening maken. Merk op dat deze heuristieken hier gecombineerd zijn met het steunen op meetkundige kennis (positie zwaartepunt; kenmerk parallellogram). Feitenkennis is belangrijk om problemen op te lossen!
4 OVERSTAANDE HOEKEN (Posamentier & Krulik, 2008)
Hoeveel paar overstaande hoeken worden gevormd door 10 rechten die elkaar in één punt snijden. (Enkel hoeken strikt kleiner dan 180° tellen mee.) Tellen is lastig. Laten we beginnen met minder rechten. (Teken mee.) -
1 rechte: 0 paar overstaande hoeken. 2 rechten: 2 paren overstaande hoeken. 3 rechten: 6 paren overstaande hoeken. 4 rechten: 12 paren overstaande hoeken. 5 rechten: 20 paren overstaande hoeken. Michel Roelens, Wie niet zoekt, niet vindt.
8
Hier is een patroon in te zien: 20 = 5 ∙ 4; 12 = 4 ∙ 3; 6 = 3 ∙ 2. Als dit patroon zich inderdaad verderzet, zijn er bij 10 rechten 10 ∙ 9 = 90 paren overstaande hoeken. Kunnen we het patroon verklaren? Elke nieuwe rechte die erbij komt, vormt met elke ‘oude’ rechte twee paar overstaande hoeken die nog niet geteld was. Bv. van vier naar vijf rechten: er waren 12 paren overstaande hoeken; de vijfde rechte zorgt voor 8 nieuwe paren overstaande hoeken; 12 + 8 = 20. Met dit idee kan de ‘inductiestap’ gezet worden in een bewijs door volledige inductie: als 𝑛 rechten 𝑛(𝑛 − 1) paren overstaande hoeken bepalen, dan zorgt de 𝑛 + 1-ste rechte voor 2𝑛 nieuwe paren overstaande hoeken. Welnu: 𝑛(𝑛 − 1) + 2𝑛 = (𝑛 + 1)𝑛. Je kunt het ook anders bekijken: elk paar rechten zorgt voor twee paar overstaande hoeken (en die horen enkel 2 bij dat paar). Als er 10 rechten zijn, dan kun je hierin 𝐶10 = 45 paar vinden. Dus: 45 ∙ 2 = 90 paar overstaande hoeken. Heuristieken: Patroon zoeken; ander standpunt innemen.
5 DE LOCKERS (Posamentier & Krulik, 2008) Er wordt een nieuwe school gebouwd met 1000 (genummerde) lockers. Het toeval wil dat er juist 1000 leerlingen inschrijven. Alle lockers zijn dicht. Op de eerste schooldag spreken de leerlingen het volgende af. De eerste leerling zal alle lockers openen. De tweede zal alle lockers omswitchen die een veelvoud van 2 zijn (van open naar dicht of omgekeerd). De derde zal alle lockers omswitchen die een veelvoud van 3 zijn. Enz. Als alle leerlingen gepasseerd zijn, hoeveel lockers zullen er dan open zijn? Laten we het eens proberen voor 10 lockers en 10 leerlingen i.p.v. 1000. We maken een tabel Locker
1
2
3
4
5
6
7
8
9
10
Leerling 1
O
O
O
O
O
O
O
O
O
O
Leerling 2
O
D
0
D
O
D
O
D
O
D
Leerling 3
O
D
D
D
O
O
O
D
D
D
Leerling 4
O
D
D
O
O
O
O
O
D
D
Leerling 5
0
D
D
O
D
O
O
O
D
O
Leerling 6
0
D
D
O
D
D
O
O
D
O
Leerling 7
0
D
D
O
D
D
D
O
D
O
Leerling 8
0
D
D
O
D
D
D
D
D
O
Leerling 9
0
D
D
O
D
D
D
D
O
O
Leerling 10
0
D
D
O
D
D
D
D
O
D
Lockers 1, 4 en 9 zijn open, de kwadraten. Inderdaad: alle getallen behalve de kwadraten hebben een even aantal delers, want die delers komen in paren voor. 10: 1 en 10; 2 en 5; 12: 1 en 12; 2 en 6; 3 en 4 Maar de kwadraten hebben een oneven aantal delers. 9: 1 en 9; 3 16: 1 en 16; 2 en 8; 4. Een oneven aantal keren omswitchen levert als resultaat op: ‘open’.
Michel Roelens, Wie niet zoekt, niet vindt.
9
Omdat 312 = 961 < 1000 < 1024 = 322 , zijn er 31 kwadraten in {1, 2, 3 … 1000}. Er zullen dus 31 lockers open zijn.
6 0PPERVLAKTE TUSSEN DRIEHOEKEN (Posamentier & Krulik, 2008)
Vind de oppervlakte van het gebied tussen de driehoek 𝐴𝐵𝐶 en de driehoek 𝐺𝐻𝐼, als je weet dat de zijden van de drie driehoeken evenwijdig zijn en op afstand 1 van elkaar liggen. De zijden van de driehoek 𝐷𝐸𝐹, de middelste van de drie, zijn 5, 6 en 7 (zie figuur).
De voor de hand liggende methode is: bereken de oppervlakten van Δ𝐴𝐵𝐶 en Δ𝐺𝐻𝐼 en trek die van elkaar af. Het is echter veel gemakkelijker om de gevraagde oppervlakte te berekenen als je die bekijkt als de som van de oppervlakten van de trapezia 𝐵𝐶𝐼𝐻, 𝐶𝐴𝐺𝐼 en 𝐴𝐵𝐻𝐺, namelijk: 5 ∙ 2 + 6 ∙ 2 + 7 ∙ 2 = 36. Heuristiek: een ander standpunt innemen.
7 BANKEN IN DE KLAS (Posamentier & Krulik, 2008)
In een klaslokaal staan 25 banken in een vierkant patroon, vijf rijen van vijf. Alle plaatsen zijn bezet. De leraar geeft aan alle leerlingen de opdracht om zich te verplaatsen, namelijk één bank naar voor, naar achter, naar links of naar rechts. Kan de klas dit bevel opvolgen? Als je het lokaal voorstelt als een schaakbord van vijf op vijf vierkantjes, om beurten wit en zwart gekleurd, dan moeten de leerlingen van een wit naar een zwart vierkantje verhuizen of omgekeerd. Maar: er zijn 13 zwarte en 12 witte vierkantjes. De opdracht is dus onmogelijk.
Heuristieken: Een ander standpunt innemen; een tekening maken.
Michel Roelens, Wie niet zoekt, niet vindt.
10
8 STRAAL VAN DE CIRKEL Gegeven is een gelijkzijdige driehoek ABC met zijde 1. Op het verlengde van de zijde [BC] kiezen we punten A1 (aan de kant van B) en A2 (aan de kant van C) zodat |A1B| = |A2C| =|BC| = 1.. Analoog kiezen we B1, B2, C1 en C2. Bereken de straal van de cirkel door A1, B2, C1, A2, B1 en C2. Het middelpunt van de omgeschreven cirkel van driehoek ABC is ook het middelpunt van de cirkel door A1, B2, C1, A2, B1 en C2. (Dit volgt duidelijk uit de symmetrie; je hoeft het niet te bewijzen.) Maak een tekening. Noem M middelpunt. Noem D het midden van [BC].
Pythagoras in ABD: |𝐴𝐷| =
√3 2
M is zwaartepunt, dus: |𝑀𝐷| =
√3 6
Pythagoras in A1MD: straal = |𝑀𝐴1 | =
√21 3
Heuristiek: een tekening maken. Ook kenniselementen: positie zwaartepunt; stelling van Pythagoras.
9 DOBBELSTEEN (Posamentier & Krulik, 2008)
Bij een dobbelsteen is de som van de ogen op twee overstaande zijvlakken altijd 7. Hoeveel verschillende waarden heeft de som van de ogen op drie zijvlakken die in één hoekpunt samenkomen? De overstaande zijvlakken hebben dus (1 en 6), (2 en 5) en (3 en 4) ogen. Rond een hoekpunt heb je telkens drie ogenaantallen, één uit elk van deze paren. Dit geeft: 1+2+3=6 1+2+4=7 1+5+3=9 1 + 5 + 4 = 10 6 + 2 + 3 = 11 6 + 2 + 4 = 12 6 + 5 + 3 = 14 6 + 5 + 4 = 15. Er zijn dus acht verschillende sommen, rond elk hoekpunt een andere som. Heuristiek: alle mogelijkheden overlopen. Michel Roelens, Wie niet zoekt, niet vindt.
11
10 SOM VAN KWADRATEN (Posamentier & Krulik, 2008)
Een regelmatige twaalfhoek is ingeschreven in een cirkel met straal 1. P is een willekeurig punt van die cirkel. Bepaal de som van de kwadraten van de afstanden van P tot de hoekpunten. Het gaat over een som van 12 kwadraten van afstanden. Als je de termen zo groepeert, dat je de kwadraten van de afstanden tot overstaande hoekpunten bij elkaar neemt, dan heb je zes keer de diameter 2 in het kwadraat, dus is de gevraagde som 24.
Heuristieken: een tekening maken, een ander standpunt innemen. Ook kenniselementen spelen hier een cruciale rol: omtrekshoek op een halve cirkel; stelling van Pythagoras.
11 KOOPJES Wat is het voordeligst:
Eerst 20% korting, dan 15% erbij? Eerst 15% erbij, dan 20% korting?
Start met 100 euro 100 −20 80 +12 92 100 +15 115 −23 92 Beiden zijn dus even voordelig. De berekening hierboven geeft het antwoord, maar laat nog niet duidelijk zijn ‘waarom’ het gelijk is. Michel Roelens, Wie niet zoekt, niet vindt.
12
Zo zie je het wel: door de commutativiteit van de vermenigvuldiging... Heuristiek: werken met concrete getallen
12 GEBIEDEN KLEUREN Hoeveel verschillende kleuren heb je nodig om een vierkant in te kleuren dat verdeeld is door 𝑛 rechten? (Gebieden met een gemeenschappelijk lijnstuk als grens moeten een verschillende kleur hebben.) Bewijs! Begin bij 𝑛 = 1, dan 2, dan 3...
Wanneer er een rechte bij komt, wisselen we de kleuren aan één kant. (volledige inductie...) Besluit: 2 kleuren volstaan.
Michel Roelens, Wie niet zoekt, niet vindt.
13
BIJLAGE 1 BESPREKING UIT UITWISKELING 24/3 (ZOMER 2008) Terence Tao, Solving mathematical problems. A personal perspective Oxford University Press, Oxford / New York, 2006, ISBN 978-0-19-920560-8. Terence Tao, winnaar van de Fieldsmedaille in 2006, is hoogleraar wiskunde aan de University of California te Los Angeles. Hij schreef dit boekje in 1990 toen hij … 15 jaar oud was. Op dat moment had hij al, op 12-, 13- en 14-jarige leeftijd, achtereenvolgens brons, zilver en goud gewonnen op de internationale wiskundeolympiade! In dit boekje legt hij aan de hand van een aantal olympiadevragen uit wat het denkproces is dat tot een oplossing kan leiden. Ik heb dit boekje graag gelezen, niet zozeer vanwege de opgaven (er bestaan veel boeken met mooie, opgeloste wiskundeproblemen), maar vooral omdat Tao heel eerlijk en gedetailleerd zijn gedachtegang beschrijft. Hij geeft niet zomaar de kortste of de meest elegante oplossing, maar voert de lezer echt mee doorheen zijn denkproces. Hij besteedt aandacht aan het begrijpen van de opgave, aan de psychologie van de vraagsteller (“de kans is groot dat hij het zo bedoelt, anders had hij de vraag anders geformuleerd…”), aan de efficiëntie van de tijdsbesteding (“deze berekening zou lastig kunnen zijn, laten we eerst proberen om het te vermijden”), aan het herformuleren van de opgave en aan vele andere heuristieken en oplossingsstrategieën… Ook omwegen of doodlopende straatjes komen wel eens aan bod. Je merkt op elke bladzijde hoe leuk deze 15-jarige wiskunde vindt en hoe helder hij denkt. Het boek bevat ook een aantal oefeningen zonder oplossing, analoog aan de uitgewerkte voorbeelden. In de inleiding waarschuwt de auteur voor overdreven verwachtingen: wiskundige problemen oplossen is niet zomaar te herleiden tot het toepassen van een aantal trucjes: “Two of the main weapons – experience and knowledge are not easy to put into a book. But there are many simpler tricks that make it easier to find a feasible attack plan. There are systematic ways of reducing a problem into successively simpler sub-problems.” Om een idee te geven, beschrijf ik in het kort twee van de opgaven die Tao in het boekje oplost.
Machten van twee met dezelfde cijfers… Probleem 2.2 Bestaat er een macht van 2 waarvan je de cijfers kunt herschikken tot een andere macht van 2? (Getallen die met een nul beginnen, zoals 0302, zijn niet toegelaten.) De opgave lijkt moeilijk, want het herschikken van cijfers kan op heel veel manieren gebeuren en het lijkt niet makkelijk om afzonderlijke cijfers te bepalen van een macht van 2. Kunnen we een oplossing vinden door te raden? Waarschijnlijk niet, anders zou deze vraag niet op een wiskundecompetitie gesteld worden. Misschien bestaat er een oplossing met veel cijfers, die je alleen kunt vinden met een ingewikkelde constructie. Maar het is wellicht moeilijk om zo’n constructie te bedenken. “We should rather take a sensible look around before plunging into deep water”… Laten we dus eerst proberen om te bewijzen dat er geen zo’n getal bestaat. Als dit lukt, hebben we veel tijd gewonnen en als het niet lukt dan zit er niets anders om toch maar werk te maken van de waarschijnlijk lastige constructie. Laten we eens denken aan bekende eigenschappen van machten van 2 om te zien of we er een vinden die niet compatibel is met het wisselen van cijfers. We schrijven alvast de eerste machten van 2 op: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,1024, 2048, 4096, 8192, 16384, 32768, 65536, … We zien niet meteen iets speciaals aan de cijfers. Het laatste cijfer is natuurlijk altijd even (behalve bij 1), maar de andere cijfers kunnen op het eerste gezicht gelijk wat zijn. Neem bv. 4096. Kunnen we het herschikken tot een andere macht van 2 die we nog niet hebben opgeschreven? Neen, want we hebben maar vier cijfers. Misschien is dit iets bruikbaars: als we de cijfers herschikken blijft het aantal cijfers hetzelfde. (Nogal wiedes, maar ook evidente zaken zijn soms nuttig!) Dit leidt tot een veel makkelijker probleem.
Michel Roelens, Wie niet zoekt, niet vindt.
14
Verwant probleem Bestaan er twee machten van 2 met hetzelfde aantal cijfers? Als het antwoord neen is, is het antwoord op het oorspronkelijke probleem ook neen. Helaas is het antwoord op deze vraag ‘ja’: 2048 en 4096 hebben bv. hetzelfde aantal cijfers. Dit betekent nog niet dat het antwoord op de oorspronkelijke vraag ook ‘ja’ is. Het kan zijn dat we het probleem te fel hebben vereenvoudigd; dat we rekening moeten houden met meer eigenschappen dan enkel het aantal cijfers. Laten we nog eens kijken naar 4096 en de andere machten van 2 met evenveel cijfers: 1024, 2048, 4048 en 8192. Er zijn er vier. Kunnen er ook meer dan vier getallen met evenveel cijfers in het rijtje voorkomen? Neen: het eerste cijfer van het kleinste getal is minstens 1 en wordt steeds verdubbeld: 1··, 2··, 4··, 8··, 16·· . Dit betekent dat er voor elke macht van 2 hoogstens drie kandidaten zijn voor getallen met dezelfde cijfers. We staan al een stap verder: misschien kunnen we iets vinden om deze drie kandidaten uit te schakelen. Het volstond blijkbaar niet om enkel naar het aantal cijfers te kijken. Laten we zoeken of er nog iets anders is dat behouden blijft bij het verwisselen van de cijfers. Wat hebben getallen met dezelfde cijfers nog met elkaar gemeen? Ze hebben bv. dezelfde som van de cijfers! Dit leidt tot het volgende probleem. Verwant probleem Bestaan er twee machten van 2 met hetzelfde aantal cijfers en met dezelfde som van de cijfers? Als het antwoord neen is, is het antwoord op het oorspronkelijke probleem ook neen. Laten we eens kijken naar de som van de cijfers van de eerste machten van 2: 1, 2, 4, 8, 7, 5, 10, 11, 13, 8, 7, 14, 19, 20, 22, 26, 25, … Deze sommen zijn vrij kleine getallen. Dit is misschien pech, want kleine getallen hebben een grotere kans om aan elkaar gelijk te zijn. De rij van de sommen gaat op en neer maar lijkt globaal een stijgende trend te vertonen (wat niet verrassend is). Het beschouwen van het aantal cijfers volstond niet; het lijkt erop dat we ook met de som van de cijfers vast zitten. De som van de cijfers heeft veel te maken met de rest bij deling door 9, anders gezegd met de som van de cijfers modulo 9. We weten dat de som van de cijfers modulo 9 gelijk is aan het getal zelf modulo 9 (m.a.w. de rest bij deling van het getal door 9). Laten we dit eens proberen. Verwant probleem Bestaan er twee machten van 2 met hetzelfde aantal cijfers en met dezelfde rest bij deling door 9? Als het antwoord neen is, is het antwoord op het oorspronkelijke probleem ook neen (want het verwisselen van cijfers verandert niets aan de som van de cijfers modulo 9). Laten we kijken naar de resten bij deling door 9 (die we evengoed kunnen berekenen aan de hand van de reeds berekende sommen van de cijfers): 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7, … Nu zien we onmiddellijk een patroon: er is een ‘periode’ van zes resten die steeds terugkomen. Even controleren dat dit patroon inderdaad altijd zal terugkomen: 2n+6 = 2n26 = 2n · 64 2n (mod 9) want 64 1 (mod 9). Er zijn zeker machten van 2 die dezelfde rest hebben bij deling door 9 (bv. 1 en 64 of 2 en 128), maar die liggen in de rij te ver uit elkaar om hetzelfde aantal cijfers te hebben (zie hoger: hoogstens vier opeenvolgende machten van 2 kunnen hetzelfde aantal cijfers hebben). Hiermee is dus het oorspronkelijke probleem opgelost! Even de gevonden redenering samenvatten.
Michel Roelens, Wie niet zoekt, niet vindt.
15
Veronderstel dat er een macht van 2 zou bestaan waarvan je de cijfers kunt herschikken tot een andere macht van 2. Dan zouden deze twee machten van 2 hetzelfde aantal cijfers hebben en dezelfde rest bij deling door 9. Maar de resten bij deling door 9 van de opeenvolgende machten van twee vormen een periodieke rij met periode 6, zonder herhaling binnen één periode. De twee getallen zouden dus minstens een onderlinge afstand van 6 hebben binnen de rij, maar dan kunnen ze niet hetzelfde aantal cijfers hebben.
Chocolade Probleem 6.3 Twee mensen spelen een spel met een grote chocoladereep die uit 60 vierkante stukken bestaat, in een rechthoek van 6 bij 10. De eerste speler breekt de reep in twee stukken volgens één van de lijnen die de reep in vierkantjes verdelen. Hij eet één van de twee stukken op. De tweede speler breekt op dezelfde manier het overblijvende stuk in tweeën en eet één stuk op. Enzovoort. Wie niet meer kan spelen omdat hij van de andere speler één stukje van 1 bij 1 krijgt, is verloren. Voor welke speler bestaat er een winnende strategie? In de speltheorie kan men aantonen dat elk eindig strategisch spel voor twee spelers die om beurten een zet mogen doen, een niet-verliezende strategie heeft voor één van de spelers. Omdat hier gelijkspel niet mogelijk is, bestaat er dus een winnende strategie. Eerst moet het probleem vertaald worden van chocolade naar wiskunde. Het gaat over een rechthoek van 6 bij 10. Je kunt die bv. verdelen in twee rechthoeken van 6 bij 7 en 6 bij 3 Of in twee rechthoeken van 2 bij 10 en 4 bij 10. Eén van de twee blijft over. Van de twee afmetingen wordt één behouden en wordt de andere een kleiner natuurlijk getal (verschillend van nul). Laten we een notatie invoeren voor de rechthoeken. Ze zijn bepaald door twee getallen. We noteren bv. de oorspronkelijke reep als (6, 10). De mogelijke zetten vanaf (6, 10) zijn (6, 1), (6, 2), …, (6, 9); (1, 10), (2, 10), …, (5, 10). Als we deze koppels voorstellen in een assenstelsel, dan vertrekken we in het punt (6, 10) en mogen we evenwijdig met één van de assen naar de oorsprong toe bewegen. Het probleem kan dus als volgt worden geherformuleerd. Herformulering Twee spelers bewegen om beurten een punt in een rooster, over een geheel aantal stapjes naar links of naar onder. Het punt start in (6, 10) en kan nooit op of voorbij een as geraken. De winnaar is wie het punt (1, 1) bereikt. Wie heeft een winnende strategie? Je kunt ook zeggen dat het punt start in (5, 9), dat je wel op maar niet voorbij een as mag komen en dat je wint als je in (0, 0) komt. Nog een andere formulering: Herformulering Er zijn twee stapels kaartjes, een stapel van 5 en een stapel van 9. Elke speler moet om beurten één of meer kaartjes wegnemen van één van de twee stapels. Wie de laatste kaart wegneemt is gewonnen. We hebben nu zeker goede wiskundige modellen. Maar de moeilijkheid is dat er zoveel mogelijkheden zijn. Daarom kunnen we eerst het spel met kleinere aantallen spelen. Het ‘verschuiven’ van (1, 1) naar (0, 0) laten we (voorlopig?) links liggen. Stel dat we starten met reep of punt (2, 3). De eerste speler kan naar (1, 3), (2, 2) of (2, 1). Maar (1, 3) of (2, 1) is niet slim want daarmee kan de tweede speler gemakkelijk naar (1, 1). Dus moet de eerste speler naar (2, 2). De tweede speler is dan verplicht om naar (2, 1) of (1, 2) te gaan en de eerste speler wint. Dus: als men start in (2, 3) is de eerste speler gewonnen. Laten we nu starten in (3,3). Naar (1, 3) of (3, 1) gaan is niet goed. Maar ook naar (2, 3) is geen goed idee want we hebben zojuist gezien dat met (2, 3) mag starten, altijd kan winnen. En (3, 2) is natuurlijk even slecht als (2, 3). Dus zal de eerste speler verliezen als men start in (3, 3). Michel Roelens, Wie niet zoekt, niet vindt.
16
We losten het op voor (3, 3) steunend op wat we wisten voor (2, 3). Dit suggereert een recursieve werkwijze. Door de symmetrie kunnen we ons beperken tot (a, b) met a b. (1, 1) is verliezend (wie dit krijgt, is verloren). (1, n) met n > 1 is winnend (wie dit krijgt, kan de andere (1, 1) geven). (2, 2) is verliezend (wie dit krijgt, moet de andere (1, 2) geven en dus laten winnen). Dus is (2, n) met n > 2 winnend (wie dit krijgt, kan de andere (2, 2) geven. Enzovoort. We zouden hiermee stap voor stap kunnen verdergaan tot (6, 10). Maar het is leuker om een patroon te zoeken voor de winnende en verliezende punten. Hierboven merkten we de volgende eigenschappen op.
Als (a, b) verliezend is, dan is (a, c) met c > b winnend, want wie dit krijgt, kan aan de andere (a, b) geven.
(a, b) is verliezend als je van hieruit enkel naar winnende posities (voor de tegenpartij) kunt gaan.
Als we alle winnende punten die we al kennen in het vlak aanduiden, en de verliezende punten in een andere kleur, krijgen we de indruk dat de verliezende punten gewoon de punten (x, x) zijn en dat de andere punten allemaal winnend zijn. Anders gezegd: als de reep chocolade vierkant is, zal de eerste speler verliezen en anders kan de eerste speler winnen. Met dit vermoeden proberen we een strategie te formuleren voor de eerste speler bij de (6, 10)-reep. Breek de chocolade zo dat je een vierkant van 6 bij 6 aan de tegenspeler geeft. Wat de tegenspeler daarna ook doet, maak er telkens weer een vierkant van. Deze strategie werkt: de tegenspeler krijgt telkens een vierkant en kan hier dus nooit een vierkant van maken. De eerste speler krijgt dus telkens een rechthoek en kan er wel telkens een vierkant van maken. Vermits de vierkanten die de tegenspeler krijgt, steeds kleiner worden, komt er zeker een moment waarop dit een vierkant van 1 bij 1 is. Achteraf gezien bleek de eerste herformulering nuttig om een patroon te herkennen, maar hebben we de tweede herformulering niet gebruikt. Michel
Michel Roelens, Wie niet zoekt, niet vindt.
17
BIJLAGE 2 BESPREKING UIT UITWISKELING 31/1 (WINTER 2015 – AVANT-PREMIÈRE)
Michel Roelens, Wie niet zoekt, niet vindt.
18
Michel Roelens, Wie niet zoekt, niet vindt.
19
Michel Roelens, Wie niet zoekt, niet vindt.
20
BIBLIOGRAFIE Jacobs, S., Op de Beeck, R., Willems, J. (2005), Problem solving. Uitwiskeling 22/1 Pólya, G. (1966). Let us teach guessing. MAA Video Classics number 1, The Mathematical Association of America, 1966, http://vimeo.com/48768091, besproken in UW 31/1 Pólya, G. (1990). How to solve it. Princeton University Press Posamentier, A.S., Krulik, S. (2008). Problem solving strategies for efficient and elegant solutions. Grades 6-12. A resource for the mathematics teacher. Corwin Press, Thousand Oaks, California, 2008, 260 pp., ISBN 976-14129-5970-4, besproken in UW 29/3 Schoenfeld, A. (1985) Mathematical problem solving. Orlando, Academic Press Tao, T. (2006). Solving mathematical problems. A personal perspective. Oxford University Press, Oxford / New York, 2006, ISBN 978-0-19-920560-8, besproken in UW 24/3 Van Leemput, G. e.a. (1991), Problemen oplossen in de wiskundeles. Uitwiskeling 8/1
Michel Roelens, Wie niet zoekt, niet vindt.
21
