________________________________________________________________________________
Inhalt....: Das Geburtstagsproblem
Kategorie.: Arbeitsblatt
Mathematik: Stochastik, Kryptographie
MuPAD.....: 3.0.0
Datum.....: 2003-06-23
Autoren...: Julia Faflek <faflek@mupad.de>
Funktionen: !, plot, plot::Polygon2d
________________________________________________________________________________
Das Geburtstagsproblem oder wie viele
Personen lade ich zu meiner Party ein?
Das Geburtstagsproblem ist ein klassisches Beispiel aus der Stochastik und Wahrschein-
lichkeitsrechnung, welches auch in der Kryptographie Anwendung findet.
Zu meinem nächsten Geburtstag möchte ich eine große Party machen. Dazu
überlege ich mir, wie viele Freunde ich einladen soll. Denn an diesem Tag soll
mit einer Wahrscheinlichkeit größer als 1/2 mind. einer der Anwesenden auch
Geburtstag haben.
Wir betrachten die Gegenwahrscheinlichkeit: Aus einer Gruppe von n Personen
hat niemand an meinem Tag Geburtstag. Die Anzahl möglicher Ereignisse ist
die Anzahl möglicher Geburtstage für n Personen:
Für die Anzahl günstiger Ereignisse ergibt sich mittels Kombinatorik:
Damit ergibt sich für die gesuchte Wahrscheinlichkeit:
p1 := n -> 1 - (364^n)/(365^n)
Zunächst stellen wir diese Wahrscheinlichkeit für bis zu 365 Personen grafisch
dar.
Punkte1 := [0 $ 365]:
for i from 1 to 365 do
Punkte1[i] := [i, p1(i)]
end_for:
plot(plot::Polygon2d(Punkte1));
(Die Punkte liegen so nahe beieinander, dass der obige Polygonzug wie
-ein gewöhnlicher, von MuPAD dargestellter, Funktionsgraph aussieht.)
Nun suchen wir das minimale n, für das die Wahrscheinlichkeit größer als 1/2
ist. Anhand der Grafik können wir dieses n für den Bereich 240 bis 260 ein-
schränken:
for j from 240 to 260 do
print("Bei ".j. " Personen beträgt die Wahrscheinlichkeit "
.expr2text(float(p1(j))))
end_for:
"Bei 240 Personen beträgt die Wahrscheinlichkeit 0.4823400021"
"Bei 241 Personen beträgt die Wahrscheinlichkeit 0.4837582487"
"Bei 242 Personen beträgt die Wahrscheinlichkeit 0.4851726097"
"Bei 243 Personen beträgt die Wahrscheinlichkeit 0.4865830957"
"Bei 244 Personen beträgt die Wahrscheinlichkeit 0.4879897173"
"Bei 245 Personen beträgt die Wahrscheinlichkeit 0.4893924852"
"Bei 246 Personen beträgt die Wahrscheinlichkeit 0.4907914099"
"Bei 247 Personen beträgt die Wahrscheinlichkeit 0.4921865019"
"Bei 248 Personen beträgt die Wahrscheinlichkeit 0.4935777718"
"Bei 249 Personen beträgt die Wahrscheinlichkeit 0.4949652299"
"Bei 250 Personen beträgt die Wahrscheinlichkeit 0.4963488869"
"Bei 251 Personen beträgt die Wahrscheinlichkeit 0.4977287529"
"Bei 252 Personen beträgt die Wahrscheinlichkeit 0.4991048385"
"Bei 253 Personen beträgt die Wahrscheinlichkeit 0.500477154"
"Bei 254 Personen beträgt die Wahrscheinlichkeit 0.5018457098"
"Bei 255 Personen beträgt die Wahrscheinlichkeit 0.5032105161"
"Bei 256 Personen beträgt die Wahrscheinlichkeit 0.5045715831"
"Bei 257 Personen beträgt die Wahrscheinlichkeit 0.5059289213"
"Bei 258 Personen beträgt die Wahrscheinlichkeit 0.5072825407"
"Bei 259 Personen beträgt die Wahrscheinlichkeit 0.5086324515"
"Bei 260 Personen beträgt die Wahrscheinlichkeit 0.509978664"
Dieser Ausgabe entnehmen wir, dass bei 253 Personen die Wahrscheinlich-
keit bereits höher als 1/2 liegt. Die gesuchte Anzahl der Personen ist also 253.
Demnach muss ich zu meiner Geburtstagsparty 252 Personen (253-ich) einla-
den, wenn ich mit einer Wahrscheinlichkeit größer als 1/2 nicht die einzige Per-
son sein möchte, die an diesem Tag Geburtstag hat.
Verallgemeinern wir die Situation etwas. Ich befinde mich auf einer Einweihungs-
party. Wie viele Personen müssen anwesend sein, damit mit einer Wahrschein-
lichkeit größer als 1/2 mind. 2 Personen an dem selben Tag Geburtstag haben?
Der Unterschied zu dem vorherigen Beispiel besteht darin, dass jetzt nicht nach
einem bestimmten Tag gefragt wird, sondern nach einem beliebigen. Schauen
wir uns auch hier zunächst die Gegenwahrscheinlichkeit an: Die Anzahl möglicher
Ereignisse bleibt gleich, nur die Anzahl günstiger Ereignisse ändert sich zu
Damit ergibt sich für die gesuchte Wahrscheinlichkeit:
p2 := n -> 1 - (365!/(365-n)!)/(365^n)
Auch hier visualisieren wir das Verhalten:
Punkte2 := [0 $ 365]:
for i from 1 to 365 do
Punkte2[i] := [i, p2(i)]
end_for:
plot(plot::Polygon2d(Punkte2));
Schauen wir uns das Ganze mal im Zusammenhang an:
pl1 := plot::Polygon2d(Punkte1, Color = RGB::Blue):
pl2 := plot::Polygon2d(Punkte2, Color = RGB::Green):
plot(pl1, pl2)
Erstaunlich wie sehr sich diese beiden Wahrscheinlichkeiten unterscheiden!
Nun suchen wir das minimale n, für das die Wahrscheinlichkeit größer als 1/2
ist. Anhand der Grafik können wir dieses n für den Bereich von 10 bis 30 ein-
schränken:
for j from 10 to 30 do
print("Bei ".j. " Personen beträgt die Wahrscheinlichkeit "
.expr2text(float(p2(j))))
end_for:
"Bei 10 Personen beträgt die Wahrscheinlichkeit 0.1169481777"
"Bei 11 Personen beträgt die Wahrscheinlichkeit 0.1411413783"
"Bei 12 Personen beträgt die Wahrscheinlichkeit 0.1670247888"
"Bei 13 Personen beträgt die Wahrscheinlichkeit 0.1944102752"
"Bei 14 Personen beträgt die Wahrscheinlichkeit 0.223102512"
"Bei 15 Personen beträgt die Wahrscheinlichkeit 0.2529013198"
"Bei 16 Personen beträgt die Wahrscheinlichkeit 0.2836040053"
"Bei 17 Personen beträgt die Wahrscheinlichkeit 0.3150076653"
"Bei 18 Personen beträgt die Wahrscheinlichkeit 0.3469114179"
"Bei 19 Personen beträgt die Wahrscheinlichkeit 0.379118526"
"Bei 20 Personen beträgt die Wahrscheinlichkeit 0.4114383836"
"Bei 21 Personen beträgt die Wahrscheinlichkeit 0.4436883352"
"Bei 22 Personen beträgt die Wahrscheinlichkeit 0.4756953077"
"Bei 23 Personen beträgt die Wahrscheinlichkeit 0.5072972343"
"Bei 24 Personen beträgt die Wahrscheinlichkeit 0.5383442579"
"Bei 25 Personen beträgt die Wahrscheinlichkeit 0.568699704"
"Bei 26 Personen beträgt die Wahrscheinlichkeit 0.5982408201"
"Bei 27 Personen beträgt die Wahrscheinlichkeit 0.6268592823"
"Bei 28 Personen beträgt die Wahrscheinlichkeit 0.6544614723"
"Bei 29 Personen beträgt die Wahrscheinlichkeit 0.6809685375"
"Bei 30 Personen beträgt die Wahrscheinlichkeit 0.7063162427"
Wir sehen also, dass mind. 23 Personen auf der Party anwesend sein müssen,
damit mit einer Wahrscheinlichkeit größer als 1/2 mind. 2 Personen an dem
gleichen Tag Geburtstag haben.
Anwendung findet dieses Problem auch in der Kryptographie. Dort betrachtet
man eine Funktion und untersucht, ob zwei verschiedene Urbilder den gleichen
Funktionswert liefern. Man sucht so genannte Kollisionen z.B. bei Pollard's-Rho-
Methode zum Faktorisieren ganzer Zahlen. Wobei die in der Kryptographie oft
benutzten Hashfunktionen kollisionsfrei sein sollen.
___________________________________________________________________________________
Übungen:
1. Machen Sie sich mit den Funktionen ! und fact vertraut.
2. Besuchen Sie die Hilfeseite zu ?plot::Polygon2d.
___________________________________________________________________________________
Anmerkungen:
1. Unter www.schule.mupad.de/material/ finden Sie weitere interessante Notebooks.
2. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe wird eine Vielzahl
ssunterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die Bücher können unter
sswww.schule.mupad.de/literatur kostenfrei kopiert werden.
___________________________________________________________________________________