Problem der vertauschten Hüte (Kombinatorik)

[@WhiteGandalfs]

Bevor ich mir die Details des Videos ansehe: Ich simuliere mal... Einer fängt an... Er nimmt seinen Hut und gibt ihn an einen der anderen... 5.. weiter. Frei wählbar. Der, dem er seinen Hut gibt, ist als nächstes dran. Er kann unter... 5 ... frei auswählen, denn der Anfänger darf nun auch Empfänger spielen. Frei wählbar unter den 5. Der nächste, der den Hut des zweiten bekommen hat, ist dran, seinen Hut weiterzugeben. Er kann das an ... 4... verbleibende Leute, die noch keinen neuen Hut bekommen haben. Frei wählbar. Der vierte, der soeben den Hut des dritten bekommen hat, kann noch unter 3 verbleibenden Leuten auswählen. Der fünfte unter 2. Der sechste, der den Hut vom fünften bekommen hat, muss seinen Hut an den fünften zurückgeben, denn alle anderen haben bereits einen neuen Hut bekommen, und der fünfte ist nun der letzte, der noch einen neuen braucht. Das ergibt 5 * 5! frei wählbare Optionen, das sind 600 Möglichkeiten. Das stimmt nicht mit dem überein, was ich am Ende des Videos sehe. Also wird das Gucken extra interessant: Wer irrt hier? Irgendwo muss ein Fehler versteckt sein... Hmmm... Haben wir beim Simulieren wirklich freie Wahl? Ja, doch, das schon. Aber können wir bei wiederholter freier Wahl wirklich unterschiedliche Verteilungen erzeugen? Oder sind die irgendwie voneinander abhängig? Ja, sie sind abhängig: Von allen, die soweit ihren Hut abgegeben haben, haben alle bis auf den ersten mit Sicherheit auch schon einen neuen erhalten. Bei jedem, der seinen Hut gerade weitergibt, gibt es die Möglichkeit, dass er seinen Hut an den Ringtausch-Starter zurückgibt und damit den Ring abschließt. Der Rest der Leute muss dann einen neuen Tauschring unter sich aufmachen. Wenn ich diese Abhängigkeiten simuliere, erhalte ich...: T1: freie Wahl 5 T2: freie Wahl 4 (a) oder T1 (b) T2a) T3: freie Wahl 3 (a) oder T1 (b) T2a-T3a) T4: freie Wahl 2 (a) oder T1 (b) T2a-T3a-T4a) T5: Zwingend T6, weil T6 keinen neuen Tauschring aufmachen kann; dann T6: T1 zwingend abschließend T2b) schließt Tauschring (T1,T2); neuer Tauschring (T3-T6) mit T3: freie Wahl 3 T2b) T4: freie Wahl 2 (a) oder T3 (b) T2b-T4a) T5: Zwingend T6, weil T6 keinen neuen Tauschring aufmachen kann; dann T6: T3 zwingend abschließend T2b-T4b) Zwingend dritter Tauschring unter T5 und T6, die keine Wahl haben T2a-T3b) schließt Tauschring (T1,T2,T3); neuer Tauschring (T4-T6) mit T4: freie Wahl 2 T2a-T3b) T5: Zwingend T6, weil T6 keinen neuen Tauschring aufmachen kann; dann T6: T4 zwingend abschließend T2a-T3a-T4b) schließt Tauschring (T1,T2,T3,T4); neuer Tauschring (T5-T6) ohne Wahl Wenn ich das jetzt addiere und multipliziere in seinen Abhängigkeitspfaden komme ich auf 5 * (1*(3 * (1 + 2)) + 4 * (1*(2) + 3 * (1 + 2))) = 5 * (1*(3 * 3) + 4 * (2 + 3 * 3)) = 5 * ( 9 + 4 * 11 ) = 5 * 53 = 265 ...und das ist das nächste unterschiedliche Ergebnis, nachdem ich das bereits auf Papier versucht habe :D (das andere: 216 - da hatte ich zwar die Pfade wie hier aufgestellt, die aber nicht in die richtigen Stellen des Gesamtausdrucks hineinmultipliziert...) Ich glaube, ich verlasse mich lieber aufs Programmieren und lasse das per Brute Force aus allen 6! Einzelvarianten herausschneiden... Zufälligerweise ist mein Ergebnis im dritten Anlauf zwar offenbar korrekt, aber verlassen würde ich mich in der Praxis dann doch nicht auf eine solche "intelligent-analytische" Lösung. Die ist mir einfach zu fehlerträchtig. Eine falsche Idee, ein Fehltritt in der Aufmerksamkeit - und alles liegt in Scherben. Für sowas hat man dann doch die Brute Force Rechenpower. Interessant an der Aufgabe ist die thematische Verwandtheit mit dem 100-Prisoner-Problem von letztens. Da ging's ja auch schon um "Ringe" - zwar nicht zum Tauschen, aber halt von der Organisation der Daten her. Ohne diese Anregung in den Hintergründen des Langzeitgedächtnisses wäre ich hier vielleicht nicht auf die Erleuchtung gekommen. Weiter solche Rätsel! Und das schönste am ganzen Video: Es führt mal wieder jeder Weg nach Rom! Mit völlig unterschiedlichen Denkweisen. Beeindruckend :D

[@renesperb]

Eine interessante und anspruchsvolle Aufgabe , sehr gut erklärt.

[@mpluftikuss]

Mein erster Gedanke: Person 1 tauscht mit Person 2-6, Person 2 tauscht mit Person 3-6 usw. Somit 5,4,3,2,1 Tausch = Total 15 Tauschversionen damit jeder mal jeden Hut gehabt hat. Jetzt mal schauen was mein Denkfehler ist.

[@schaff220]

die Lösung nennt sich auch subfakultät ;-) aber nett hergeleitet.

[@rudolfsbkm5250]

ich bin nur ein programmierer (learning-by-doing) und hätte dafür einfach ein kleines programm geschrieben (zb in python) um auf die zahl zu kommen: ----- import itertools # Alle Permutationen der Zahlen von 1 bis 6 permutationen = list(itertools.permutations(range(1, 7))) # Filter für Reihen, bei denen keine Zahl an Position i (1-basiert) gleich i ist gefiltertes_array = [ list(p) for p in permutationen if all(p[i] != i + 1 for i in range(6)) ] # Anzahl der verbleibenden Reihen anzahl_verbleibende_reihen = len(gefiltertes_array) # Ausgabe print("Anzahl der verbleibenden Reihen:", anzahl_verbleibende_reihen) ----- Anzahl der verbleibenden Reihen: 265

[@gregorgregorian2764]

sehr interessant... Bei Kombinatorik Aufgaben habe ich auch immer viel gemalt... (Bei “an Stelle 1 darf alles stehen außer einer 1" musste ich an die Verschlüsselungsmaschine ENIGMA denken: Anstelle von "A" steht jeder andere Buchstabe (außer "A")... schon klar, geht in eine ganz andere Berechnungsrichtung...26 hoch n vs. 25 hoch n; Unabhängigkeit...)

[@h.becker2129]

Rekursion ist schön, benötigt aber zur allgemeinen Lösung analytische Methoden ( z.B Erzeugende Funktion). Solche Probleme löst man am elegantesten mit den Inklusions/ Exkludionsprinzio

[@renesperb]

Was ich sehr interessant finde : für grosses n strebt die Anzahl der Möglichkeiten gegen n ! /e . Für n = 6 ist man bei 264.9 , also schon sehr nahe beim berechneten Wert 265 !

[@renesperb]

@@intarsienschrankzwetschgen4224 Richtig, ich habe nicht aufgepasst beim tippen.

[@trummler4100]

Ich hätte an 5! gedacht

[@conan7422]

Summe aller Permutationen minus Summe aller "Fehlvarianten" also: 6!-2^6+1+6 war mein erster Gedanke...

Vor vielen Jahren wurde ich mit dem Problem der vertauschten Briefe konfrontiert: Wie viele Möglichkeiten gibt es, sämtliche (8) Briefe in ein falsches Kuvert zu stecken? Ich bin auch vorgegangen wie im Video beschrieben. Also 1 Brief 1 Kuvert - 0 Möglichkeiten 2 Briefe 2 Kuverts - 1 Möglichkeit 3 Briefe 3 Kuverts - 2 Möglichkeiten 4 Briefe 4 Kuverts - 9 Möglichkeiten. Und dann ist mir diese Gesetzmäßigkeit in meiner Tabelle aufgefallen: 0 x 2 + 1 = 1 1 x 3 - 1 = 2 2 x 4 + 1 = 9. Und dann konnte ich weiterrechnen: 9 x 5 - 1 = 44. Da habe ich dann noch das Ergebnis verifiziert (also alle Möglichkeiten gelistet), wonach klar war: 44 x 6 + 1 = 265 265 x 7 - 1 = 1854 1854 x 8 + 1 = 14833. Und dann war ich (als Nichtmathematiker) stolz wie Oskar. 🤗

[@mariojacob6799]

Gibt es auch eine Formel, mit der ich z.B. n(20) ausrechnen kann, ohne die Werte von A(19) und A(18) zu kennen??? Die Tabelle ist ja schon ok, aber bei größeren n wird es schwierig... also wenn z.B. Excel nicht verfügbar ist 🤔

[@Mariusde]

Gibt es! Wie schon von einem anderen User erwähnt, handelt es sich bei der Tabelle um die sogenannten Subfakultäten. Im Gegensatz zur Fakultät steht bei der Subfakultät das Ausrufezeichen vor der Zahl und die Formel lautet: !n = n! * Summe von k=0 bis n (((-1)^k)/k!)

[@MrGeorge1896]

Guck mal bei Wikipedia mit Stichtwort "Fixpunktfreie Permutation". Dort gibt es eine Formel. de.wikipedia.org/wiki/Fixpunktfreie_Permutation#Anzahl

[@konraddapper7764]

Ich verstehe nicht wo das problem liegt 6 kann man einfach partitioniern mit minder partition größe 2 bilden das spaltete das problem in 4 duetlich liechter nicht überlappenen Fälle auf diese entsprech 'vertauschungskreisen' 6= 6 6 = 2+4 6 = 3+3 6=2+2+2 im Fall 6 gibt es offen sich 5 ! = 120 möglichkeiten im Fall 2+4 gibt es bin(6,2)* 1! *3 != 15* 6 =90 im Fall 3+3 gibt es bin(6,3)*2! * 2! /2!= 20*2 *2/2= 40 in Fall 2+2+2 gibt es bin(6,2) *1! * bin(4,2)*1! *1!/ 3! = 15 *6*1/ 6 =15 auf addiert sind das also 265 möglcihkeiten

[@taflo1981]

Das war auch mein erster Rechenweg. Hat im Kopf deutlich weniger als die im Video erwähnten 5 Minuten gedauert. Ein anderer einigermaßen schneller Rechenweg ist Inklusion-Exklusion. Die Anzahl der Permutationen von n Elementen ohne Fixpunkte ist nämlich bin(n,0)*n! - bin(n,1)*(n-1)! + bin(n,2)*(n-2)! - ... + (-1)^(n-1)*bin(n,n-1)*1! + (-1)^n*bin(n-n)*0! Dabei steht jedes bin(n,k)*(n-k)! für die Anzahl bin(n,k) an Teilmengen der Größe k, für jede solche Teilmenge multipliziert mit der Zahl (n-k)! der Permutationen, bei denen die Zahlen dieser Teilmenge (aber nicht unbedingt *nur* diese Zahlen) Fixpunkte sind. Durch die alternierenden Vorzeichen werden am Ende genau die Permutationen ohne Fixpunkt gezählt. Beweis dieser Behauptung: Zu einer beliebige Permutation f nennen wir K die Menge ihrer Fixpunkte und schreiben k=|K|. Dann wird f für jedes m zwischen 0 und k (beides inklusive) im Summanden bin(n,m)*(n-m)! genau bin(k,m)-mal gezählt, nämlich jeweils einmal für jede m-elementige Teilmenge von K. Das bedeutet, das f insgesamt summe(m=0 bis k) bin(k,m)*(-1)^m = summe(m=0 bis k) bin(k,m)*(-1)^m*1^(k-m) mal gezählt wird. Für k=0 ist diese Summe 1 (sie hat nur einen Summanden und der ist 1). Für k>0 ist die Summe nach dem binomischen Lehrsatz (1-1)^m = 0^m = 0. Es werden bei der oben genannten Formel also alle Permutationen ohne Fixpunkt genau einmal gezähl und alle mit Fixpunkten werden nicht gezählt. In der Formel kann man die ersten beiden Summanden auch weglassen, weil diese identisch sind (wobei einer addiert und der andere subtrahiert wird). In unserem Beispiel haben wir bin(6,2)*4! - bin(6,3)*3! + bin(6,4)*2! - bin(6,5)*1! + bin(6,6)*0! = 15*24 - 20*6 + 15*2 - 6*1 + 1*1 = 360 - 120 + 30 - 6 + 1 = 265.

[@user-qs1xz2mx6f]

Tricky!

[@silviagreiner3435]

😅😅

[@zuckerfee9928]

Folgen, Reihen, Induktion.... da habe ich aufgegeben.....nicht jedem ist' s gegeben.... manch einer liegt daneben!

[@Mathegym]

Am Reimen hingegen ist Ih'n gelegen ;-) Es sollten die Begrifflichkeiten zur Aufgabe doch nicht verleiten Noch ein Versuch wäre es wert Hab ich's doch ausführlich erklärt

[@aligator4920]

6!!