Forum: Wissenschaft
Rätsel der Woche: Trenchcoat-Roulette in Pullach
SPIEGEL ONLINE

In Pullach ist die Welt noch in Ordnung: Tagsüber wird spioniert, und abends treffen sich die Agenten auf ein Helles in der Kneipe. Doch leider herrscht an der Garderobe ein ziemliches Durcheinander.

Seite 1 von 3
rotella 21.07.2018, 16:24
1. Fixpunktfreie Permutation

Ein Lieblingsthema vom Foristen Permissiveactionlink.

Nachdem das Thema bei jedem Wahrscheinlichkeitsrätsel hier im Forum auftaucht, hat es Herr Dambeck also nun auch endlich entdeckt, allerdings ohne überhaupt den einzig interessanten Clou bei diesem Problem zu erwähnen.

Da das Thema aber wie gesagt PAL "gehört", will ich hier nicht vorgreifen.

Beitrag melden Antworten / Zitieren
permissiveactionlink 21.07.2018, 17:16
2. #1, rotella

Stimmt, aber Herr Dambeck hat die Problematik ein bisschen dadurch abgewandelt, dass eben gerade nach den n i c h t fixpunktfreien Permutationen gefragt wird. Wenn ich mich nicht irre, ist die Lösung dann 1 - (!4/4!) = 0,625 bzw. 62,5 %. Da neun fixpunktfreie Permutationen von vier verschiedenen Elementen existieren, und 24 Permutationen insgesamt, findet man die Lösung auch ohne Fakultäts- und Subfakultätsschreibweise zu 1 - (9/24) = 15/24 = 5/8. Je mehr Mäntel von immer mehr Schlapphüten an der Garderobe abgegeben werden, desto mehr nähert sich die Wahrscheinlichkeit, dass mindestens ein Spion seinen eigenen Trenchcoat zurückerhält, dem Wert 1 - 1/e = 0,6321205588.... = 63,21...%. Die Subfakultät von n (!n), also die Anzahl fixpunktfreier Permutationen von n, ist zumindest in der klassischen Kryptographie von erheblicher Bedeutung. Die legendäre ENIGMA verschlüsselte immer dreizehn Paare von Buchstaben über Kreuz, also z.B. a durch X und x durch A, allerdings in jedem Verschlüsselungsschritt mit einem anderen Schlüsselalphabet. Kein Buchstabe konnte jemals durch sich selbst verschlüsselt werden ! In diesem besonderen Fall sank die Anzahl theoretisch möglicher Schlüsselalphabete von insgesamt 26! nicht nur auf !26, sondern auf äußerst bescheidene 25!!. (26! = 4,03*10^26, !26 = 1,48*10^26 und 25!! = 7,91*10^12), und die fixpunktfreie Verschlüsselung in jedem einzelnen Verschlüsselungsschritt ermöglichte (u.a.) den Alliierten den Einbruch in die geheime Kommunikation der Deutschen. Der Vorteil an Dambecks Aufgabenstellung besteht darin, dass man sie für kleine n auch ohne die Formel zur Herleitung der Subfakultät noch durch Ausprobieren lösen kann. (!n = n! * (1 - (1/1!) + (1/2!) - (1/3!) + (1/4!) - ......+ (-1)^n * (1/n!))).

Beitrag melden Antworten / Zitieren
ManeGarrincha 21.07.2018, 17:21
3. Enttäuschende Lösung

Dass das Problem bei der Anzahl n=4 einfach durch Auflistung aller Fälle gelöst werden kann, ist trivial. Enttäuschend ist, wie schon der erste Kommentar erwähnt, dass nicht die allgemeine Lösung präsentiert wird, bei n-> inf geht die Wahrscheinlichkeit gegen 1/e, das Problem heißt fixpunktfreie Permutation oder Derangement.

Beitrag melden Antworten / Zitieren
permissiveactionlink 21.07.2018, 18:11
4. #3, ManeGarrincha

Jain ! Zugegeben, für den kleinen, erlesenen Kreis der "üblichen Verdächtigen", die sich hier im Forum Samstags oder Sonntags tummeln, ist die Aufgabe vermutlich keine mathematische Herausforderung. Aber man sollte nicht vergessen, dass die Zahl der Leser, die sich an den Aufgaben versuchen, vermutlich sehr deutlich die kleine, überschaubare Zahl von regelmäßig bzw. sporadisch in diesem Forum postenden Foristen übersteigt. Sicher sind viele darunter, die sich mehr für eine schöne Nummer interessieren als für Zahlen und Permutationen. Das Rätsel sollte auch Nicht-Mathematikfreaks einen Einstieg in die Problematik ermöglichen, ohne zusätzlichen Frust bezüglich der Mathematik aufzubauen. Das Niveau muss ja nicht Woche für Woche auf dem der Mathematikolympiade liegen. Dann würde das hier auch eine ziemlich eintönige Angelegenheit. Ich sehe es genau andersherum : Besonders interessant wird es hier immer, wenn sich ausgehend von Dambeck Aufgabe deutlich schwierigere Fragen stellen. Da gibt es bisweilen verblüffende Überraschungen !

Beitrag melden Antworten / Zitieren
dasfred 22.07.2018, 23:52
5. Zu Nr.4

Ich danke für Ihren Verweis auf diejenigen, die eben nicht si tief in der Materie stecken. Bei vielen, wie bei mir, ist der Mathematik Unterricht eben Jahrzehnte her und die meisten Inhalte, hat man in Beruf und Alltag nie mehr abrufen brauchen. Von daher sind die kleinen Wochenend Rätsel immer ein Ansporn, längst verdrängtes Wissen wieder auszugraben, ohne gleich die Frustrationsschwelle zu überschreiten. Ein kleines Erfolgserlebnis zum Sonntag ist für uns mathematische Laien somit trotzdem zu erzielen. Und, wie man sieht, für die Kenner eben Ansporn zu tieferer Betrachtung.

Beitrag melden Antworten / Zitieren
permissiveactionlink 22.07.2018, 09:49
6. Tabula recta et al.

Ein Problem, das fixpunktfreie Permutationen nutzt, aber in seiner mathematischen Komplexität weit darüber hinaus geht, stellt das sogenannte lateinische Quadrat dar. Dabei müssen n verschiedene Elemente einer Zeile in n Zeilen so verteilt werden, dass in jeder Zeile und jeder Spalte alle n Elemente auftreten. Die einfachste Methode dafür besteht darin, in die erste Zeile A,B,C,D... zu schreiben, und diese Zeile in jeder Zeile darunter immer wieder eine Stelle weiter nach links zu bewegen. Da sich an dem entstehenden lateinischen Quadrat, das man auch Tabula recta nennt, durch Permutation seiner Zeilen und/oder Spalten nichts wesentliches verändert, zählen diese zeilen- bzw. spaltenpermutierten lateinischen Quadrate mit geordneter Kopfzeile alle nur als eine Lösung ("reduzierte lateinische Quadrate"). Ein besonders schönes lateinisches Quadrat der Größe 8 * 8 mit den Elemente 0 bis 7 hat der forist herrmann gottschewsi hier vor einiger Zeit vorgestellt. Es erfüllte zusätzlich die Eigenschaft, direkt übereinander oder nebeneinander alle möglichen Zifferpaare, also 01 bis 76 zu enthalten. Für vier Elemente gibt es vier reduzierte lateinische Quadrate (Können Sie die restlichen drei neben der Tabula recta finden ?). Es ist aber bis zum heutigen Tag nicht möglich exakt zu berechnen, wieviele reduzierte lateinische Quadrate der Größe 26 * 26 (Alphabetgröße, Kryptografie !) existieren. Man weiß nur : Für die erste Zeile gibt es eine Möglichkeit (im reduzierten Fall), für die zweite !26 Möglichkeiten, und für die unterste, letzte Zeile wieder nur eine einzige Möglichkeit. Wieviel es dazwischen gibt, weiß bisher keiner genau ! Die Anzahl dürfte allerdings hyperastronomisch sein, irgendwo bei vermuteten 10^320. Wer schon einmal mit der polyalphabetischen Substitution nach "Vigenère" verschlüsselt hat, verwendete dabei ganz sicher die Tabula recta. Damit ist die Chiffre sehr schnell knackbar, sofern genügend Geheimtext zur Verfügung steht. Vigenère selbst hat jedoch im Gegensatz dazu empfolen, die oberste Alphabetzeile zunächst zufällig zu permutieren, und erst dann die oberste Zeile sukzessive zu verschieben. Noch sicherer wird das Verfahren, wenn man ein völlig verwürfeltes lateinisches Quadrat als Verschlüsselungstafel verwendet.

Beitrag melden Antworten / Zitieren
einEi 22.07.2018, 10:17
7. Themengebiet klar?

Zitat von permissiveactionlink
Stimmt, aber Herr Dambeck hat die Problematik ein bisschen dadurch abgewandelt, dass eben gerade nach den n i c h t fixpunktfreien Permutationen gefragt wird.
Na ja, Übergang zur Komplementärwahrscheinlichkeit ist schwerlich eine Abwandlung der Thematik.

Beitrag melden Antworten / Zitieren
Joe Black 22.07.2018, 10:58
8. Mal eine Frage an die Mathe Cracks

Ich gehöre zu den Nicht-Mathematikern hier die den Artikel lesen und ganz gerne rätseln :-)
Vielleicht können mir ja die Experten hier im Forum helfen: warum ist die Lösung 5/8? Dass es 24 oder n! Mögliche Fälle gibt habe ich verstanden, aber warum wird in der Lösung davon ausgegangen, dass der 1. Agent einen falschen Mantel bekommt? Ist in den 24 Fällen nicht auch der Fall enthalten, dass A1 M1 ausgehändigt bekommt? Ich stehe auf dem Schlauch - danke für Aufklärung!

Beitrag melden Antworten / Zitieren
chrismuc2011 22.07.2018, 11:25
9.

Hat zwar nichts mit dem mathematischen Problem zu tun, aber in Pullach gibt es keine Kneipen, nur Wirtschaften:-)
Zudem würde ich mal vermuten wollen, dass es den Beschäftigten verboten ist sich miteinander im Umfeld des Geheimdienstes zu treffen.
Nicht umsonst wurde eine Unterführung unter die S-Bahnstrecke gebaut, damit sich der Verkehr nach Feierabend der "Spione" nicht staut und der KGB und Konsorten keine Fotos machen können.

Beitrag melden Antworten / Zitieren
Seite 1 von 3