Springen naar inhoud

Het tellen van mensen met willekeurige lengtes


  • Log in om te kunnen reageren

#1

JayCi

    JayCi


  • 0 - 25 berichten
  • 7 berichten
  • Gebruiker

Geplaatst op 31 oktober 2006 - 02:13

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?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 31 oktober 2006 - 09:59

Best lastig, geen middelbare school vraag neem ik aan?

Volgens mij is het LaTeX
In theory, there's no difference between theory and practice. In practice, there is.

#3

*_gast_PeterPan_*

  • Gast

Geplaatst op 31 oktober 2006 - 11:42

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 ?

#4

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 31 oktober 2006 - 17:32

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:

Volgens mij is het LaTeX

Minnetje vergeten, moet zijn: LaTeX
In theory, there's no difference between theory and practice. In practice, there is.

#5

JayCi

    JayCi


  • 0 - 25 berichten
  • 7 berichten
  • Gebruiker

Geplaatst op 01 november 2006 - 02:30

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


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:

Volgens mij is het LaTeX

Minnetje vergeten, moet zijn: LaTeX


#6

kotje

    kotje


  • >1k berichten
  • 3330 berichten
  • Verbannen

Geplaatst op 01 november 2006 - 08:03

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?

#7

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 01 november 2006 - 10:50

Notatie: LaTeX is de verwachtingswaarde van het aantal verwisselingen in een rij met n elementen. LaTeX .

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 LaTeX . 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 LaTeX . Het aantal rijen met op de k-de positie het grootste element is LaTeX . Voor de verwachtingswaarde van het aantal verwisselingen kunnen we nu dus zeggen:
LaTeX
(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:
LaTeX
Deze formule moet ook gelden voor n-1:
LaTeX
We gaan nu verder met hierboven:
LaTeX
dus:
LaTeX
Hieruit is simpel te zien dat geldt:
LaTeX
Dit is volgens mij de vergelijking van een harmonisch getal en hiervoor is dacht ik geen expliciete formule.

#8

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 01 november 2006 - 12:22

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: LaTeX
In theory, there's no difference between theory and practice. In practice, there is.

#9

JayCi

    JayCi


  • 0 - 25 berichten
  • 7 berichten
  • Gebruiker

Geplaatst op 02 november 2006 - 23:29

Beste Rogier,

Ik heb gezien dat er twee oplossingen zijn:

LaTeX

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

#10

JayCi

    JayCi


  • 0 - 25 berichten
  • 7 berichten
  • Gebruiker

Geplaatst op 02 november 2006 - 23:34

Beste Rogier,

Ik heb gezien dat er twee oplossingen zijn:

LaTeX

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





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures