Ik heb het volgende vraagstuk:
Stel, in een uur heb je 40 vliegtuigen die op een vliegveld aankomen of vertrekken. Per saldo vertrekken er 20 vliegtuigen (DEP) en komen er tevens 20 vliegtuigen (ARR) aan. Ik wil graag weten hoe je berekent hoe vaak het gemiddeld voorkomt dat na een vertrek (DEP) een aankomst (ARR) volgt.
Ofwel ... ARR - ARR - {DEP - ARR }- DEP ....
Als het gelijkmatig verdeeld is, dan komt het 20 x voor, immers na elk vertrek volgt een aankomst, maar stel dat de aankomende en vertrekkende vliegtuigen willekeurig verdeeld zijn over het uur, hoe kan ik dan het gemiddeld aantal aankomende toestellen die direct na een vertrekkend toestel landen, berekenen?
Alvast bedankt voor de input
vraagstuk vliegtuigen
Re: vraagstuk vliegtuigen
Ik zou zo beginnen:Poes schreef:Ofwel ... ARR - ARR - {DEP - ARR }- DEP ....
In het hele sample zitten 40 vluchten. 20 zijn "ARR" en 20 zijn "DEP". Dus p(DEP) = 0.5 en p(ARR) = 0.5.
Splits in 2 groepen: DEP - ARR en niet-DEP - ARR en vertaal ze naar ballen.
DEP - ARR is een blauwe bal. kans = 0.5 * 0.5
ARR is een rode bal en DEP is een rode bal.
b = aantal blauwe ballen. r = aantal rode ballen.
2b + r = 40 en ga alle mogelijke waarden voor b na 0 <= b <= 20
Of kies om te beginnen een kleiner aantal vluchten dan 40, bijv. 4.
2b+r=4
dan 0 <= b <= 2
ik geef alle paren ARR-DEP schuin weer.
b=0: r = 4; geen paar van ARR-DEP (=blauw)
mogelijkheid:
DEP-DEP-ARR-ARR
b=1, r=2 een paar van ARR - DEP
mogelijkheden:
DEP-ARR-DEP-ARR
ARR-DEP-DEP-ARR
DEP-ARR-ARR-DEP
ARR-ARR-DEP-DEP
b=2, r=0
ARR-DEP-ARR-DEP
In totaal 6 mogelijke paren (4 boven 2) waarvan het gemiddelde 1 paar is.
Helpt dit je?
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)
(Raffiek Torreman)
Re: vraagstuk vliegtuigen
Goedenavond David
Bedankt voor de uitleg. Helder en goed te volgen. Voor kleine verzamelingen is het nog wel handmatig te bepalen, maar voor verzamelingen met 40 vluchten in het uur is het ondoenlijk dit voor b=1 tot b=20 te bepalen. Immers voor 40 vluchten heb je al 2^40 mogelijkheden.
Stel 2b + r = 40 en b=10 dan r=20 dus 10 paren van DEP - ARR in de verzameling maar hoe kan ik dan wiskundig bepalen hoeveel mogelijkheden in deze poel zitten zonder het volledig te moeten uitschrijven?
Nogmaals bedankt voor je raad.
Bedankt voor de uitleg. Helder en goed te volgen. Voor kleine verzamelingen is het nog wel handmatig te bepalen, maar voor verzamelingen met 40 vluchten in het uur is het ondoenlijk dit voor b=1 tot b=20 te bepalen. Immers voor 40 vluchten heb je al 2^40 mogelijkheden.
Stel 2b + r = 40 en b=10 dan r=20 dus 10 paren van DEP - ARR in de verzameling maar hoe kan ik dan wiskundig bepalen hoeveel mogelijkheden in deze poel zitten zonder het volledig te moeten uitschrijven?
Nogmaals bedankt voor je raad.
Re: vraagstuk vliegtuigen
Bekijk het probleem algemener:
noem:
m = totaal aantal vliegbewegingen (ARR of DEP)
d = aantal DEP
0 = ARR
1 = DEP
Elk rijtje bestaande uit m nullen en/of enen symboliseert nu de vluchtbewegingen.
Bijvoorbeeld:
als m=4 en d=2 zijn er 6 mogelijke rijtjes (zie ook David hierboven):
0011
0101
0110
1001
1010
1100
Je wilt weten hoe vaak de combinatie {DEP-ARR} = "10" in deze rijtjes voorkomt.
En specifiek voor het geval m=40 en d=20.
Handmatig uitschrijven is in dat geval inderdaad geen goede oplossing.
In plaats daarvan kunnen we de oplossing via recursiviteit proberen te vinden.
Definieer daarvoor eerst een aantal hulpfuncties:
s0(m,d) = het aantal rijtjes van lengte m met daarin d enen (=departures) dat start met '0'
s1(m,d) = het aantal rijtjes van lengte m met daarin d enen (=departures) dat start met '1'
s(m,d) = s0(m,d) + s1(m,d)
Omdat een rijtje altijd start met een nul of een 1 is
s(m,d) =
In bovenstaand voorbeeld:
s0(4,2)=3 (waarom?)
s1(4,2)=...?
s(4,2)=...?
t0(m,d) = het aantal keren dat "10" in de rijtjes startend met '0' van lengte m met d enen voorkomt
t1(m,d) = het aantal keren dat "10" in de rijtjes startend met '1' van lengte m met d enen voorkomt
t(m,d) = t0(m,d) + t1(m,d).
In bovenstaand voorbeeld:
t0(4,2)=2 (waarom?)
t1(4,2)=...?
t(4,2)=...?
Nu in het algemeen:
s0(m,d) kunnen we vinden door voor alle rijtjes van lengte (m-1) met d enen erin een nul te schrijven:
s0(m,d) = s0(m-1,d) + s1(m-1,d)
ofwel:
s0(m,d) = s(m-1,d).
t0(m,d) ontstaat evenzo door de som van het aantal 10-en te nemen:
t0(m,d) = t0(m-1,d) + t1(m-1,d) = t(m-1,d)
Voor t1(m,d) moeten we op de volgende 2 punten letten:
[1] we introduceren een nieuwe 1, dus we moeten uitgaan van rijtjes lengte (m-1) met (d-1) enen erin: als we voor die rijtjes een 1 plaatsen dan onstaan de rijtjes van lengte m met d enen erin.
[2] als een rijtje van lengte (m-1) start met een 1 en we schrijven er een 1 voor blijft het aantal 10-en gelijk aan het oorspronkelijke aantal,
maar als een rijtje van lengte (m-1) start met een 0 en we schrijven er een 1 voor dan introduceren we naast het oorspronkelijke aantal 10-en in dat rijtje een nieuwe 10. Het totale aantal nieuwe 10-en dat hierdoor ontstaat is dan dus gelijk aan het aantal rijtjes dat met nul begint. Dit aantal (= s0(m-1,d-1)) moeten we ook bij het totaal optellen:
t1(m,d) = t0(m-1,d-1) + t1(m-1,d-1) + s0(m-1,d-1) = t(m-1,d-1) + s0(m-1,d-1)
Nu is
t(m,d) = t0(m,d) + t1(m,d)
ofwel
t(m,d) = t(m-1,d) + t(m-1,d-1) + s0(m-1,d-1)
en omdat s0(m,d) = s(m-1,d):
t(m,d) = t(m-1,d) + t(m-1,d-1) + s(m-2,d-1)
ofwel:
t(m,d) = t(m-1,d) + t(m-1,d-1) +
We kunnen voor de binomiaalcoefficient
in een tabel a en b tegen elkaar uitzetten:
Dit levert de driehoek van Pascal:
Vul deze tabel s.v.p. zelf eens aan.
Vervolgens kan je een soortgelijke tabel maken voor t(m,d):
als m=1 hebben de rijtjes lengte 1, er zijn er daar 2 van:
"0" en "1"
in beide zit geen "10", dus de regel voor m=1 kunnen we invullen.
Als we vervolgens kijken naar alle rijtjes waarvoor d=0, dus alle rijtjes zonder 1 erin,
dan kan daar nooit een "10" in voorkomen, dus ook de kolom d=0 weten we:
Lukt het je om met de formule
t(m,d) = t(m-1,d) + t(m-1,d-1) +
en de eerste tabel (aCb) deze tweede tabel regel voor regel aan te vullen?
Dus om te beginnen:
t(2,1) = t(1,1) + t(1,0) +
etc
Je hebt nu de recursieve formule gevonden:
t(m,d) = t(m-1,d) + t(m-1,d-1) +
waarmee je alle waarden kan berekenen zonder alles uit te schrijven.
Alleen is dit voor t(40,20) ook nog een aardige klus.
Lukt het je om met volledige inductie te bewijzen dat
 = (m-1) \cdot {m-2 \choose d-1})
de gesloten oplossing is van bovenstaande recursieve formule?
Wat is nu t(4,2)?
Vergelijk dit met het resultaat van David hierboven.
En wat is nu t(40,20)?
Het gemiddelde dat je zoekt is tenslotte dit aantal gedeeld door het aantal mogelijke rijtjes:
 = \frac{ (m-1) \cdot {m-2 \choose d-1}}{{m \choose d}})
Kan je deze formule herleiden tot een simpele breuk?
En wat wordt deze breuk als d = m/2 ?
noem:
m = totaal aantal vliegbewegingen (ARR of DEP)
d = aantal DEP
0 = ARR
1 = DEP
Elk rijtje bestaande uit m nullen en/of enen symboliseert nu de vluchtbewegingen.
Bijvoorbeeld:
als m=4 en d=2 zijn er 6 mogelijke rijtjes (zie ook David hierboven):
0011
0101
0110
1001
1010
1100
Je wilt weten hoe vaak de combinatie {DEP-ARR} = "10" in deze rijtjes voorkomt.
En specifiek voor het geval m=40 en d=20.
Handmatig uitschrijven is in dat geval inderdaad geen goede oplossing.
In plaats daarvan kunnen we de oplossing via recursiviteit proberen te vinden.
Definieer daarvoor eerst een aantal hulpfuncties:
s0(m,d) = het aantal rijtjes van lengte m met daarin d enen (=departures) dat start met '0'
s1(m,d) = het aantal rijtjes van lengte m met daarin d enen (=departures) dat start met '1'
s(m,d) = s0(m,d) + s1(m,d)
Omdat een rijtje altijd start met een nul of een 1 is
s(m,d) =
In bovenstaand voorbeeld:
s0(4,2)=3 (waarom?)
s1(4,2)=...?
s(4,2)=...?
t0(m,d) = het aantal keren dat "10" in de rijtjes startend met '0' van lengte m met d enen voorkomt
t1(m,d) = het aantal keren dat "10" in de rijtjes startend met '1' van lengte m met d enen voorkomt
t(m,d) = t0(m,d) + t1(m,d).
In bovenstaand voorbeeld:
t0(4,2)=2 (waarom?)
t1(4,2)=...?
t(4,2)=...?
Nu in het algemeen:
s0(m,d) kunnen we vinden door voor alle rijtjes van lengte (m-1) met d enen erin een nul te schrijven:
s0(m,d) = s0(m-1,d) + s1(m-1,d)
ofwel:
s0(m,d) = s(m-1,d).
t0(m,d) ontstaat evenzo door de som van het aantal 10-en te nemen:
t0(m,d) = t0(m-1,d) + t1(m-1,d) = t(m-1,d)
Voor t1(m,d) moeten we op de volgende 2 punten letten:
[1] we introduceren een nieuwe 1, dus we moeten uitgaan van rijtjes lengte (m-1) met (d-1) enen erin: als we voor die rijtjes een 1 plaatsen dan onstaan de rijtjes van lengte m met d enen erin.
[2] als een rijtje van lengte (m-1) start met een 1 en we schrijven er een 1 voor blijft het aantal 10-en gelijk aan het oorspronkelijke aantal,
maar als een rijtje van lengte (m-1) start met een 0 en we schrijven er een 1 voor dan introduceren we naast het oorspronkelijke aantal 10-en in dat rijtje een nieuwe 10. Het totale aantal nieuwe 10-en dat hierdoor ontstaat is dan dus gelijk aan het aantal rijtjes dat met nul begint. Dit aantal (= s0(m-1,d-1)) moeten we ook bij het totaal optellen:
t1(m,d) = t0(m-1,d-1) + t1(m-1,d-1) + s0(m-1,d-1) = t(m-1,d-1) + s0(m-1,d-1)
Nu is
t(m,d) = t0(m,d) + t1(m,d)
ofwel
t(m,d) = t(m-1,d) + t(m-1,d-1) + s0(m-1,d-1)
en omdat s0(m,d) = s(m-1,d):
t(m,d) = t(m-1,d) + t(m-1,d-1) + s(m-2,d-1)
ofwel:
t(m,d) = t(m-1,d) + t(m-1,d-1) +
We kunnen voor de binomiaalcoefficient
Dit levert de driehoek van Pascal:
Code: Selecteer alles
aCb b=0 b=1 b=2 b=3 b=4 b=5 b=6
a=0 1 0 0 0 0 0 0
a=1 1 1 0 0 0 0 0
a=2 1 2 1 0 0 0 0
a=3 1 3 3 1 0 0 0
a=4 . . . . . . .
a=5 . . . . . . .
a=6 . . . . . . .Vervolgens kan je een soortgelijke tabel maken voor t(m,d):
als m=1 hebben de rijtjes lengte 1, er zijn er daar 2 van:
"0" en "1"
in beide zit geen "10", dus de regel voor m=1 kunnen we invullen.
Als we vervolgens kijken naar alle rijtjes waarvoor d=0, dus alle rijtjes zonder 1 erin,
dan kan daar nooit een "10" in voorkomen, dus ook de kolom d=0 weten we:
Code: Selecteer alles
t(m,d) d=0 d=1 d=2 d=3 d=4 d=5 d=6
m=1 0 0 0 0 0 0 0
m=2 0 . . . . . .
m=3 0 . . . . . .
m=4 0 . . . . . .
m=5 0 . . . . . .
m=6 0 . . . . . .t(m,d) = t(m-1,d) + t(m-1,d-1) +
en de eerste tabel (aCb) deze tweede tabel regel voor regel aan te vullen?
Dus om te beginnen:
t(2,1) = t(1,1) + t(1,0) +
etc
Je hebt nu de recursieve formule gevonden:
t(m,d) = t(m-1,d) + t(m-1,d-1) +
waarmee je alle waarden kan berekenen zonder alles uit te schrijven.
Alleen is dit voor t(40,20) ook nog een aardige klus.
Lukt het je om met volledige inductie te bewijzen dat
de gesloten oplossing is van bovenstaande recursieve formule?
Wat is nu t(4,2)?
Vergelijk dit met het resultaat van David hierboven.
En wat is nu t(40,20)?
Het gemiddelde dat je zoekt is tenslotte dit aantal gedeeld door het aantal mogelijke rijtjes:
Kan je deze formule herleiden tot een simpele breuk?
En wat wordt deze breuk als d = m/2 ?
Re: vraagstuk vliegtuigen
Ik ben zelf verder gegaan in het onderverdelen in aantal paren. Daarvoor heb ik de getallen van 1 t/m 63 in binaire code gezet en alle getallen waar de 1 drie keer in voorkomt eruit gepakt.
01 = paar DEP en ARR, blauw weergegeven
0 is DEP, rood weergegeven
1 is ARR, groen weergegeven.
voor 6 vluchten; 3 DEP en 3 ARR:
Totaal 6 nCr 3 = 20 onderverdelingen.
0 paren {DEP-ARR}:
"111000"
totaal: 1
1 paar {DEP-ARR}:
"000111"
"001110"
"011100"
"100011"
"100110"
"101100"
"110001"
"110010"
"110100"
totaal: 9
2 paren {DEP-ARR}:
"001011"
"001101"
"010011"
"010110"
"011001"
"011010"
"100101"
"101001"
"101010"
totaal: 9
3 paren {DEP-ARR}:
"010101"
totaal: 1
Wat je hierin kan zien is dat alle letters die geen paar vormen, in groepjes gescheiden door paren telkens een aantal, >= 0 aan 0, en daarna een aantal, >= 0, vormen. Zo is bijv. de enige rij vluchten die geen paren 01 heeft, dus 111000.
Daarmee probeer ik nu het volgende te bewijzen, en ben ik dus ook naar een tegenvoorbeeld op zoek.
Stel dat n het maximaal aantal paren is. en k <= n.
Dan is het aantal rijen met k paren gelijk aan het aantal rijen met n-k paren.
Ofwel: r(k) is het aantal rijen met k paren, dan r(k)=r(n-k)
Dit zou genoeg zijn om je gemiddelde te vinden.
Maar wat je verder nog kan zien is dat de aantallen rijen met dat een aantal paren, bijv. het aantal rijgen met 2 paren, is een kwadraat.
Je zou kunnen herkennen dat
Zodat:
Ofwel={n \choose k}^2)
i.i.g. voor n = 2 v 3 en dus k <= 3; k = 0, 1, 2, 3
Ik zal nog kijken hoe het zit voor n = 4 (4 arrivals en 4 departures)
Nog speculatiever (voor mij, maar misschien al uitsluitsel over):
Wat betekent dit voor het gemiddelde?
Ik kijk nog verder. Probeer jij te bewijzen dat
r(k)=r(n-k) met n is maximaal mogelijk aantal paren (aantal dep) en k is aantal paren?
01 = paar DEP en ARR, blauw weergegeven
0 is DEP, rood weergegeven
1 is ARR, groen weergegeven.
voor 6 vluchten; 3 DEP en 3 ARR:
Totaal 6 nCr 3 = 20 onderverdelingen.
0 paren {DEP-ARR}:
"111000"
totaal: 1
1 paar {DEP-ARR}:
"000111"
"001110"
"011100"
"100011"
"100110"
"101100"
"110001"
"110010"
"110100"
totaal: 9
2 paren {DEP-ARR}:
"001011"
"001101"
"010011"
"010110"
"011001"
"011010"
"100101"
"101001"
"101010"
totaal: 9
3 paren {DEP-ARR}:
"010101"
totaal: 1
Wat je hierin kan zien is dat alle letters die geen paar vormen, in groepjes gescheiden door paren telkens een aantal, >= 0 aan 0, en daarna een aantal, >= 0, vormen. Zo is bijv. de enige rij vluchten die geen paren 01 heeft, dus 111000.
Daarmee probeer ik nu het volgende te bewijzen, en ben ik dus ook naar een tegenvoorbeeld op zoek.
Stel dat n het maximaal aantal paren is. en k <= n.
Dan is het aantal rijen met k paren gelijk aan het aantal rijen met n-k paren.
Ofwel: r(k) is het aantal rijen met k paren, dan r(k)=r(n-k)
Dit zou genoeg zijn om je gemiddelde te vinden.
Maar wat je verder nog kan zien is dat de aantallen rijen met dat een aantal paren, bijv. het aantal rijgen met 2 paren, is een kwadraat.
Code: Selecteer alles
aantal paren: 0 |1 |2 |3
aantal rijen: 1 = 1^2 |9 = 3^2 |9 = 3^2 |1 = 1^2Zodat:
Ofwel
Ik zal nog kijken hoe het zit voor n = 4 (4 arrivals en 4 departures)
Nog speculatiever (voor mij, maar misschien al uitsluitsel over):
Ik kijk nog verder. Probeer jij te bewijzen dat
r(k)=r(n-k) met n is maximaal mogelijk aantal paren (aantal dep) en k is aantal paren?
Laatst gewijzigd door David op 10 sep 2011, 10:39, 1 keer totaal gewijzigd.
Reden: {DEP - ARR} - dank je, Arie
Reden: {DEP - ARR} - dank je, Arie
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)
(Raffiek Torreman)
Re: vraagstuk vliegtuigen
Dit is correct, zie bijvoorbeeld formule (8) op deze pagina:David schreef:Nog speculatiever (voor mij, maar misschien al uitsluitsel over):
http://en.wikipedia.org/wiki/Binomial_coefficient
PS: voor het eindresultaat maakt het niet uit, maar het gaat om het aantal paren
{DEP-ARR} = 10 (zie de eerste post van Poes).
Wellicht is het beter om deze combinatie aan te houden in onze redenaties.