Weihnachtsfeier Geschenkeverteilung

27.10.2010, 13:50

Shortstop

Weihnachtsfeier Geschenkeverteilung

Hallo zusammen Wink

Ich habe folgende Aufgabe:

Bei einer Weihnachtsfeier bringt jeder der n Teilnehmer ein Geschenk mit. Diese werden in einen Sack gesteckt, gut durchmischt und wieder unter den n Teilnehmern verteilt.

Wie groß ist die Wahrscheinlichkeit, dass niemand das Geschenk erhält, das er mitgebracht hat?

Wie verhält es sich für $\begin{eqnarray*} n \to \infty \end{eqnarray*}$ ?

So, hier hab ich so ein paar Probleme mit. Vielleicht geh ich das Problem aber auch komplexer an, als es eigentlich ist.

Klar ist ja, dass die erste Person, die ein Geschenk bekommt, eine Chance von $\begin{eqnarray*} \frac{n-1}{n} \end{eqnarray*}$ hat, nicht ihr eigenes Geschenk zu bekommen.
Nun steh ich aber vor der Überlegung, dass es doch wichtig sein müsste, welches Geschenk Person 1 denn erhalten hat. Hat sie nämlich z.B. Geschenk 2 erhalten, hat Person 2 eine 100%ige Chance, nicht ihr Geschenk zu bekommen.

Somit müsste ich hier n Fallunterscheidungen allein für die erste Person machen, das kann ja nicht im Sinne des Erfinders sein?! Mein Kopf ist momentan ein bisschen blockiert, ich möchte es aber gerne nachvollziehen können.

Ohne Nachzudenken hatte ich mal spontan gedacht, wenn sich alle einfach auf die Geschenke stürzen hat jede Person eine Chance von $\begin{eqnarray*} \frac{n-1}{n} \end{eqnarray*}$ , nicht ihr eigenes zu bekommen. (Insgesamt also $\begin{eqnarray*} (\frac{n-1}{n})^n \end{eqnarray*}$ )

Das verhält sich dann im Grenzwert folgendermassen:
$\begin{eqnarray*} \lim_{n \to \infty} (\frac{n-1}{n})^n= \lim_{n \to \infty} (1- \frac{1}{n})^n = \frac{1}{e} \end{eqnarray*}$

Über ein paar Denkanstöße würd ich mich freuen smile

27.10.2010, 14:49

Shortstop

Auf diesen Beitrag antworten »

Leider zu spät zum editieren, ich sehe grade, ich habs in die Schulmathematik gepackt. Könnte mal jemand in die Hochschule verschieben? Wink

27.10.2010, 14:51

Huggy

Auf diesen Beitrag antworten »

RE: Weihnachtsfeier Geschenkeverteilung
Der Grenzwert stimmt. Für eine exaktere Herleitung siehe z. B. Wahrscheinlichkeit
dort letzter Beitrag von AD.
Schade, schade, dass Arthur Dent nicht mehr im Forum ist!

27.10.2010, 15:04

Shortstop

Auf diesen Beitrag antworten »

Ok. Ich nehme also bei n Geschenken den Laplace-Raum der Permutationen von 1 bis n.

Nun suche ich die Mächtigkeit der Menge von Permutationen ohne Fixpunkt bzw. die der Permutationen mit mind. einem Fixpunkt, beides hilft mir ja weiter.

Allerdings hatten wir die von AD erwähnte Formel noch nicht in der Vorlesung, ich müsste Sie also selbst beweisen. böse

Dann muss ich mich mal da durchquälen...

Und ja, wirklich schade dass er nicht mehr hier ist.

27.10.2010, 15:13

Huggy

Auf diesen Beitrag antworten »

Ich fürchte, ohne die (eigentlich gut bekannte) Siebformel geht es nicht.

27.10.2010, 15:20

René Gruber

Auf diesen Beitrag antworten »

Fakt ist, dass der Grundraum aus $\begin{eqnarray*} n! \end{eqnarray*}$ gleichwahrscheinlichen Permutationen besteht. Und egal, wie und womit (Siebformel etc.) man da rechnet: Die Wahrscheinlichkeiten sämtlicher Ereignisse aus diesem Grundraum können nur ganzzahlige Vielfache der Laplaceschen atomaren Wahrscheinlichkeit $\begin{eqnarray*} \frac{1}{n!} \end{eqnarray*}$ sein.

Das allein ist schon Begründung dafür, dass $\begin{eqnarray*} \left(\frac{n-1}{n} \right)^n \end{eqnarray*}$ nicht stimmen kann. Interessanterweise haut es zumindest im Grenzwert $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ dann doch wieder hin. Augenzwinkern

27.10.2010, 15:21

Shortstop

Auf diesen Beitrag antworten »

Ich fürchte auch. Buschmann

Dank dir trotzdem

27.10.2010, 15:23

wisili

Auf diesen Beitrag antworten »

RE: Weihnachtsfeier Geschenkeverteilung

Zitat:

Original von kvnb
Ohne Nachzudenken hatte ich mal spontan gedacht, wenn sich alle einfach auf die Geschenke stürzen hat jede Person eine Chance von $\begin{eqnarray*} \frac{n-1}{n} \end{eqnarray*}$ , nicht ihr eigenes zu bekommen. (Insgesamt also $\begin{eqnarray*} (\frac{n-1}{n})^n \end{eqnarray*}$ )

Wie nahe diese Ueberlegung der exakten Lösung ist, zeigt folgende Graphik in Prozenten, in Abhängigkeit von n (horizontale Achse, nur ganzzahlig):

[attach]16376[/attach]

(Der Fehler wird erst für ca. n>50 kleiner als 1%.)

27.10.2010, 15:23

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Das allein ist schon Begründung dafür, dass $\begin{eqnarray*} \left(\frac{n-1}{n} \right)^n \end{eqnarray*}$ nicht stimmen kann. Interessanterweise haut es zumindest im Grenzwert $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ dann doch wieder hin. Augenzwinkern

Richtig.
Aber mehr haben kvnb und ich auch nicht behauptet.

27.10.2010, 15:28

René Gruber

Auf diesen Beitrag antworten »

Es schien mir nur noch nicht klar genug herausgestellt, dass $\begin{eqnarray*} \left(\frac{n-1}{n} \right)^n \end{eqnarray*}$ tatsächlich nur eine Näherung ist.

P.S.: Komisch, dass man sich hier öfter gleich mal in einer Verteidigungshaltung wiederfindet, nur weil man einen interessanten Aspekt zum Problem beisteuern will, und überhaupt keinen angegriffen oder kritisiert hat. unglücklich

27.10.2010, 15:39

Shortstop

Auf diesen Beitrag antworten »

Hallo Rene! Okay, also weiss ich jetzt definitiv dass diese Lösung nicht die richtige ist. Wäre mir auch komisch vorgekommen. Umso bemerkenswerter, dass der Grenzwert übereinstimmt Big Laugh

Ich versuche immer noch das Problem irgendwie mit bekannten Mitteln erklären zu können, da ich eigentlich keine Lust habe, diese Siebformel zu beweisen. Ich frag mich auch, was unser Prof sich dabei gedacht hat ^^

27.10.2010, 15:41

Huggy

Auf diesen Beitrag antworten »

Nur keinen unnötigen Streit!
Wenn in einem Beitrag steht, dass etwas nicht stimmen kann

Zitat:

Das allein ist schon Begründung dafür, dass $\begin{eqnarray*} (\frac{n-1}{n})^n \end{eqnarray*}$ nicht stimmen kann.

ist es doch verständlich, dass man klarstellen möchte, dass man das auch nicht behauptet hat.

27.10.2010, 16:15

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von kvnb
Hallo Rene! Okay, also weiss ich jetzt definitiv dass diese Lösung nicht die richtige ist. Wäre mir auch komisch vorgekommen. Umso bemerkenswerter, dass der Grenzwert übereinstimmt Big Laugh

Ich habe noch mal nachgedacht, ob man den Grenzwert 1/e auch ohne Siebformel beweisen kann. Irgendwie sollte das gehen. Aber ich muss gestehen, mir ist nichts brauchbares eingefallen.

27.10.2010, 16:27

Shortstop

Auf diesen Beitrag antworten »

Ich habs jetzt mit Siebformel gemacht. Kann ich auch nix für dass wir die noch nicht hatten. Dafür ist der Weg wenigstens richtig!

Neue Frage »

Antworten »

Weihnachtsfeier Geschenkeverteilung

Verwandte Themen