Verteilungsrechnung beim Wichteln
Sicher kennt jeder den Geschenkaustausch durch Wichteln Jeder zieht einen Namen und muss der Person dann anonym ein Geschenk machen
Jetzt zu meiner frage Bei einer geraden zahl an Teilnehmern ist es leicht vorstellbar 1 beschenkt 2 und umgekehrt 3 beschenkt 4 und umgekehrt
Klar zieht man sich im seltensten Fall gegenseitig aber ich schreibe es jetzt so um meine Frage besser zu erklären:
Wie ist es bei einer ungeraden Zahl an teilnehmern 1 beschenkt 2 und umgekehrt
3 beschenkt 4 und umgekehrt dann würde der 5. weder jemanden haben der noch nicht beschenkt wird noch bekommt er selber ein Geschenk
Geht man aber Folgender maßen vor geht es auf
1 schenkt 2
2 schenkt 3
3 schenkt 4
4 schenkt 5
5 schenkt 1
Meine Frage ist jetzt warum geht es auf diese Weiße auf und vorher mit der selben Personenzahl nicht?
3 Antworten
Ich versuche mich mal an der mathematischen Erklärung, die KlyX84 erwähnte...
Was wir hier betrachten, sind sogenannte Permutationen. Wir haben eine Menge von 5 Personen, die wir der Einfachheit halber als M = {1,2,3,4,5} bezeichnen.
Eine Permutation ist eine bijektive Funktion f von M nach M.
Das heißt einfach, dass für jedes x aus M der Wert f(x) ebenfalls in M liegt und dass jeder Wert in M genau einmal getroffen wird.
Ein Beispiel für eine solche Permutation wäre:
f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 3
f(5) = 5
Offensichtlich trifft diese Funktion jeden Wert in M genau einmal.
Eine Permutation f interpretieren wir wie folgt:
f(x) = y ist gleichbedeutend mit x schenkt y.
So, nun schauen wir uns deinen ersten Vorschlag an. Dieser lautet:
f(1) = 2
f(2) = 1
f(3) = 4
f(4) = 3
f(5) = 5
Das ist offenbar eine Permutation. Aber sie hat einen sogenannten Fixpunkt, denn die 5 wird auf sich selbst abgebildet. Das bedeutet, Person 5 beschenkt sich selber. Diese Option ist bei Permutationen nicht ausgeschlossen, denn sogar der Spezialfall f(x) = x für alle Elemente x der Menge M (jeder beschenkt sich selbst) ist eine Permutation.
Das Problem ist also, dass es Permutationen gibt, die einen Fixpunkt haben. Umgekehrt gibt es aber auch immer fixpunktfreie Permutationen, eine davon hast du ja bereits genannt. Daher kann die eine Permutation eine für uns passende Lösung sein und die andere nicht.
Hi,
das eine ist eine Reihe - die funktioniert mit beliebig vielen Personen (in dem Fall deinen 5). Diese Reihe hat die Voraussetzung, dass eine Person immer die nächste Person in der Reihe beschenkt und die Letzte somit die Erste.
Bei der anderen Variante, bei der es mit 5 nicht ausgeht, hast du eine ganz andere Voraussetzung. Dort setzt du nämlich voraus, dass eine Person die gleiche Person beschenkt, die ihn ebenfalls beschenkt. Für diese Funktion brauchst du also eine gerade Anzahl an Personen, damit es klappt ;)
Wie gesagt, das liegt an den Vorgaben, die du setzt:
in der Variante 1 sagst du, dass eine Person immer eine andere Person beschenkt. So ist es komplett unabhängig ob die Anzahl der Personen ungerade ist oder nicht.
In der Variante 2 sagst du, dass zwei Personen sich gegenseitig beschenken. Die Vorgabe ist also, dass immer 2 Personen zusammen eine "Einheit" bilden. Man kann die Aufgabe also in zwei Teile splitten: 1. Teile die Personen in 2er-Gruppen auf 2. Jede Gruppe tauscht untereinander Geschenke aus
Der zweite Teil ist also quasi das Gleiche Prinzip wie bei der ersten Variante 1: insgesamt tauschen alle Personen untereinander Geschenke aus. Limitierend ist aber Teil 1 der Aufgabe: die Aufteilung in 2er Gruppen. Diese Voraussetzung kann nur mit einer geraden Anzahl erfüllt werden. In der Variante 1 ist diese Vorgabe nicht vorhanden.
Dazu gibt es bestimmt noch eine total mathematische Erläuterung - vermute ich - kann ich aber leider nicht liefern :D
Das funktioniert einfach nicht dadurch muss nämlich 5 sich selber gezogen haben und das ist ja gegen die 'regeln'
aber Variante 2 mit der Reihe zeigt doch das es irgendwie gehen muss
Ja was ich aber nicht verstehe es sind bei beiden varianten gleich viele Personen
bei einer variante bekommt jeder genau ein Geschenk und jeder verschenkt genau ein Geschenk
das kann ja schlecht mal funktionieren und mal nicht
warum bleibt bei der anderen variante da einer extra den man absolut da nicht hineinbekommt obwohl das andere beispiel ja beweißt das es geht