Re: Telprobleem

Dit is een reactie op vraag 41427

Geachte,

In antwoord op mijn vraag 'Kan dit probleem veralgemeend worden voor n personen?' werd mij geantwoord met de verwijzing naar een link over het "sinterklaasprobleem".

Tenzij de analogie mij ontgaat, is er toch een verschil: bij het Sinterklaasprobleem mag niemand zichzelf kiezen. Hier bereken je echter de kans dat er geen koppels zijn die elkaar gekozen hebben. Toch niet helemaal hetzelfde. Of wel?

Groetjes

pepijn
Docent - zondag 18 maart 2007

Antwoord

Update: collega-beantwoorder JCS kwam met volgend antwoord, waarvoor hartelijk dank:

----------------------------

Het probleem: In een groep van n personen schrijft ieder de naam van een willekeurig ander lid van de groep op een kaartje. Als we aan alle (n-1)ⁿ mogelijkheden dezelfde kans toekennen, hoe groot is dan de kans dat er minstens 1 tweetal personen is dat elkaars naam heeft opgeschreven?

Oplossing mbv de zg regel van “inclusie en exclusie” (zie William Feller, An Introduction to Probability Theory and its Applications. Hoofdstuk 5: Combinations of Events.)
Laat A1, A2, …, AN een rij gebeurtenissen zijn. De kans P dat minsten één ervan optreedt is:

P = S1 - S2 + S3 – S4 ….. ± SN ,
met S1 = PA1 + PA2 + … + PAN (N termen)
S2 = PA1A2 + PA1A3 + … ( N(N-1)/2 = C(N,2) termen, alle PAi Aj met i< j)
S3 is de som van alle C(N, 3) kansen PAi Aj Ak met I< j < k.
Enzovoort.
Hoe passen we dit toe op ons geval?
We hebben N = C(n,2) gebeurtenissen van het type Aij : = “ Personen i en j hebben elkaar gekozen” Zeg maar: “i en j vormen een koppel”. De kans daarop is : 1/(n-1)²

Voor de sommen S1, S2, enz. krijgen we:

S1 = n(n-1)/2 · 1/(n-1)²

S2 = {n(n-1)(n-2)(n-3)/(2·2 ·2!)} · 1/(n-1)⁴ ( het deel tussen accoladen is het aantal manieren om twee disjuncte tweetallen te kiezen.

Algemeen: Sk = n(n-1)….(n-2k+1)/(2^k · k!) · 1/(n-1)²k
= P(n,2k)/(2^k · k!) · 1/(n-1)²k (met P(n,j) = C(n,j)·j!)
en dit zolang 2k ≤ n

Dus bv n = 5: S1 = 10 /16 = 640/1024
S2 = ( 120 /8) / 256 = 60/1024
Dus P = S1 –S2 = 580 / 1024
Zelfs voor n =11 kun je nu nog gemakkelijk de kans op minstens 1 koppel met de hand berekenen.

Interessant is ook de berekening wat de kans op minstens één koppel wordt als het aantal mensen groot wordt (naar oneindig gaat dus). Dit naar analogie met de limietkans 1/e uit het sinterklaasprobleem.

Er blijkt dat de kans P op minstens één koppel, convergeert naar 0,3935... terwijl het dus a priori niet intuïtief duidelijk was of die kans naar 0, naar 1, of naar een tussenliggende waarde zou convergeren...

---------------------------

En dit was het oorspronkelijke antwoord, echter zonder bevredigende oplossing...

-------------

Het is inderdaad een ander probleem dan het sinterklaasprobleem. En ook een veel lastiger denk ik. Voor n vrij klein kan je nog met een computerprogramma weg, maar een algemene formule heb ik niet gevonden.

Het is duidelijk dat je met n personen (n-1)ⁿ uitkomsten kan hebben. Ik denk dat het het 'makkelijkst' moet zijn om te tellen hoeveel goede uitkomsten er zijn, dus zonder paar (noem dit aantal T(n) ). De reden is dat je anders moet meenemen dat er uitkomsten zijn met 2, 3, ... paren, en dan moet je opletten dat je niks dubbel telt.

Ik heb geprobeerd met inductie iets te doen: om een goede oplossing te krijgen, zeg dat 1 kiest a, a kiest b, met 1, a en b allemaal verschillend. Dan kan b kiezen voor 1, of voor een nieuwe persoon c. Kiest b voor 1, dan heb je nog n-3 mensen over. Kiest b voor c en c voor 1: nog n-4 personen. Enzovoort.

Probleem is dat, bv bij 1 kiest a, a kiest b, b kiest 1, heb je niet T(n-3) mogelijkheden meer, want alle anderen kunnen ook nog voor 1 of a of b kiezen. Je zou dan krijgen T(n-3) (dan kiezen de n-3 andere personen nooit voor 1 of a of b), plus de oplossingen waarbij die 3 wel gekozen worden, maar om die te tellen zonder dubbele tellingen lijkt mij heel moeilijk.

Andere methode? Voor i van 1 tot n noem je n(i) het aantal keren dat i gekozen wordt. Probleem hier: die partities kan je nog wel tellen, maar je kan ze op veel verschillende manieren invullen: als n(i)=n(j)=1 dan krijg je een verschillende situatie wanneer i en j voor elkaar kiezen dan wanneer i voor j kiest en j niet voor i, of dat ze geen van beiden voor de andere kiezen. Dus ook hier wordt het hopeloos complex.

Grafische aanpak? 1 tot n op een horizontale as, 1 tot n op een verticale as, juist één punt per verticale rechte, geen punten op de diagonaal y=x, de spiegeling van punten tov de y=x geeft geen punten die er al waren (dat bevat dus ook de vorige eis). Dit zijn de eisen. Nu, teken de punten (x,y) wanneer x kiest voor y, en teken ook de spiegeling over de rechte y=x. De figuur wordt dan symmetrisch, dus je kan dan net zo goed kijken naar de punten onder de diagonaal. Daar moeten dus n punten liggen op de n·(n-1)/2 roosterpunten. Als je dan een paar had (a kiest b, b kiest a), dan krijg je de punten (a,b) en (b,a) elk twee keer en liggen er dus slechts maximaal n-1 punten binnen die driehoek, dus de eisen 'geen paren' en 'niet voor jezelf kiezen' zijn dan voldaan.

Probleem is hier weer dat je moet kunnen tellen met hoeveel keuzes zo één grafische voorstelling overeenkomt, en dat aantal hangt ook weer sterk van de ligging van de punten af (kan ook nul zijn trouwens).

Voor wat het waard is kan ik wel de kansen geven voor kleine n-waarden:
n=1: 0 mogelijkheden
n=2: 1 mogelijkheid, waarvan 1 met paren
n=3: 8 mogelijkheden, waarvan 6 met paren
n=4: 81 mogelijkheden, waarvan 51 met paren
n=5: 1024 mogelijkheden, waarvan 580 met paren
n=6: 15625 mogelijkheden, waarvan 8265 met paren
n=7: 279936 mogelijkheden, waarvan 141246 met paren
n=8: 5764801 mogelijkheden, waarvan 2810437 met paren
n=9: 134217728 mogelijkheden, waarvan 63748728 met paren

Voor steeds grotere n lijkt de kans op situaties met paren dus licht te dalen, maar of dat zo blijft is natuurlijk niet zeker, en dan nog kan het zijn dat de kans naar nul gaat voor grote n, of dat er een limietkans bestaat zoals bij het sinterklaasprobleem.

Dus sorry, maar het antwoord dat je zocht is er (nog) niet gekomen...

Groeten,
Christophe.

Christophe
maandag 2 april 2007

©2001-2024 WisFaq