geburtstagsproblem < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:05 Mi 08.11.2006 | | Autor: | Moe007 |
| Aufgabe | Sei [mm] p_{n} [/mm] die W., dass in einer Klasse von n Kindern mind. 2 am gleichen Tag Geburtstag haben. Vereinfachend sei angenommen, dass kein Kind am 29.02. geboren ist, und alle Geburtstage gleichwahrscheinlich.
Z.Z.: [mm] p_{n} \ge [/mm] 1- exp(- [mm] \bruch{n(n-1)}{730}) [/mm] (unter Verwendung der Abschätzung 1-x [mm] \le e^{-x})
[/mm]
Man bestimme ein möglichst kleines n mit [mm] p_{n}\ge \bruch{1}{2} [/mm] |
HalliHallo,
ich hab versucht, die Aufgabe so weit ich konnte zu lösen, komm aber an einer Stelle nicht mehr weiter. ich hoffe, dass mir da jemand helfen kann. Danke!
Jeder Tag im Jahr ist gleichwahrscheinlich, also [mm] \bruch{1}{365}, [/mm] also ist [mm] |\omega| [/mm] = [mm] 365^{n}
[/mm]
Das Komplement von [mm] p_{n} [/mm] ist [mm] \overline{p_{n}} [/mm] = Alle n Personen haben an versch. Tagen Geburtstag.
Dann ist [mm] |p_{n}| [/mm] = [mm] \bruch{365!}{(365-n)!} [/mm] oder??
Also ist [mm] p_{n} [/mm] = 1- [mm] \overline{p_{n}} [/mm] = 1 - [mm] \bruch{|\overline{p_{n}}|}{|\omega|} [/mm] = 1- [mm] \bruch{365!}{(365-n)! 365^{n}}
[/mm]
Jetzt weiß ich nicht wie ich auf [mm] p_{n} \ge [/mm] 1- exp(- [mm] \bruch{n(n-1)}{730}) [/mm] kommen soll.
Nach der Abschätzung, die man ja verwenden soll, folgt aus dem oberen [mm] p_{n} \le e^{\bruch{365!}{(365-n)! 365^{n}}} [/mm] oder?
Dann sollte man ja ein möglichst kleines n finden mit [mm] p_{n}\ge \bruch{1}{2}.
[/mm]
Da hab ich folgendes berechnet: 1- exp(- [mm] \bruch{n(n-1)}{730}) [/mm] = 1/2
Nach längerer Rechnung kommt beimir n= 23 heraus, kann das sein?
Ich hoffe, es kann mir jemand bei dem obigen Beweis weiter helfen.
Danke und viele Grüße,
Moe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:02 Mi 08.11.2006 | | Autor: | Walde |
Hi Moe007,
> Sei [mm]p_{n}[/mm] die W., dass in einer Klasse von n Kindern mind.
> 2 am gleichen Tag Geburtstag haben. Vereinfachend sei
> angenommen, dass kein Kind am 29.02. geboren ist, und alle
> Geburtstage gleichwahrscheinlich.
> Z.Z.: [mm]p_{n} \ge[/mm] 1- exp(- [mm]\bruch{n(n-1)}{730})[/mm] (unter
> Verwendung der Abschätzung 1-x [mm]\le e^{-x})[/mm]
>
> Man bestimme ein möglichst kleines n mit [mm]p_{n}\ge \bruch{1}{2}[/mm]
>
> HalliHallo,
> ich hab versucht, die Aufgabe so weit ich konnte zu lösen,
> komm aber an einer Stelle nicht mehr weiter. ich hoffe,
> dass mir da jemand helfen kann. Danke!
>
> Jeder Tag im Jahr ist gleichwahrscheinlich, also
> [mm]\bruch{1}{365},[/mm] also ist [mm]|\omega|[/mm] = [mm]365^{n}[/mm]
>
> Das Komplement von [mm]p_{n}[/mm] ist [mm]\overline{p_{n}}[/mm] = Alle n
> Personen haben an versch. Tagen Geburtstag.
>
> Dann ist [mm]|p_{n}|[/mm] = [mm]\bruch{365!}{(365-n)!}[/mm] oder??
Was da steht ist die Anzahl von Möglichkeiten, die n Personen haben an n verschiedenen Tagen Geburtstag zu haben. Das stimmt. Aber du solltest das nicht [mm] |p_{n}| [/mm] nennen. Denn der Buchstabe [mm] p_n [/mm] ist schon belegt, wie du es ja oben benutzt hast. So wie es da steht ist es falsch, auch wenn du das richtige meinst.
>
> Also ist [mm]p_{n}[/mm] = [mm] 1-\overline{p_{n}}[/mm] =1-\bruch{|\overline{p_{n}}|}{|\omega|}[/mm] [/mm]
>[mm]= 1- \bruch{365!}{(365-n)! 365^{n}}[/mm]
Jo stimmt, aber wie gesagt, nimm was anderes als [mm] |p_n| [/mm] als Bezeichner.
>
> Jetzt weiß ich nicht wie ich auf [mm]p_{n} \ge[/mm] 1- exp(-
> [mm]\bruch{n(n-1)}{730})[/mm] kommen soll.
Hm, ich geh mal von der Abschätzung aus:
[mm] 1-x\le e^{-x}
[/mm]
[mm] \gdw x-1\ge -e^{-x}
[/mm]
[mm] \gdw x\ge 1-e^{-x} [/mm] für x setze ich jetzt ein, was du zeigen sollst
[mm] \gdw -\bruch{n(n-1)}{730}\ge 1-e^{-\bruch{n(n-1)}{730}} [/mm]
Ok, wenn du jetzt zeigen kannst, dass
[mm] p_n=1-\bruch{365!}{(365-n)! 365^{n}}\red{\ge}-(\bruch{n(n-1)}{730}),
[/mm]
dann hast du's geschafft. Ich würde es mal mit Induktion nach n probieren, ich habe es aber selbst nicht ausprobiert.
>
> Dann sollte man ja ein möglichst kleines n finden mit
> [mm]p_{n}\ge \bruch{1}{2}.[/mm]
> Da hab ich folgendes berechnet: 1-
> exp(- [mm]\bruch{n(n-1)}{730})[/mm] = 1/2
> Nach längerer Rechnung kommt beimir n= 23 heraus, kann das
> sein?
Das dürfte stimmen. Kuck auch mal ![[]](/images/popup.gif) hier. Ein Wikipedia Artikel zum Geburtstagsproblem.
>
>
> Ich hoffe, es kann mir jemand bei dem obigen Beweis weiter
> helfen.
> Danke und viele Grüße,
> Moe
Ich hoffe, ich war hilfreich.
L G walde
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:28 Do 09.11.2006 | | Autor: | Moe007 |
Hallo walde,
vielen dank für deine ausführliche Antwort.
Ich hab leider nur ein Problem bei der Induktion.
Man muss ja [mm] p_n=1-\bruch{365!}{(365-n)! 365^{n}}\red{\ge}-(\bruch{n(n-1)}{730}) [/mm] zeigen.
Ind-anfang: n=0.
1- [mm] \bruch{365!}{365!} [/mm] = 0 [mm] \ge [/mm] 0. Stimmt.
Ind.-vor.: Es gilt die Beh. für ein n [mm] \in \IN.
[/mm]
Ind-schritt: n [mm] \to [/mm] n+1.
Z.z. ist doch nun [mm] 1-\bruch{365!}{(365-(n+1))! 365^{n+1}}\red{\ge}-(\bruch{n(n+1)}{730})
[/mm]
Da komm ich leider nicht weiter bei der Umformung:
[mm] 1-\bruch{365!}{(364-n)! 365^{n+1}} [/mm] = 1- [mm] \bruch{364!}{(364-n)! 365^{n}} [/mm]
Wie kann ich da nun die Ind.-voraussetzung einbauen?, damit der Ausdruck [mm] \ge -(\bruch{n(n+1)}{730}) [/mm] wird?
Ich hoffe, dass mir jemand weiterhelfen kann.
Viele Grüße,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:00 Fr 10.11.2006 | | Autor: | Walde |
Hi Moe007,
hier mein Versuch:
> Hallo walde,
> vielen dank für deine ausführliche Antwort.
> Ich hab leider nur ein Problem bei der Induktion.
> Man muss ja [mm]p_n=1-\bruch{365!}{(365-n)! 365^{n}}\red{\ge}-(\bruch{n(n-1)}{730})[/mm]
> zeigen.
Ja, aber ich forme das mal um, damit man leichter rechnen kann:
[mm] \gdw -\bruch{365!}{(365-n)! 365^{n}}\ge -\bruch{n(n-1)}{730}-1
[/mm]
[mm] \gdw \bruch{365!}{(365-n)! 365^{n}}\le \bruch{n(n-1)}{730}+1
[/mm]
Das ist ja äquivalent zum urspünglichen, aber mir fällt es leichter nach oben abzuschätzen 
>
> Ind-anfang: n=0.
> 1- [mm]\bruch{365!}{365!}[/mm] = 0 [mm]\ge[/mm] 0. Stimmt.
>
> Ind.-vor.: Es gilt die Beh. für ein n [mm]\in \IN.[/mm]
>
> Ind-schritt: n [mm]\to[/mm] n+1.
> Z.z. ist doch nun [mm]1-\bruch{365!}{(365-(n+1))! 365^{n+1}}\red{\ge}-(\bruch{n(n+1)}{730})[/mm]
>
> Da komm ich leider nicht weiter bei der Umformung:
>
> [mm]1-\bruch{365!}{(364-n)! 365^{n+1}}[/mm] = 1-
> [mm]\bruch{364!}{(364-n)! 365^{n}}[/mm]
> Wie kann ich da nun die Ind.-voraussetzung einbauen?, damit
> der Ausdruck [mm]\ge -(\bruch{n(n+1)}{730})[/mm] wird?
>
> Ich hoffe, dass mir jemand weiterhelfen kann.
>
> Viele Grüße,
> Moe
Ok. Mit der Umformulierung von oben ist die Ind.-Vorr. jetzt:
[mm] \bruch{365!}{(365-n)! 365^{n}}\le \bruch{n(n-1)}{730}+1
[/mm]
und zu zeigen ist:
[mm] \bruch{365!}{(365-(n+1))! 365^{n+1}}\le \bruch{n(n+1)}{730}+1
[/mm]
Also beginnen wir mit der linken Seite:
[mm] \bruch{365!}{(365-(n+1))! 365^{n+1}}
[/mm]
[mm] =\bruch{365!}{(365-n-1)! 365^{n}*365}*\bruch{(365-n)}{(365-n)}
[/mm]
[mm] =\bruch{365!}{(365-n)! 365^{n}}*\bruch{365-n}{365}
[/mm]
Soweit klar? Ich habe einfach mit 1 multipliziert, so dass ich den Nenner auf die Gestalt der Ind.Vorr. bringen kann, indem man aus [mm] 365^{n+1} [/mm] ein 365 rauszieht und bei [mm](365-n-1)![/mm] einen Faktor (365-n) dazu tut.
Was jetzt kommt ist verblüffend einfach: Der Faktor [mm] \bruch{365-n}{365}
[/mm]
ist kleiner 1. Wenn ich ihn also weglasse, vergrössert sich der gesamte Term:
[mm] \bruch{365!}{(365-n)! 365^{n}}*\bruch{365-n}{365}\le\bruch{365!}{(365-n)! 365^{n}}\le\bruch{n(n-1)}{730}+1 [/mm] nach Ind. Vorraussetzung.
und [mm] \bruch{n(n-1)}{730}+1\le\bruch{n(n+1)}{730}+1 [/mm] offensichtlich.
Es kommt mir so einfach vor,dass ich fürchte einen Fehler gemacht zu haben. Denks nochmal durch und wenns stimmt, dann freut es mich, dass ich dir helfen konnte.
L G walde
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:39 Fr 10.11.2006 | | Autor: | Moe007 |
Hallo walde,
du hast mir sehr viel geholfen  , vielen dank dafür!
Die Induktion war ganz schön trickreich...
|
|
|
| |
|
hallooo!
ich weiß das is schon ein wenig älter, aber ich hab da ein problem...
> [mm]\gdw x\ge 1-e^{-x}[/mm] für x setze ich jetzt ein, was du
> zeigen sollst
>
> [mm]\gdw -\bruch{n(n-1)}{730}\ge 1-e^{-\bruch{n(n-1)}{730}}[/mm]
wo kommt das minus auf der linken seite her? ich find keine mir bekannte rechnung die das rechtfertigt
andererseits ist für n=300 die linke seite etwa -122, während rechts etwa 1 steht
womit die ungleichung einfach mal falsch is
und die weiteren tipps damit mir auch nicht weiter helfen :D
lG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:35 Di 12.04.2011 | | Autor: | fred97 |
> hallooo!
> ich weiß das is schon ein wenig älter, aber ich hab da
> ein problem...
> > [mm]\gdw x\ge 1-e^{-x}[/mm] für x setze ich jetzt ein, was du
> > zeigen sollst
> >
> > [mm]\gdw -\bruch{n(n-1)}{730}\ge 1-e^{-\bruch{n(n-1)}{730}}[/mm]
>
> wo kommt das minus auf der linken seite her?
Nirgendwoher kommt das. Da hat sich jemand vertan.
FRED
> ich find keine
> mir bekannte rechnung die das rechtfertigt
> andererseits ist für n=300 die linke seite etwa -122,
> während rechts etwa 1 steht
> womit die ungleichung einfach mal falsch is
> und die weiteren tipps damit mir auch nicht weiter helfen
> :D
> lG
|
|
|
| |
|
gut, dass ich jetzt weiß, dass der ansatz falsch ist.
gut, dass ich keine neue idee hab -.-
ich krieg es irgendwie immer nur hin die linke seite nach oben, die rechte nach unten oder die mitte nicht in die mitte, sprich zu weit abzuschätzen :/
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Do 14.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Do 14.04.2011 | | Autor: | Walde |
Hi,
Also man darf ja verwenden, dass [mm] $1-x\le e^{-x}$ [/mm] also [mm] $1-e^{x}\le [/mm] x$
Es gilt (das sollte stimmen) [mm] p_n=1-\bruch{365!}{(365-n)!365^n}, [/mm] zu zeigen ist also
[mm] $1-e^{-\bruch{n(n-1)}{730}}\le 1-\bruch{365!}{(365-n)!365^n}$ [/mm] und da man [mm] $1-e^{-\bruch{n(n-1)}{730}}\le \bruch{n(n-1)}{730} [/mm] geschenkt bekommt (diesmal ohne den Fehler mit dem Minus), bleibt noch
[mm] \bruch{n(n-1)}{730}\le 1-\bruch{365!}{(365-n)!365^n} [/mm] zu zeigen.
Da ich bei der Induktion rausbekam, dass dies für n>1 nicht zu stimmen scheint (falls ich nicht wieder Schmuh gemacht habe), dachte ich mir, ich schau mir mal den Verlauf von [mm] f(x):=1-\bruch{365!}{(365-x)!365^x}-\bruch{x(x-1)}{730} [/mm] an, der Graph sollte ja (wenigstens irgendwann) oberhalb der x Achse verlaufen, damit die Behauptung stimmt. tut es aber nicht. Also ist entweder die Aufgabenstellung falsch oder es steckt irgendwo noch ein Fehler drin. Fred, kannst du nicht mal nachkucken, (ob) was nicht stimmt?
LG walde
|
|
|
|
