Problem der vertauschten Hüte (Kombinatorik)

Hier geht's zu meiner Lernplattform: mathegym.de
• 6 Herren und 6 Zylinde...

[@renesperb]

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

[@marcop4107]

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.

[@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 interessat 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 !

[@conan7422]

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

[@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

[@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

[@trummler4100]

Ich hätte an 5! gedacht

[@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