Routes in een drie dimensionaal rooster

Wiskunde A1 - Praktische Opdracht Hoofdstuk 2
1. Inleiding
We hebben de opdracht gekregen een praktische opdracht te doen voor wiskunde. We hebben gekozen voor: ‘routes in een drie dimensionaal rooster’ (VWO 1, opdracht 4, blz. 95). De bedoeling is om een manier te bedenken om het aantal kortste routes in een drie dimensionaal rooster te berekenen. Het leek ons wel een interessante opdracht, een uitdaging en een leuke aanvulling bij het hoofdstuk. 2. Plan van aanpak
1. Hoofd- en deelvragen bedenken. (30 min) 2. Eventuele aanvullende informatie zoeken (internet en bibliotheek) (60 min) 3. Drie dimensionale driehoek van Pascal maken (ter verduidelijking). (120 min) 4. Logica ontdekken in de (nagebouwde) driehoek van Pascal, en daarvoor een formule opstellen. (120 min) 5. Met behulp van formule een formule opstellen voor het aantal kortste routes in een drie dimensionaal rooster. (60 min) 6. Toepassingen zoeken voor het aantal kortste routes in een rooster. (30 min) 7. Verslag in het net afmaken. (120 min) 3. Hoofd- en deelvragen

Hoofdvraag: Wat is de manier om het aantal kortste routes in een drie dimensionaal rooster te bereken? Deelvragen: 1. Wat houdt de driehoek van Pascal in? 2. Wat is het verband tussen het aantal kortste routes in een drie dimensionaal en de driehoek van Pascal? 3. Hoe ziet de drie dimensionale versie van de driehoek van Pascal eruit? 4. Wat is het verband tussen het binomium van Newton en de drie dimensionale versie van de driehoek van Pascal? 5. Wat is het verband tussen de drie dimensionale versie van de driehoek van Pascal en de kortste routes in een drie dimensionaal rooster? 6. Zijn er toepassingen in de praktijk met de kortste routes in een drie dimensionaal? Hypothese
We denken dat de formule om het aantal kortste routes in een drie dimensionaal rooster lijkt op de manier voor het aantal kortste routes in een rooster er komt waarschijnlijk nog een factor bij, omdat je nu ook de keuze hebt om omhoog te gaan (in een rooster: links of rechts, in een drie dimensionaal rooster: links of rechts of omhoog) 4. Tijdsschema
Week Te verrichten activiteit verwachte tijdsduur
12/13 informatie verzamelen, opvragen 0,5 uur
13 maken 3d versie van driehoek van Pascal 2 uur
13/14/15 beantwoorden deelvragen 5 uur
15 hoofdvraag beantwoorden 0,5 uur
16 verslag in het net maken 2 uur
5.1 Wat houdt de driehoek van Pascal in? Dit is de driehoek van Pascal: Elk getal krijg je door de twee getallen die er schuin boven staan, bij elkaar op te tellen. De driehoek is genoemd naar Blaise Pascal (1623-1662) als waardering voor zijn grote bijdrage aan de kansrekening en combinatoriek. De driehoek van Pascal was al bekent bij de Chinezen rond 1300. Pascal was dus niet de ontdekker van de driehoek die zijn naam draagt. Elk getal in de driehoek van Pascal geeft het aantal routes om vanuit de top op die plaats te komen. De getallen op de n-de rij zijn: n , n , n , n , . . ., n 0 1 2 3 n
5.2 Wat is het verband tussen de driehoek van Pascal en de kortste routes in een twee dimensionaal rooster? Hierboven zie je de driehoek van Pascal nog een keer met daarin een rooster van 2 x 2. Als je het rooster zo in de driehoek van Pascal legt zie je dat het aantal kortste routes van a naar b 6 is. Dit kun je schrijven als 4 (zie: Wat houdt de driehoek van Pascal in?) Hoe bereken je dan het aantal kortste routes in een rooster? Als voorbeeld neem ik het rooster hieronder: In een rooster is het aantal kortste routes, van A naar B de uitkomst van de combinatie: nCr

n = 8 want je maakt 8 keer de keuze links of rechts (en ligt in de driehoek van Pascal op de 8e rij). r = 4 want je kiest 4 keer links (op de 4e plaats van de 8e rij). Het aantal kortste routes in een rooster is dus: aantal keuzes: n aantal keuzes opzij: r
5.3 Hoe ziet de drie dimensionale versie van de driehoek van Pascal eruit? Om het te verduidelijken hebben we de driehoek van Pascal nagebouwd. Hieronder zie je een bouwtekening hoe we het aangepakt hebben. We hebben de drie dimensionale versie van de driehoek van Pascal 4 lagen hoog gemaakt en met 4 vlakken (3 zijvlakken en een ondervlak). De voor en zijaanzichten zien er gewoon hetzelfde uit als de driehoek van Pascal. De buitenste getallen van de lagen zijn nog hetzelfde als de 2d driehoek van Pascal omdat je daar nog niet met 3d te maken hebt. Een bovenaanzicht van de lagen: Op de bovenkant van de kubusjes hebben we het aantal kortste routes naar dat punt geschreven (optellen van de 3 punten die in de laag erboven liggen). Aan de zijkanten staan de nummers van de gewone driehoek van Pascal. Als je de kubusjes van een laag onderling verbindt en je zet ze op elkaar heb je de driehoek van Pascal in het drie dimensionaal. Om te kijken of het klopte hebben we bij een aantal kubussen systematisch nageteld: Afmeting van kubus Aantal keuzes Aantal kortste routes
1 x 1 x 1 3 6
1 x 1 x 2 4 12
1 x 1 x 3 5 20
1 x 2 x 2 5 30
Afmeting van kubus is lengte maal breedte maal hoogte (voor de afmeting van de ribbe van een kubus neem je voor het gemak 1) Aantal keuzes is het aantal ribben die je op de kortste route langs moet. De waarden van de eerste kolom opgeteld. Deze tabel klopt dus met de driehoek van Pascal. Bij een kubus van 1 x 1 x 1 moet je op de derde laag zijn (omdat er 3 keuzes zijn), in het midden (je moet 1 stap opzij) van de derde laag staat ook 6, dit klopt dus. Ook kun je de punten in de drie dimensionale versie van de driehoek van Pascal liggen berekenen. Deze logica hebben we gevonden aan de hand van de 3d versie die we hadden gemaakt. Uit de bovenstaande afbeeldingen heb ik een paar dingen afgeleid: 1. Behalve de factor nCr is er nog een factor aanwezig om de binnenste getallen van de 3d driehoek van Pascal uit te rekenen. 2. Je zult die factor moeten vermenigvuldigen men nCr want de binnenste getallen zijn steeds wel deelbaar door de nCr van de rij waar ze in horen
3. Deze factor bestaat volgens mij ook uit een combinatie want pas in de tweede rij van een laag (vanaf laag 3) heb je te maken met een 3d getal en pas vanaf de vierde laag heb je meerdere verschillende 3d getallen. 4. Al deze gegevens heb ik in een tabel gezet: nCr b g g volgt uit
3C2 6 2 2C1
4C2 12 2 2C1
4C3 12 3 3C1 en 3C2
5C2 20 2 2C1
5C3 30 3 3C1 en 3C2
5C4 20 4 4C1 en 4C3
5C4 30 6 4C2 en 6C1 en 6C5
b = de getallen die in de r de rij voorkomen en niet gelijk zijn aan nCr

g = het getal waarmee je nCr moet vermenigvuldigen om b te krijgen
g volgt uit = de combinatie waaruit je g kunt krijgen
Vooral aan de laatste kolom hadden we veel om de formule te bepalen. De formule die we gevonden hebben is: nCr x rCk
nCr = de combinatie van de getallen aan de rand (op de n-de laag in 3d versie zijn dat de combinaties op de n-de rij in de 2d versie) k = k-de plaats in een rij van een laag van de 3d versie van Pascal (begint ook bij 0): als voorbeeld de 3e laag: wil je dan bijvoorbeeld de waarde weten van het getal op
de derde rij op de tweede plaats moet je uitrekenen: nCr x nCk = 3C2 x 2C1 = 6
5.4 Wat is het verband tussen het binomium van Newton en de drie dimensionale versie van de driehoek van Pascal? De som van de getallen op een bepaalde rij in de 2d driehoek van Pascal is 2n . Dit is afgeleid van het binomuim van Newton: (x + y)0 = 1 (x + y)1 = 1x + 1y (x + y)2 = 1x2 + 2xy + 1y2 (x + y)3 = 1x3 + 3x2y + 3xy2 + 1y3 , enzovoort
Als je dus het aantal kortste routes wil weten van het punt (0,0) naar (1,2) moet je een keer in de z richting en twee keer in de y richting. Dit kan op drie manieren: xyy, yxy en yyx. Dit is precies in het binomium van Newton: x2y in (x + y)3. In een drie dimensionaal rooster heb je ook nog een andere richten, laten we die de z richting noemen. Het is dus logisch om dan te kijken naar de machten: (x + y + z). Als je dan het kortste aantal routes wil weten van het punt (0,0,0) naar het punt (1,2,3) krijg je in het binomium van Newton dus xy2z3 in (x + y + z)3. Als voor de som op een bepaalde rij in de 2d driehoek van Pascal geldt: 2n moet er dus ook een manier zijn om dat te doen in de 3d versie. Bij de formule 2n is aangenomen dat x en y 1 waren: (1 + 1)n = 2n. Als je dit toepast op de 3d versie krijg je: (1 + 1 + 1)n = 3n. Maar klopt dit wel? Op de derde rij van de 3d versie van de driehoek van Pascal staan de volgende getallen: 1 3 3 1
3 6 3
3 3 1
Die zijn bij elkaar opgeteld: 27. Reken je dit na met de som van de getallen op de n-de rij = 3n klopt dit want 33 = 27
5.5 Wat is het verband tussen de drie dimensionale versie van de driehoek van Pascal en de kortste routes in een drie dimensionaal rooster? Ook in een 3d rooster geld de 3d driehoek van Pascal: zie plaatje hieronder
Hier zie je dus dat je in een 3d rooster ook weer dezelfde driehoek van Pascal met dezelfde aantal punten tegenkomt. En werkt dus op dezelfde manier als het verband tussen de 2d versie van de driehoek van Pascal en routes in een 2d rooster. 5.6 Zijn er toepassingen in de praktijk met de kortste routes in een drie dimensionaal? In de praktijk zijn er meestal wel mogelijkheden met routes in een 3d rooster, maar meestal is het aantal kortste routes niet van belang. Een voorbeeld van een toepassing is bijvoorbeeld het aantal kortste routes naar een branduitgang in een flat/kantoorgebouw. Je zou die uit kunnen werken voor een soort calamiteiten plan. In de praktijk kom je meestal geen rooster tegen met allemaal gelijke hokjes. Dan is het aantal kortste routes moeilijker te berekenen. Je moet het eerst vereenvoudigen tot een rooster: Stap 1. Voor de kortste route van A naar B moet je over de schuine lijn. Want de schuine zijde van een rechthoekige driehoek is altijd korter dan de twee rechthoekszijden samen. Dus de paarse lijnen vervallen dan bij het bereken van de kortste routes. Stap 2. Je kunt de oranje lijn vlak voor b, gelijk maken met de andere lijnen in het rooster, omdat dit voor het aantal kortste routes niet uit maakt. Het vereenvoudigde model ziet er dus zo uit. De schuine lijn is voor het gemak weggelaten omdat daar toch maar 1 keuze mogelijkheid is. Stap 3. Je kunt nu het aantal kortste routes van a naar b (zonder de blauwe lijnstukken) bepalen. Dat is (6C4) = 15. Stap 4. Ga na hoeveel van de kortste routes 2 maal langs een keuzepunt komen met een blauwe lijn. Want alleen als ze er 2 maal langs komen is er een kortste route over het blauwe gedeelte mogelijk. In dit geval is dat er 1. Stap 5. Bereken het aantal kortste routes in het blauwe gedeelte. Dat is (3C2)=3. Waarvan er 1 helemaal over de zwarte lijnen gaat. Die is dus al meegerekend in stap 3. Dus komen er 3-1=2 nieuwe aantal kortste routes bij. Stap 6. Het aantal kortste routes van stap 3 + aantal kortste routes van stap 5 =15+2=17
Als je iets dergelijks tegenkomt in het driedimensionaal moet je het vereenvoudigen tot een 3d-rooster. Bij een 3d-rooster kom je ook ongelijke hokjes tegen. Om dan het aantal kortste routes te berekenen moet je dezelfde stappen langs gaan als bij een normaal(2d) rooster.  Eerst kijken of er een (of meerdere)schuine zijden in zitten. Als dat zo is, moet eerst het aantal kortste routes van A tot de schuine zijde berekent worden. Dat moet vermenigvuldigt worden met het aantal kortste routes van de schuine zijde tot B. De uitkomsten per schuine zijde tel je bij elkaar op. Let op! Als er meerdere schuine zijden in dezelfde kortste route liggen. Moet je maar net het aantal kortste routes van A via de schuine zijden naar B bereken. Want de schuine zijde is altijd korter dan 2 rechte zijden.  Als er hokjes zijn die onderverdeeld zijn in kleinere hokjes, (punt X), bereken je het aantal kortste routes via X. Dit vermenigvuldig je met het aantal kortste routes in het hokje. Dit antwoord tel je op bij de eerder gevonden aantal kortste routes.  Vervolgens kun je met de formule die in het hoofdstuk hierna wordt behandeld het aantal kortste routes berekenen

6. Hoe bereken je het aantal kortste routes in een drie dimensionaal rooster? Hoe bereken je nu het aantal kortste routes in een 3d rooster?  Bereken het aantal kortste routes op het bovenvlak.  Dit moet vermenigvuldigd worden met een derde factor. lengte x breedte x hoogte aantal kortste routes op bovenvlak Totaal aantal kortste routes Verband kolom 2 en 3
1x1x1 2 6 x 3 3 x 1
2x1x1 3 12 x 4 4 x 1
3x1x1 4 20 x 5 5 x 1
2x2x1 6 30 x 5 5 x 1  Laatste kolom is het aantal kruispunten die je op het bovenvlak tegen komt x het aantal lagen. a a  Controle 1. b b 1 = 2
Formule: (n C r) bovenvlak x kruispunten op bovenvlak x hoogte
1: (2 C 1) X 3 X 2=12
2: (3 C 1) X 4 X 1=12
Controle 1. klopt  Controle 2. a a b b 3 = 4
3: (2 C 1) X 3 X 3=18
4: (4 C 1) X 5 X 1=20
Controle 2. klopt niet.  Conclusie die we daaruit trokken: Het aantal kortste routes op het bovenvlak moet wel vermenigvuldig worden met een 2e factor. De hoogte moet in de 2e factor komen. Maar de hoogte moet niet vermenigvuldigd worden met een ander getal. Oplossing: De hoogte als combinatie schrijven van het totaal aantal stappen.  Nieuwe formule: (n C r) bovenvlak x (n2 C r2) n2 = totaal aantal stappen van a naar b
r2 = aantal lagen (hoogte)  Controle

Zie figuren vorige controles
Formule: (n C r) bovenvlak X (n2 C r2) 1: (2 C 1) X (4 C 2)=12
2: (3 C 1) X (4 C 1)=12
3: (2 C 1) X (5 C 3)=20
4: (4 C 1) X (5 C 1)=20  Door nog meer controles uit te voeren bleek dat deze formule overal klopte. Ook bij een 2d rooster want dan vermenigvuldig je het bovenvlak met (n2 C o)=1. Opmerking: Als er bedoeld wordt n boven r, hebben we dat geschreven als (n C r) 7. Evaluatie
De hele praktische opdracht is best goed gegaan. Het was alleen een beetje verwarrend dat we het op een duur met ons drieën mochten doen, maar dat scheelde wel een hoop werk. Sommige dingen hebben we nu dus eigenlijk wel dubbel gedaan. We hebben veel (misschien wel te veel) tijd gestoken in het maken van de 3d versie van Pascal, eerst wisten we de vorm niet precies en later kwamen we erachter dat we de 3d versie eigenlijk helemaal niet hadden hoeven maken omdat je het op papier duidelijk kon aangeven. Ook is het plan van aanpak en het tijdsschema niet zo goed gevolgd, omdat het wel even duurden voor we de 3d versie van Pascal bedacht en afhadden, zijn we al verder gegaan met het ontdekken van een formule in een 3d rooster zonder dat we de 3d versie van Pascal als hulpmiddel gebruikten. Gelukkig hebben we goede resultaten en alle deelvragen kunnen beantwoorden. We vinden het wel leuk dat we niet alles uit boekjes hebben, omdat je die niet zo snel te pakken krijgt, maar zelf achter de meeste dingen zijn gekomen door uit te proberen en dergelijke. We vonden het alle drie heel leuk en hebben er veel van geleerd. 8.1 Logboek Denise
Datum Activiteit sbu Opmerkingen
20 – 3 – 00 hoofd- + deelvragen bedacht 0,25 goedgekeurd
20 – 3 – 00 Plan van aanpak en tijdsschema gemaakt 0,25 goedgekeurd
27 – 3 – 00 gezocht naar formule 1,5
28 – 3 – 00 schematische tekeningen met cijfers gemaakt 1
29 – 3 – 00 bouwopzet gemaakt. 1 Eerst had ik een foute gemaakt
29 – 3 – 00 3d driehoek gebouwd 2 duurde lang
29 – 3 – 00 gezocht naar formule 2 heel moeilijk, steeds als je denkt dat je de formule hebt klopt er weer iets niet. 30 – 3 – 00 gezocht naar formule 2
3 – 4 – 00 gezocht naar formule, formule gevonden. 1,5

Totaal: 11,6
8.2 Logboek Willeke
datum activiteit sbu opmerkingen
27 – 3 - 00 werkplan, inleiding, hoofd- en deelvragen gemaakt
begonnen met de beantwoording deelvraag 1 1
28 – 3 – 00 informatie op internet gezocht 0,5 ik heb wel iets gevonden, maar het gaf geen extra informatie
29 – 3 - 00 met elkaar de mogelijke oplossingen besproken 0,7
3 – 4 - 00 drie dimensionale versie van Pascal gemaakt 1,5 In het begin wisten we nog niet precies hoe de 3d versie van de 3-hoek van Pascal eruit zag, dat werkte een beetje verwarrend. 4 – 4 - 00 verband tussen de driehoek van Pascal en kortste routes in een drie dimensionaal rooster uitgewerkt 0,5 Je doet er best lang over om alles op de computer uit te werken, vooral de schema’s
7 - 4 - 00 geprobeerd logica in de 3d versie te vinden (formule) 3 met de ‘uitvindingen’ van ons drieën zijn we eruit gekomen. 14 – 4 - 00 verband tussen de 3d versie en binomium van Newton uitgewerkt. Verder aan het verslag gewerkt. 2
15 - 4 - 00 verder aan verslag gewerkt 1

17 – 4 - 00 verslag afgemaakt 1,5
Totaal 11,7
8.3 Logboek Windy
Datum Activiteit Sbu Opmerkingen
Week 12 Werkplan gemaakt 0,5 goedgekeurd
Week 13 Naar mogelijkheden voor oplossingen gezocht 2,5
Week 13 Deelvraag 2 en 3 beantwoordt 1
Week 13 Bouwplan 3d driehoek van Pascal gemaakt 0,5
Week 14 Driehoek van Pascal in 3d gebouwd 1,5
Week 14 Ideeën van iedereen met elkaar vergeleken 0,7
Week 14 Informatie aangevraagd bij TU 0,5
Week 15 Naar formule gezocht 3,4 formule gevonden voor kortste routes in 3d rooster, klopt ook met de formule die we al hadden gevonden in de 3d driehoek van Pascal. Week 16 Aan deelvraag 6 gewerkt 1
Totaal sbu 11,6
9. Bronnen  Getal en Ruimte, Wiskunde voor de tweede fase, VWO1. Eerste druk, tweede oplaag 1998.