03: Not-so-secret Santa

  • Auch mein Lösungsansatz erfolgt über Permutationen:

    5 verschiedene Objekt können auf 5! = 120 Arten angeordnet werden. D.h. die sogenannte Permutationsgruppe hat 120 Elemente. Permutationen kann man in sog. Zyklen aufschreiben.

    Beipiele: (ABCDE) ; (AB)(CDE) ; (ABCD)(E) usw.

    Die ersten beiden sind tatsächlich günstig für unser Problem, aber der dritte Zyklus nicht, denn hier würde E auf sich selbst zeigen und das ist gegen die Spielregel.

    Damit sind aber nur die 5er- Zyklen also (ABCDE) ; (BACDE) usw. erfasst, denn das sind genau 24.

    Da ist aber kein Fall dabei, bei dem sich zwei Wichtel wechselseitig auswählen.

    Bsp: (AB)(CDE), also A zeigt auf B und umgekehrt, C zeigt auf D, D auf E und E auf C.

    Wie viele solche Permutationen mit einem Zweierzyklus und einem Dreierzyklus gibt es?

    Für jeden festen Zweierzyklus gibt es genau zwei: (AB)(CDE) und (AB)(CED)

    (Vorsicht: (AB)(ECD) = (AB)(CDE) usw.)

    Wie viele Zweierzyklen kann man aus 5 Elementen bilden?

    5 über 2 = 10

    Somit gibt es 2*10 = 20 solche Permutationen.

    Alle anderen sind nicht günstig: z.B. (A)(BCDE) ; (AB)(CD)(E) geht ja nicht, da niemand auf sich selbst zeigt.

    Insgesamt sind also 20 + 24 = 44 günstige Zyklen dabei.

    Demnach komme ich auf p = 44/1024 = 11/256 = 0,04296875

  • habe die von pierrot erwähnte Anzahl der Fixpunktfreien Permutationen rekursiv bestimmt. (Ich hoffe, das stimmt)

    Rekursive Ermittlung von P(k)

    •P(0) = 1 (per Definition)
    •P(1) = 0
    •P(2) = 1, Reihenfolge 2, 1
    •P(3) = 2, Reihenfolgen 2,3,1 und 3,1,2
    •P(4) = 4! – (4 über 4)*P(0) - (4 über 3) *P(1) - (4 über 2) * P(2) - (4 über 1) * P(3) = 24 – 1 – 0 – 6 – 8 = 9


    •P(5) = 5! – ∑_5i=1    (5 über i) * P (5-i) = 44


    •P(k) = k! – ∑_ki=1 (k über i) * P (k-i), für alle k >=2



    Die Idee dabei: von k! werden für alle i <= k alle Permutationen subtrahiert, in denen i Stellen Fixpunkte sind, das ist von der Anzahl her (k über i) multipliziert mit der Anzahl der Möglichkeiten, die übrigen k-i Plätze fixpunktfrei auf diese zu verteilen (P ( k-i ) )

  • Diese Aufgabe ließ sich sehr einfach nachprogrammieren. Ich nummeriere die Wichtel von 1-5 durch und da die Wichtel zufällig auf jemanden zeigen, kann man ihren Fingerzeig random generieren. Wenn man dann die Menge aller Fingerzeige bildet, und diese 5 Elemente enthält, endet die Prozedur.


    Der Code liefert in wenigen Sekunden Laufzeit recht genaue Ergebnisse für p (die Zweite Nachkommastelle reichte hier schon für die Wahl der Antwortmöglichkeit)


    Diese Lösung war für mich als Schüler deutlich einfacher und schneller, als mit fixpunktfreien Permutationen u.ä. zu argumentieren. Mich würde interessieren, ob es einen einfacheren Lösungsweg gibt, da die Aufgaben sich ja an Schüler richten. Aber anhand der Antwortmöglichkeiten vermute ich fast, dass die Aufgabensteller es absichtlich als Möglichkeit lassen wollten, es zu programmieren. ;)

  • Einfacher als ein Pyton-Programm? Ja das geht auch direkt in Excel ganz ohne VBA;-)
    Ich hatte in einer Tabellenzeile eine zufällige Permutation und Test dazu mit einfachen Formeln gebastelt und diese Zeile nach unten kopiert. Ein stabiles Ergebnis stellte sich bereits nach etwas über hundert Zeilen ein.

    --
    Frank


    Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell)

  • Diese Lösung war für mich als Schüler deutlich einfacher und schneller, als mit fixpunktfreien Permutationen u.ä. zu argumentieren. Mich würde interessieren, ob es einen einfacheren Lösungsweg gibt, da die Aufgaben sich ja an Schüler richten.

    Man muss für den Ansatz von MatheJürgen keine fixpunktfreien Permutationen kennen. Ich habe mir auch die Zyklen überlegt, die möglich sind, wenn ich mit einem beliebigen Wichtel (den ich oBdA "A" nenne) anfange. Den Wichtel, auf den A zeigt, nenne ich B (generell ist zu Beginn nur A festgelegt, die anderen vier Wichtel erhalten im Folgenden ihre Bezeichnung darüber, wer auf wen zeigt). Für den Fall (A->B->C->D->E->A) seien C, D und E die Wichtel, auf die B, C und D zeigen (die Pfeile geben jeweils an, wer auf wen zeigt). Dazu kann man sich die Wahrscheinlichkeit, dass B, C, D und E jeweils keiner der Wichtel ist, auf von den bis dahin betrachteten Wichteln schon jemand zeigt, recht leicht berechnen. Für A->B ist die Wahrscheinlichkeit 1 (da A der erste Wichtel ist, der betrachtet wird, kann auf B noch niemand anderes zeigen). Für B->C ist die Wahrscheinlichkeit, dass C ein noch "freier" Wichtel (und nicht A) ist, 3/4 (A ist ausgeschlossen, von den übrigen drei Wichteln sind noch alle frei), für C->D sind es 2/4 (A und B sind ausgeschlossen), für D->E 1/4 (nur noch ein Wichtel ist noch verfügbar), und die Wahrscheinlichkeit, dass E dann auf A zeigt, ist ebenfalls 1/4. Die Wahrscheinlichkeit für einen solchen Zyklus ist das Produkt dieser Einzelwahrscheinlichkeiten, also (3*2*1*1)/(4^4)=6/256.

    Dann betrachtet man den Fall (A->B->A) und (C->D->E->C). Die Wahrscheinlichkeit für A->B ist wieder 1, die, dass B dann von den 4 Wichteln genau A erwischt, ist 1/4. Die Wahrscheinlichkeit für C->D ist 2/4, weil D einer der beiden in diesem Fall noch nicht betrachteten Wichteln sein muss, und analog für D->E und E->A jeweils 1/4. Das Produkt der Einzelwahrscheinlichkeiten in diesem Fall ist 2/256.

    Nun fehlt noch der Fall (A->B->C->A) und (D->E->D). Hier ist die Wahrscheinlichkeit für A->B wieder 1, die für B->C ist 3/4, die für C->A 1/4, die für D->E und für E->D sind ebenfalls jeweils 1/4. Das Produkt der Einzelwahrscheinlichkeiten ist in diesem Fall 3/256.

    Die Wahrscheinlichkeit, dass einer dieser drei Fälle eintritt, ist die Summe der Wahrscheinlichkeiten für die jeweiligen Fälle, also (6+2+3)/256=11/256.


    Noch mal zur Klarstellung: Im Unterschied zu MatheJürgen lege ich in diesem Ansatz zu Beginn nur den Wichtel A fest, die Bezeichnungen B bis E ergeben sich dann daraus, wie die Wichtel aufeinander zeigen (wobei im zweiten Fall C und im dritten Fall D auch wieder oBdA als einer der verbliebenen Wichtel festgelegt werden). Die Zyklen, die zu betrachten sind, sind die gleichen wie in MatheJürgens Ansatz. Allerdings müssen (ABC),(DE) und (AB)(CDE) hier separat betrachtet werden, weil ich dadurch, dass ich Wichtel A beliebig festlege, sowohl den Fall, dass dieser in einem Zweierzyklus, als auch den, dass A in einem Dreierzyklus steckt, separat betrachten muss.

  • Eine Lösung, die ohne Programmieren oder Kenntnisse über fixpunktfreie Permutationen / Permutationszyklen auskommt, wäre davon auszugehen, dass A auf B zeigt und dann unter dieser Annahme (die aus Symmetriegründen egal sein sollte) durch Zählen die Wahrscheinlichkeit zu berechnen - es gibt noch 24 Möglichkeiten, die sich einfach auflisten lassen, bei denen niemand auf dieselbe Person zeigt:

    Macht 11 Möglichkeiten, bei denen nicht wiederholt wird, von 4^4=256 Gesamtmöglichkeiten, also 11/256.

  • Ich hab es etwas anders gemacht und die gesamten Möglichkeiten durchgezählt:


    Einmal die Möglichkeiten im "großen Kreis":


    ABCDE

    ABCED

    ABDCE

    ...
    AEDCB


    Macht 24 Möglichkeiten.


    Dann noch die Möglichkeiten bei einem "2er" und einem "3er" Kreis:


    Davon gibt es 10 mögliche 2er-Pärchen

    AB, AC, AD, AE, BC, BD, BE, CD, CE, DE


    wobei das 3er Pärchen jeweils 2 mögliche Reihenfolgen haben kann, also ABC oder ACB.


    Macht hierfür somit nochmal 20 Möglichkeiten.


    Summa summarum 44 von 4^5=1024 Möglichkeiten!

  • Statt Excel oder Phyton (siehe oben) lässt sich die Aufgabe mit einfacher Fallunterscheidung lösen. Hier meine Version zur Berechnung der Wahrscheinlichkeit für den Erfolg wenn wir die zunächst nicht benannten Wichtel nacheinander betrachten und am Ende die unabhängigen Wahrscheinlichkeiten addieren:


    Beginnen wir mit dem ersten Wichtel, den wir A nennen können. Er kann auf einen beliebigen Wichtel zeigen. Für ihn gilt also die Wahrscheinlichkeit 4/4=1 für den Erfolg.


    Der zweite Wichtel, den wir B nennen können, kann auch auf einen beliebigen Wichtel zeigen, allerdings müssen wir diesmal eine Fallunterscheidung vorbereiten:

    a) Mit 1/4 Wahrscheinlichkeit zeigt er auf A

    b) Mit 3/4 Wahrscheinlichkeit zeigt er auf einen der anderen Wichtel


    Für den dritten Wichtel müssen jetzt diese beiden 2 Fälle getrennt betrachtet werden:

    a) A und B sind bereits belegt, Damit muss der dritte Wichtel einen der beiden restlichen wählen und es ergibt sich die Wahrscheinlichkeit 2/4.

    b) Hier gibt es wieder 2 Möglichkeiten:

    b1) Der dritte Wichtel zeigt mit 1/4 Wahrscheinlichkeit auf A

    b2) Der dritte Wichtel zeigt mit 2/4 Wahrscheinlichkeit auf einen der beiden restlichen Wichtel.


    Der vorletzte Wichtel muss genau den letzten Wichtel treffen, ansonsten stünde für den letzten Wichtel kein freier Wichtel zur Verfügung. Für ihn gilt also ebenfalls die Wahrscheinlichkeit 1/4 für den Erfolg.


    Nun zum letzten Wichtel. Er muss genau den einen übrigen freien Wichtel treffen. Für ihn gilt also die Wahrscheinlichkeit 1/4 für den Erfolg.


    Insgesamt entstehen also 3 unabhängige Fälle:

    a) 1 * 1/4 * 2/4 * 1/4 * 1/4

    b1) + 1 * 3/4 * 1/4 * 1/4 * 1/4

    b2) + 1 * 3/4 * 2/4 * 1/4 * 1/4

    = (2+3+3*2)/4^4 = 11 / 256 = 0,04296875

    --
    Frank


    Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell)