routes in een rooster


Routes tellen.	© h.hofstede (h.hofstede@hogeland.nl)

Hiernaast staat een plattegrond getekend. De vraag is: Hoeveel verschillende kortste routes lopen er van S (start) naar F(finish)?
Omdat het gaat om kortste routes moet elke stap van je route de goede kant op zijn, dus of naar rechts of naar boven. Twee mogelijke kortste routes zijn al aangegeven.

De systematische manier om dat aantal routes te tellen is de volgende:

schrijf bij elke kruising op hoeveel
manieren je er kunt komen vanaf S

Nou weet je dat natuurlijk niet van elke kruising, maar van de eerste twee wél: daar kun je op precies één manier vanaf S komen.
Dat staat in de figuur hiernaast weergegeven.
Omdat elke stap naar rechts en naar boven moet gaan (anders vind je niet een kortste route) kun je bij alle kruisingen op de onderrand en de linkerrand maar op één manier komen vanaf S. Dat geeft al:

Laten we nu een willekeurig punt P ergens in de plattegrond nemen. Zie de figuur hiernaast. Omdat elke stap naar rechts en omhoog moet zijn, weet je dat je om in P te komen via Q of R moet zijn gekomen.
Nu geldt:

Aantal routes van S naar P
= aantal routes via R + aantal routes via Q
= aantal routes van S naar R + aantal routes van S naar Q

conclusie:

Om het aantal routes naar een punt P te weten moet je de aantallen routes van de punten onder P en links van P bij elkaar optellen.

Aantal voor een kruispunt? Tel "van onder" en "van links" bij elkaar op!

Daarmee kunnen we alle kruisingen van een getal voorzien. Dat is hiernaast gebeurd. Een getal op een kruising is dus steeds de som van die eronder en die links ervan. Soms is maar één van beiden er, dan wordt het aantal routes dus automatisch daaraan gelijk.
De conclusie is dat er van S naar F in dit rooster 99 kortste routes zijn.

We kunnen nu ook in één keer aflezen dat bijvoorbeeld van die 99 routes er 38 via het punt P in de figuur erboven gaan, en dus 51 niet via P.

Bereken het aantal kortste routes van S naar F in de volgende roosters:

81, 45 en 25

Bereken het aantal kortste routes van S naar F in de volgende roosters:

18, 8 en 29

Hieronder zie je drie mini-schaakbordjes met in de linkerbovenhoek een schaakstuk (achtereenvolgens een pion, een toren en een dame). Je moet het schaakstuk naar rechtsonder verplaatsen, en je mag dat doen door zetten te gebruiken waarbij het stuk alleen naar rechts, naar onderen of schuin naar rechtsonder gaat.

• Een pion mag één vakje horizontaal, verticaal of diagonaal verplaatsen
• Een toren mag zoveel vakjes verplaatsen als je wilt, maar alleen horizontaal of diagonaal.
• Een dame mag zoveel vakjes als je wilt, horizontaal, verticaal of diagonaal.

Bereken voor elk geval hoeveel mogelijke zettenseries van linksboven naar rechtsonder leiden.

63, 106, 188

Regelmatige roosters

Soms zijn de roosters regelmatig en dan is al dat uitschrijven niet nodig. Neem het rooster van 3 × 5 hiernaast, waarin de aantallen routes met de hand zijn geteld. Er zijn 56 routes van S naar F.
Maar dat uitschrijven was helemaal niet nodig!
Bekijk één van die 56 routes, bijvoorbeeld de getekende rode route hiernaast. Deze route zou je kunnen omschrijven door RRBRBBRR waarbij R een stapje naar rechts betekent en B een stapje naar boven.

Maar: élke route bestaat uiteindelijk uit 5 stapjes naar rechts en 3 naar boven.

Het aantal routes is daarom gelijk aan het aantal rijtjes letters RRRRRBBB met 3 R's en 5 B's.
Hé! Dat is een ANAGRAM
En we weten al hoeveel er daarvan zijn: 8 nCr 5 = 56.

Een route is een anagram

Het rooster hiernaast kun je opsplitsen in twee regelmatige delen: van S naar A en daarna van A naar F.

Van S naar A is de route RRRBB en dat kan op 5 nCr 2 = 10 manieren
Van A naar F is de route RRRRBBB en dat kan op 7 nCr 4 = 35 manieren.

In totaal zijn er daarom 10 • 35 = 350 routes van S naar F.

Bereken het aantal kortste routes van S naar F in de volgende twee roosters:

90 en 112000

BORD VAN GALTON.

In de figuur hiernaast zie je een tekening van het bord van Galton. Er valt boven een knikker in en die rolt op de bovenste pin. De knikker heeft een even grote kans om naar links als om naar rechts te vallen. Vervolgens valt de knikker weer op de volgende pin, weer met een even grote kans om naar rechts of naar links te vallen. Zo zoekt de knikker zijn weg door het bord naar beneden om uiteindelijk in één van de vakjes A t.m. F te belanden.

Hoeveel routes zijn er naar A, B, C, D, E en F?

1,5,10,10,5,1

Op hoeveel manieren kun je het woord ROOSTER in de figuur hiernaast van boven naar beneden via de verbindingslijntjes lezen?

(examenvraagstuk)

Hiernaast zie je een plattegrond van paden rond een vijver. Een route van A naar B moet zo kort mogelijk zijn en mag niet buiten de paden leiden.

Bereken het aantal verschillende kortste routes van A naar B.

648

Een mier zit in punt A op een draadmodel van een kubus die 3 bij 3 bij 3 eenheden groot is. De kubus is gemaakt van allemaal kleinere kubusjes van 1 bij 1 bij 1.
Zie de figuur hieronder.
De mier gaat lopen naar punt B schuin er tegenover. Dat doet hij via de kortst mogelijke route, dus daarvoor moet hij over 9 ribben lopen.
Hoeveel verschillende mogelijke kortste routes zijn er voor de mier?

1680

examenvraagstuk HAVO, wiskunde A, 1991

Bij onderzoek naar intelligentie van ratten wordt soms gebruik gemaakt van een gangenstelsel, een zogenaamd T-labyrint. Hieronder zie je zo'n labyrint.

In elk van de verticaal getekende gangen zit een klapdeurtje, dat slechts in één richting kan worden gepasseerd. Dat verhindert dat een rat terug naar "boven" kan lopen.
Een rat kan langs een groot aantal routes van ingang naar uitgang lopen. In de figuur is een voorbeeld van een route getekend. Twee routes van ingang naar uitgang worden als gelijk beschouwd als dezelfde serie klapdeurtjes wordt gepasseerd.

Hoeveel verschillende routes zijn er van ingang naar uitgang?

10.

Een voetbalwedstrijd is geëindigd in de stand 4-2.

Hoeveel verschillende scoreverlopen zijn er die deze eindstand opleveren?

Hoeveel mogelijke scoreverlopen zijn er die deze eindstand opleveren en waarbij het bij rust 2-1 was?

Leg uit hoe je zo'n scoreverloop kunt voorstellen door een route in een rooster.