Anzahl Schüler in einer Klasse, so dass mit 50% Wahrscheinlichkeit jeden zweiten Tag ein Geburtstag

Neue Frage »

Andre2000 Auf diesen Beitrag antworten »
Anzahl Schüler in einer Klasse, so dass mit 50% Wahrscheinlichkeit jeden zweiten Tag ein Geburtstag
Hallo zusammen,

ich habe hier eine, wie ich finde, fiese Variante einer Geburtstagsaufgabe. :-)

Ich suche die Anzahl der Schüler in einer Klasse die ich benötige, um mit einer Wahrscheinlichkeit von P (z.B. 50%, 80%..) jeden zweiten Tag oder jeden dritten Tag oder jeden Tag einen Geburtstag zu haben. Zum Beispiel könnte die Antwort lauten: Ich brauche mindestens 160 Schüler damit mit einer Wahrscheinlichkeit von 50% jeden zweiten Tag jemand Geburtstag hat.

Als Ansatz stehe ich gerade vor dem "Geburtstagsparadoxon", dass mir ja sagt, dass bei 23 Schülern mit >50% Prob. zwei am selben Tag Geburtstag haben. Ich bekommen das aber irgendwie nicht geeignet auf meinen Anwendungsfall transferiert. :-)

Habt ihr ne Idee! Danke!

Andre
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Andre2000
Ich suche die Anzahl der Schüler in einer Klasse die ich benötige, um mit einer Wahrscheinlichkeit von P (z.B. 50%, 80%..) jeden zweiten Tag oder jeden dritten Tag oder jeden Tag einen Geburtstag zu haben.

Bitte genauer spezifizieren, was das heißen soll. Wenn man beispielsweise (geordnet) die Geburtstage hat

1.1., 3.1., 5.1., 6.1., 8.1., 10.1.

usw. ist deine Bedingung "jeden zweiten Tag Geburtstag" dann auch noch erfüllt? Strenggenommen nein, allerdings hat man keine Lücke von mehr als einem Tag - vielleicht meinst du es ja auch so! verwirrt
 
 
Andre2000 Auf diesen Beitrag antworten »

Oh ja, sorry. Du hast Recht.

Also mit "jeder zweiter Tag oder jeder dritter Tag" meine ich in der Tat, dass nicht mehr als ein bzw. zwei geburtstagsfreie Tage zwischen zwei Geburtstagen liegen. D.h. die Geburtstage dürfen ruhig näher beeinaner liegen, aber nicht weiter auseinander. Deine Folge 1.1., 3.1., 5.1., 6.1., 8.1. wäre also in Ordnung.

Und ich glaube wir brauchen auch noch die zugrundeliegende Basisperiode, d.h. z.B. 1 Jahr oder 1 Monat oder 1 Woche? Hier würde ich ein Jahr nehmen wollen.

Und wenn ich nur mit einer gewissen Wahrscheinlichkeit die regelmäßigen Geburtstage haben will, müsste ich die Anzahl der dafür notwendigen Personen damit ja senken können? D.h. ich hätte dann so etwas wie " ich brauche 180 Personen um mit einer Wahrscheinlichkeit von 0,8 nicht mehr als einen Geburtstagsfreien Tag in Folge innerhalb eines Kalenderjahres zu haben".

Ich hoffe, ich habe nichts vergessen. :-)

Danke!

Andre
Andre2000 Auf diesen Beitrag antworten »

Moin,

ich knacke immer noch an meinem Problem, s.o. Ist es immer noch zu unklar oder ist es wirklich so, dass keiner eine Idee hat? Das muss sich doch irgendwie abbilden lassen. :-(

Danke!!!

Andre
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Andre2000
ich brauche 180 Personen um mit einer Wahrscheinlichkeit von 0,8 nicht mehr als einen Geburtstagsfreien Tag in Folge innerhalb eines Kalenderjahres zu haben".

Bis zu 181 Personen ist die Wahrscheinlichkeit gleich Null, keine größere Lücke als einen Tag zwischen Geburtstagen zu haben, und auch für mehr als 181 Personen steigt diese Wahrscheinlichkeit nur ganz, ganz langsam an.

Nur mal zum Vergleich, um überhaupt verschiedene Geburtstage zu haben (da ist noch nicht im entferntesten berücksichtigt, dass die "richtig" über das Jahr verteilt sein müssen!), braucht man im Mittel



Schüler, bei sind das immerhin schon etwa 252 Schüler.


Die tatsächliche Anzahl für dein Problem hier ist schwer zu greifen. Eventuell ist Simulation angesagt.


EDIT: Hab mal ein bisschen simuliert, es scheinen 1343 (!) Schüler notwendig zu sein, um deine Wkt >0.8 zu haben. Augenzwinkern
dinzeoo Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000


Die tatsächliche Anzahl für dein Problem hier ist schwer zu greifen. Eventuell ist Simulation angesagt.


EDIT: Hab mal ein bisschen simuliert, es scheinen 1343 (!) Schüler notwendig zu sein, um deine Wkt >0.8 zu haben. Augenzwinkern


Hi, dürfte ich deinen Code mal sehen? Hab es zum Spaß auch simuliert. Allerdings bin ich nicht der beste Programmierer. Deine 1343 kann ich soweit bestätigen.

Mein Rechenaufwand scheint in meinem Code aber viel zu hoch zu sein, nur das überprüfen von 1343 dauert schon 1min. bei 10000 Simulationen. Anders formuliert, hätte ich dein Ergebnis nicht gekannt, wäre mein Programm relativ nutzlos. Ich kann nämlich nicht einfach alle Schülerzahlen durchprobieren bis ich >0.8 bekomme.
HAL 9000 Auf diesen Beitrag antworten »

Mein C-Programm nutzt die 4 Kerne meines betagten (4 Jahre alt) Intel Q9550 und schafft damit bei 1343 Schülern ca. 200000 Simulationen pro Sekunde. Den Code des Gesamtprogramms gebe ich ungern preis (wegen all des unübersichtlichen Multithreading-Zeugs), allenfalls den Pseudocode einer Einzelsimulation:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
#define MAX_DAYS  1000

[...]

int nPersons        = 1343;   // Anzahl Schüler
int nDays           = 365;    // Anzahl Tage des Jahres
int nMaxDays        = 1;      // maximale Anzahl geburtstagsfreier aufeinander folgender Tage
int nSuccess        = 0;      // Anzahl bisher erfolgreicher Simulationen

[...]
    
    int         i;
    int         nDay;
    BOOL        boFlags[MAX_DAYS];
    
       /* START einer Einzelsimulation */
       memset(boFlags, 0, nDays*sizeof(BOOL));
       for (i = 0; i < nPersons; i++)
       {
           boFlags[random(nDays)] = TRUE;
       }
       nDay = 0;
       for (i = 0; i < nDays; i++)
       {
          if (boFlags[i] == FALSE)
          {
             nDay++;
          }
          else
          {
             nDay = 0;
          }
          if (nDay > nMaxDays)
          {
              nDay = -1;
              break;
          }
       }
       if (nDay >= 0)
       {
           nSuccess++;
       }
       /* ENDE einer Einzelsimulation */

Wenn man auch den Jahreswechsel einbezieht ("wrap around"), dann braucht man übrigens einen Schüler mehr, also 1344, um auf die 80% zu kommen: Z.B. wäre dann eine Geburtstagslücke 31.12+1.1. nicht mehr statthaft. Augenzwinkern

Hab ich oben im Code jetzt mal weggelassen, weil es die Sache nur unübersichtlicher macht.
dinzeoo Auf diesen Beitrag antworten »

hey hal, vielen dank.

Zitat:

Den Code des Gesamtprogramms gebe ich ungern preis


kein problem, der code der einzelsimulation reicht mir schon. wollte rein aus neugier mal wissen wie du vorgegangen bist. hab meinen fehler jetzt erkannt. ich hab es nicht über diese bool variabe bzw. true false gelöst sondern viel zu umständlich mehrere for schleifen für schwachsinn verbraucht. um genau zu sein so:

- zufallsvektor der grösse 1x1443 erstellt. d.h. ich hatte dann z.b. einen vektor (1,222,4,3,6,365,1,1,3,54,usw.)
-diesen nach der größe sortiert, d.h. (1,1,1,3,3,4, usw.)
-danach überprüft ob die differenz zweier aufeinanderfolgender zahlen grösser 2 ist

fürs effizientere programmieren brauch ich wohl mehr erfahrung, aber danke nochmal für deine ausführung!
HAL 9000 Auf diesen Beitrag antworten »

Ja, die Effizienz hängt wirklich auch von den Größenbereichen der Parameter ab: Hätten wir vergleichsweise wenige Schüler (so etwa <30), dann wäre dein Verfahren vermutlich sogar schneller. Natürlich sind diese geringen Schülerzahlen in Bezug auf die konkrete Problemstellung mit "maximal ein Tag Lücke" uninteressant, aber vielleicht ist man ja auch mal an Lücken von maximal einen Monat o.ä. interessiert - dann sieht es schon anders aus. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »