Stuhlbesetzungsproblem < Wahrscheinlichkeit < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:16 So 16.09.2007 | | Autor: | janssens |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Folgendes Problem: X Personen stehen X leeren Stuehlen gegenüber.
In X Durchgängen wird nun jeder Person ein Stuhl per Zufall zugelost.
Je nachdem, ob der Platz noch frei ist oder nicht, setz sie sich auf den Stuhl oder geht leer aus, sprich die Person nimmt nicht weiter an dem Verfahren teil. Die Frage ist nun, wieviel Prozent der Personen auf diesem Weg einen Platz finden.
Habe das Verfahren gewählt, um die Zuverlässigkeit von Zufallszahlen bei der Programmierung zu testen.(hier Funktion rand() in PHP) in etlichen Programmdurchläufen mit unterschiedlicher Anzahl Personen(untersch. Arraygrösse) ergab einen Wert knapp über 0.75, also ca. 75%. Dies ist unabhängig von der Anzahl der Stühle.
Kann jemand dies mathematisch spezifizieren?
MfG Stephan
|
|
| |
|
Hallo Stephan,
> Folgendes Problem: X Personen stehen X leeren Stuehlen
> gegenüber.
> In X Durchgängen wird nun jeder Person ein Stuhl per
> Zufall zugelost.
> Je nachdem, ob der Platz noch frei ist oder nicht, setz
> sie sich auf den Stuhl oder geht leer aus, sprich die
> Person nimmt nicht weiter an dem Verfahren teil. Die Frage
> ist nun, wieviel Prozent der Personen auf diesem Weg einen
> Platz finden.
Dies scheint eine Abwandlung des ![[]](/images/popup.gif) Geburtstagsproblems zu sein. Die W'keit, das k Personen sich k von n Stühlen zum Sitzen finden können, wäre demnach:
[mm]p=\frac{(n-0)(n-1)\dotsm{}(n-k+1)}{n^k}[/mm]
Aber wie man jetzt daraus auf [mm]p=0.75\![/mm] kommt, ist mir leider nicht ganz klar.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:38 Mo 17.09.2007 | | Autor: | Donut87 |
Die Frage kann doch wohl nicht sein ob alle Stühle besetzt werden (denn das ist theoretisch immer möglich) sondern viel eher mit welcher Wahrscheinlichkeit dieser Fall eintritt. Es sind ja alle Fälle von "Eine Person findet Platz" bis "Alle Personen finden Platz" denkbar. Die Frage
> wieviel Prozent der Personen auf diesem Weg einen Platz finden.
verstehe ich nicht so ganz.
|
|
|
| |
|
Hallo,
ich vermute, dass es sich bei den 75% nicht wie beim Geburtstagsproblem darum handelt, wie wahrscheinlich es ist, dass k Personen Platz finden, sondern darum, wieviele Personen im Schnitt Platz finden, gewichtet mit den jeweiligen Häufigkeiten natürlich (Erwartungswert), oder?
Also z.B. bei 3 Stühlen/Personen/Durchgängen:
Es gibt 3 Möglichkeiten, dass nur einer Platz findet:
1,1,1 | 2,2,2 | 3,3,3
Es gibt 18 Möglichkeiten, dass zwei Platz finden:
1,1,2 | 1,1,3 | 1,2,1 | 1,2,2 | 1,3,1 | 1,3,3 | 2,1,1 | 2,1,2 | 2,2,1 | 2,2,3 | 2,3,2 | 2,3,3 | 3,1,1 | 3,1,3 | 3,2,2 | 3,2,3 | 3,3,1 | 3,3,2
Es gibt 6 Möglichkeiten, dass alle drei Platz finden:
1,2,3 | 1,3,2 | 2,1,3 | 2,3,1 | 3,1,2 | 3,2,1
Also kommen wir im Schnitt auf [mm]\bruch{3*1 + 18*2 + 6*3}{3^3} = 2,111[/mm], was 70% von 3 Personen entspricht.
Mathematisch wird das etwas unangenehm, rechnerisch leider auch. Bis n=9 kann man aber sehen, dass die Werte doch etwas tiefer liegen. Ich liefere sie gleich nach.
So, ich bekomme folgende Werte:
[mm] \begin{matrix}
n & proz. Anteil\\
---&---\\
1 & 100\\
2 & 75 \\
3 & 70,37\\
4 & 68,36 \\
5 & 67,23 \\
6 & 66,51 \\
7 & 66,01 \\
8 & 65,64 \\
9 & 65,36
\end{matrix}
[/mm]
Gruß
Martin
|
|
|
|
