Hallo,
Ik moet een probleem oplossen die ik niet zo goed begrijp. Ik dacht dat ik het begreep maar achteraf liep ik vast in mijn eigen gedachten. Kan iemand me misschien helpen?
Het probleem:
In een rij staan n personen achter elkaar die alle verschillend van lengte zijn. Er loopt iemand langs de rij en haalt de eerste persoon uit de rij; hij vervangt deze zodra hij een langer iemand in de rij tegenkomt. Dit blijft hij doen tijdens het lopen langs de rij.
Hoeveel mensen heeft hij naar verwachting gemiddeld genomen uit de rij gehaald als hij aan het eind van de rij is gekomen?
Laatste berichten
-
20:14
Aardlek-schakelaar 2
-
19:55
wig 9
-
15:56
Programmeren met vectoren 6
-
14:53
Straatklok loopt 5 minuten voor 12
-
23:12
speciale rel. theorie 10
-
22:36
Gravity and gravitation 4
-
22:24
[scheikunde] vraag Chemie - wat is de oplossing? 10
-
25 apr
Bruine vlekken op treinaanwijzerbord 10
-
25 apr
Vogels in de stad zijn goede klussers 2
-
25 apr
Rood laserlicht 3
-
25 apr
Herleiden afmetingen vanaf een foto 21
-
25 apr
[wiskunde] Prijs Product per KG; Alternatief Inzicht 3
-
25 apr
do-re-mi-fa-so vliegtuigen 9
-
25 apr
geen minkowski-ruimte toch? Doe ik dit nou fout? 17
-
25 apr
[natuurkunde] kroon van koning op Syracuse 10
-
25 apr
2013 – Augustus Vraag 3 3
-
24 apr
Vraag 2009 Juli Vraag 5 5
-
24 apr
positie 2
-
24 apr
Schroefdraad berekening 8
-
24 apr
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Het tellen van mensen met willekeurige lengtes
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 5.679
Re: Het tellen van mensen met willekeurige lengtes
Best lastig, geen middelbare school vraag neem ik aan?
Volgens mij is het
Volgens mij is het
\(\sum_{k=1}^n {n choose k}\frac{(-1)^k}{k}\)
In theory, there's no difference between theory and practice. In practice, there is.
Re: Het tellen van mensen met willekeurige lengtes
Ik begrijp het probleem niet.
Vb. een rijtje met lengtes 7, 2, 4, 3, 8, 5
Wordt dat eerst
8, 2, 4 ,3, 7, 5
dan
8, 4, 2, 3, 7, 5
dan
8, 4, 3, 2, 7, 5
dan
8, 4, 3, 7, 2, 5
en dan
8, 4, 3, 7, 5, 2 ?
Vb. een rijtje met lengtes 7, 2, 4, 3, 8, 5
Wordt dat eerst
8, 2, 4 ,3, 7, 5
dan
8, 4, 2, 3, 7, 5
dan
8, 4, 3, 2, 7, 5
dan
8, 4, 3, 7, 2, 5
en dan
8, 4, 3, 7, 5, 2 ?
-
- Berichten: 5.679
Re: Het tellen van mensen met willekeurige lengtes
Voorbeeld: n=8, beginsituatie is 3,1,5,4,2,6,8,7 waarbij 1 de kortste is en 8 de langste.
In het begin wordt 3 (de voorste) eruit gehaald, dus heb je 31542687.
Je neemt nr 3 langs 1 en verwisselt hem dan met 5, dus heb je 13542687
5 gaat voorbij 4 en 2 en wordt verwisseld met 6: 13425687
6 wordt verwisseld met 8: 13425687
8 gaat voorbij 7, en klaar, eindsituatie: 13425678
Je hebt nu in totaal vier keer iemand uit de rij gehaald.
De vraag abstracter geformuleerd: als je een willekeurige permutatie van {1,...,n} van links naar rechts afloopt, hoe vaak verwacht je dan een groter getal tegen te komen dan het maximum wat je tot dan toe bent tegengekomen (en als je nog geen getal bent tegengekomen is je maximum 0 of -
, met andere woorden het eerste getal geldt altijd als nieuw maximum).
Nog een kleine wijziging op mijn eerste antwoord:
In het begin wordt 3 (de voorste) eruit gehaald, dus heb je 31542687.
Je neemt nr 3 langs 1 en verwisselt hem dan met 5, dus heb je 13542687
5 gaat voorbij 4 en 2 en wordt verwisseld met 6: 13425687
6 wordt verwisseld met 8: 13425687
8 gaat voorbij 7, en klaar, eindsituatie: 13425678
Je hebt nu in totaal vier keer iemand uit de rij gehaald.
De vraag abstracter geformuleerd: als je een willekeurige permutatie van {1,...,n} van links naar rechts afloopt, hoe vaak verwacht je dan een groter getal tegen te komen dan het maximum wat je tot dan toe bent tegengekomen (en als je nog geen getal bent tegengekomen is je maximum 0 of -
, met andere woorden het eerste getal geldt altijd als nieuw maximum).Nog een kleine wijziging op mijn eerste antwoord:
Minnetje vergeten, moet zijn:Volgens mij is het\(\sum_{k=1}^n {n choose k}\frac{(-1)^k}{k}\)
\(\sum_{k=1}^n {n choose k}\frac{(-1)^k}{-k}\)
In theory, there's no difference between theory and practice. In practice, there is.
-
- Berichten: 7
Re: Het tellen van mensen met willekeurige lengtes
Beste Rogier,
Het is mij nu wel duidelijk wat de bedoeling van deze opgave is. Het lukt mij wel om simpele voorbeelden uit te werken. Hoe moet ik dan nu verder?
Ik dacht het volgende misschien:
Ik moet eerst kijken het aantal mogelijkheden om de getallen te rangschikken. Bijvoorbeeld bij een rij van 5 getallen ; zeg {4,3,6,8,9} zijn het aantal mogelijkheden gelijk aan 5!.
Wat ik gemerkt heb is, dat niet alle mogelijkheden dezelfde aantal verwisselingen telt. Als alle getallen van klein naar groot op een rij staan dan heb je het maximaal aantal verwisselingen, dat gelijk is aan het aantal getallen in die rij. In mijn voorbeeld dus gelijk aan 5.
Is de bedoeling dat ik een simpele versie neem bijvoorbeeld n=2 , n=3 en n=4 en dan alle mogelijkheden opschrijf en dat ik dan per mogelijkheid ga opschrijven het aantal verwisselingen? en dan op zoek moet gaan naar een regelmaat? Ik weet niet.
Je hebt daarnaast ook een meetkundige (alternerende reeks) gegeven als oplossing. Ik snap niet hier je hieraan komt. Blijkbaar maak je gebruik van combinaties. Zou je mij uitleggen hoe je aan jou antwoord komt? Tenminste een aanwijzing?
Groetjes en bijvoorbaat bedankt!
JayCi
Het is mij nu wel duidelijk wat de bedoeling van deze opgave is. Het lukt mij wel om simpele voorbeelden uit te werken. Hoe moet ik dan nu verder?
Ik dacht het volgende misschien:
Ik moet eerst kijken het aantal mogelijkheden om de getallen te rangschikken. Bijvoorbeeld bij een rij van 5 getallen ; zeg {4,3,6,8,9} zijn het aantal mogelijkheden gelijk aan 5!.
Wat ik gemerkt heb is, dat niet alle mogelijkheden dezelfde aantal verwisselingen telt. Als alle getallen van klein naar groot op een rij staan dan heb je het maximaal aantal verwisselingen, dat gelijk is aan het aantal getallen in die rij. In mijn voorbeeld dus gelijk aan 5.
Is de bedoeling dat ik een simpele versie neem bijvoorbeeld n=2 , n=3 en n=4 en dan alle mogelijkheden opschrijf en dat ik dan per mogelijkheid ga opschrijven het aantal verwisselingen? en dan op zoek moet gaan naar een regelmaat? Ik weet niet.
Je hebt daarnaast ook een meetkundige (alternerende reeks) gegeven als oplossing. Ik snap niet hier je hieraan komt. Blijkbaar maak je gebruik van combinaties. Zou je mij uitleggen hoe je aan jou antwoord komt? Tenminste een aanwijzing?
Groetjes en bijvoorbaat bedankt!
JayCi
Rogier schreef:Voorbeeld: n=8, beginsituatie is 3,1,5,4,2,6,8,7 waarbij 1 de kortste is en 8 de langste.
In het begin wordt 3 (de voorste) eruit gehaald, dus heb je 31542687.
Je neemt nr 3 langs 1 en verwisselt hem dan met 5, dus heb je 13542687
5 gaat voorbij 4 en 2 en wordt verwisseld met 6: 13425687
6 wordt verwisseld met 8: 13425687
8 gaat voorbij 7, en klaar, eindsituatie: 13425678
Je hebt nu in totaal vier keer iemand uit de rij gehaald.
De vraag abstracter geformuleerd: als je een willekeurige permutatie van {1,...,n} van links naar rechts afloopt, hoe vaak verwacht je dan een groter getal tegen te komen dan het maximum wat je tot dan toe bent tegengekomen (en als je nog geen getal bent tegengekomen is je maximum 0 of -
Nog een kleine wijziging op mijn eerste antwoord:
Minnetje vergeten, moet zijn:Volgens mij is het\(\sum_{k=1}^n {n choose k}\frac{(-1)^k}{k}\)\(\sum_{k=1}^n {n choose k}\frac{(-1)^k}{-k}\)
-
- Berichten: 3.330
Re: Het tellen van mensen met willekeurige lengtes
Ik begrijp ook de formule niet. En zeker niet het voorkomen van die -tekens.
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
-
- Berichten: 7.068
Re: Het tellen van mensen met willekeurige lengtes
Notatie: \(E_n\) is de verwachtingswaarde van het aantal verwisselingen in een rij met n elementen. \(E_0 = 0\).
Stel dat de verwachtingswaarde bekend is voor rijen t/m (n-1) elementen. We gaan nu kijken naar rijen van n elementen. Dit doen we door een element toe te voegen dat groter is dan alle voorgaande (n-1) elementen. Dit nieuwe element kan op n posities komen. We bekijken de situatie dat het op positie k staat.
Het nieuwe element op positie k deelt de rij op in twee delen. In het gedeelte achter k zullen geen verwisselingen plaats vinden aangezien het grootste element dan al geweest is. In het gedeelte voor k kunnen wel verwisselingen plaatsvinden. De lengte van dit gedeelte is (k-1). De verwachtingswaarde voor het aantal verwisselingen in een gedeelte van lengte (k-1) is bekend verondersteld. Het is nu ook mogelijk om een uitspraak te doen over het aantal wisselingen in de rij van n elementen met het grootste element op positie k, namelijk \(E_{(k-1)}+1\). Het is belangrijk om je te realiseren dat het niet uitmaakt welke elementen in het gedeelte voor positie k voor de verwachtingswaarde. In de deelrij voor k is altijd een kleinste, op een na kleinste, enz. aanwezig.
Het aantal rijen dat mogelijk is met n elementen is \(n!\). Het aantal rijen met op de k-de positie het grootste element is \((n-1)!\). Voor de verwachtingswaarde van het aantal verwisselingen kunnen we nu dus zeggen:
Dit kunnen we ook schrijven als:
Stel dat de verwachtingswaarde bekend is voor rijen t/m (n-1) elementen. We gaan nu kijken naar rijen van n elementen. Dit doen we door een element toe te voegen dat groter is dan alle voorgaande (n-1) elementen. Dit nieuwe element kan op n posities komen. We bekijken de situatie dat het op positie k staat.
Het nieuwe element op positie k deelt de rij op in twee delen. In het gedeelte achter k zullen geen verwisselingen plaats vinden aangezien het grootste element dan al geweest is. In het gedeelte voor k kunnen wel verwisselingen plaatsvinden. De lengte van dit gedeelte is (k-1). De verwachtingswaarde voor het aantal verwisselingen in een gedeelte van lengte (k-1) is bekend verondersteld. Het is nu ook mogelijk om een uitspraak te doen over het aantal wisselingen in de rij van n elementen met het grootste element op positie k, namelijk \(E_{(k-1)}+1\). Het is belangrijk om je te realiseren dat het niet uitmaakt welke elementen in het gedeelte voor positie k voor de verwachtingswaarde. In de deelrij voor k is altijd een kleinste, op een na kleinste, enz. aanwezig.
Het aantal rijen dat mogelijk is met n elementen is \(n!\). Het aantal rijen met op de k-de positie het grootste element is \((n-1)!\). Voor de verwachtingswaarde van het aantal verwisselingen kunnen we nu dus zeggen:
\(E_n = \sum_{k=1}^{n} \frac{(n-1)!}{n!} (E_k + 1) = \sum_{k=1}^{n} \frac{1}{n} (E_k + 1) = 1 + \frac{\sum_{k=1}^{n} E_k}{n}\)
(In woorden: de som over alle k van de kans dat je een rij hebt met op positie k het grootste element maal het verwachte aantal wisselingen dat hoort bij zo'n rij.)Dit kunnen we ook schrijven als:
\(n E_n = n + \sum_{k=1}^{n} E_k = n + E_{(n-1)} + \sum_{k=1}^{n-1} E_k\)
Deze formule moet ook gelden voor n-1:\((n-1) E_{n-1} = n-1 + \sum_{k=1}^{n-1} E_k \rightarrow \sum_{k=1}^{n-1} E_k = (n-1) E_{n-1} - n+1\)
We gaan nu verder met hierboven:\(n E_n = n + E_{(n-1)} + \sum_{k=1}^{n-1} E_k = n + E_{(n-1)} + (n-1) E_{n-1} - n+1 = 1 + n E_{n-1}\)
dus:\(E_n = \frac{1}{n} + E_{n-1}\)
Hieruit is simpel te zien dat geldt:\(E_n = \sum_{k=1}^{n} \frac{1}{k}\)
Dit is volgens mij de vergelijking van een harmonisch getal en hiervoor is dacht ik geen expliciete formule.-
- Berichten: 5.679
Re: Het tellen van mensen met willekeurige lengtes
Verrek, uit jouw formule komt hetzelfde als de mijne, maar is een stuk simpeler
Ook naar mijn weten is er geen expliciete formule voor die som, tenzij je wat geknutsel met de Gamma functie als expliciet beschouwt.
Zie ook mathworld:
Ook naar mijn weten is er geen expliciete formule voor die som, tenzij je wat geknutsel met de Gamma functie als expliciet beschouwt.
Zie ook mathworld:
\(E_n = \gamma + \Psi_0(n+1)\)
In theory, there's no difference between theory and practice. In practice, there is.
-
- Berichten: 7
Re: Het tellen van mensen met willekeurige lengtes
Beste Rogier,
Ik heb gezien dat er twee oplossingen zijn:
En de harmonisch getal.
Hoe ik aan de harmonisch getal kom voor de verwachting is mij wel duidelijk. Ik heb voor enkele n-en , n=1, n=2, n=3 en n=4 uitgeschreven en heb daarin een volgorde ontdekt. en heb de harmonisch getal als vermoeden gegeven.
Om dit te controle ging ik het bewijzen.... en heb het ook kunnen doen ( het bewijs is geleverd).
Een ding snap ik niet hoe jij kwam aan jou formule met combinaties. Dit is in ieder geval een soort alternerende harmonische reeks met combinaties....
Leg me maar eens uit hoe je hieraan kwam.
Groetjes,
Jayci
Ik heb gezien dat er twee oplossingen zijn:
\(\sum_{k=1}^n {n choose k}\frac{(-1)^k}{-k}\)
Die jij geleverd heb.En de harmonisch getal.
Hoe ik aan de harmonisch getal kom voor de verwachting is mij wel duidelijk. Ik heb voor enkele n-en , n=1, n=2, n=3 en n=4 uitgeschreven en heb daarin een volgorde ontdekt. en heb de harmonisch getal als vermoeden gegeven.
Om dit te controle ging ik het bewijzen.... en heb het ook kunnen doen ( het bewijs is geleverd).
Een ding snap ik niet hoe jij kwam aan jou formule met combinaties. Dit is in ieder geval een soort alternerende harmonische reeks met combinaties....
Leg me maar eens uit hoe je hieraan kwam.
Groetjes,
Jayci
-
- Berichten: 7
Re: Het tellen van mensen met willekeurige lengtes
Beste Rogier,
Ik heb gezien dat er twee oplossingen zijn:
En de harmonisch getal.
Hoe ik aan de harmonisch getal kom voor de verwachting is mij wel duidelijk. Ik heb voor enkele n-en , n=1, n=2, n=3 en n=4 uitgeschreven en heb daarin een volgorde ontdekt. en heb de harmonisch getal als vermoeden gegeven.
Om dit te controle ging ik het bewijzen.... en heb het ook kunnen doen ( het bewijs is geleverd).
Een ding snap ik niet hoe jij kwam aan jou formule met combinaties. Dit is in ieder geval een soort alternerende harmonische reeks met combinaties....
Leg me maar eens uit hoe je hieraan kwam.
Groetjes,
Jayci
Ik heb gezien dat er twee oplossingen zijn:
\(\sum_{k=1}^n {n choose k}\frac{(-1)^k}{-k}\)
Die jij geleverd heb.En de harmonisch getal.
Hoe ik aan de harmonisch getal kom voor de verwachting is mij wel duidelijk. Ik heb voor enkele n-en , n=1, n=2, n=3 en n=4 uitgeschreven en heb daarin een volgorde ontdekt. en heb de harmonisch getal als vermoeden gegeven.
Om dit te controle ging ik het bewijzen.... en heb het ook kunnen doen ( het bewijs is geleverd).
Een ding snap ik niet hoe jij kwam aan jou formule met combinaties. Dit is in ieder geval een soort alternerende harmonische reeks met combinaties....
Leg me maar eens uit hoe je hieraan kwam.
Groetjes,
Jayci
