WisFaq!

Aantal mogelijke routes met verboden pad

De opdracht waar ik een vraag over heb bestaat uit twee onderdelen. Volgens mij heb ik deel (a) goed beantwoord:
(a) In een coördinatensysteem ligt een punt A (1,2) en een punt B (17,12). Bereken het aantal mogelijk wegen van punt A naar B. Alleen stapjes met een lengte van 1 zijn toegestaan. Je mag enkel omhoog en naar rechts stapjes zetten.

Ik heb hier de formule voor combinaties gebruikt en had het volgende getal als uitkomst: 5311735.

Maar nu zit ik dus vast op deelvraag (b):
(b) We hebben hetzelfde coördinatensysteem als in (a) (en dezelfde regels qua stapjes zetten), maar nu zijn een aantal stukjes verboden om overheen te gaan. We hebben een punt P (10,6), Q (10,7), R (11,7) en S (12,7). De segmenten PQ, QR en RS zijn nu verboden om te gebruiken in de route van A naar B. Hoeveel verschillende routes zijn er nu mogelijk?

Ik was van plan om te berekenen hoeveel wegen er door PQ, QR en RS gaan en daarmee het totaal (5311735) te verminderen. Maar ik heb geen idee hoe ik dat zou moeten aanpakken...

Marja
20-5-2019

Antwoord

Bereken eerst op hoeveel manieren je van A in P kunt geraken. Vermenigvuldig dit aantal met het aantal manieren waarop je van P in Q kunt geraken, dat is maar 1, dus deze stap kun je in dit geval laten vallen. Vermenigvuldig dit aantal dan weer met het aantal manieren waarop je van Q in B kunt geraken. Je hebt nu alle wegen die het segment PQ gebruiken.

Doe nu hetzelfde voor QR en RS.

Let op. Je hebt nu bepaalde wegen dubbel geteld, namelijk degen die door P,Q, en R gaan, door P,R en S, door P,Q en S en door Q,R en S én je hebt ook de wegen die door PQR én S gaan driedubbel geteld. Je moet hier dus rekening mee houden, en deze wegen berekenen en er weer van aftrekken.

Hierna kun je pas het totale aantal verminderen met wat je hierboven had berekend.

Lukt het zo?

js2
20-5-2019