Multiple Choice Optionen:- 5
- 6
- 24
- 25
- 30
- 31
- 32
- 35
- 36
- 72
- 96
- 120
- 153
- 216
- 255
- 256
- 265
- 304
- 567
- 599
- 600
- 720
- 873
- 1024
- 5039
- 7776
- 46655
- 181209
- keine der angegebenen Anzahlen stimmt
Lösung ausblenden
Die richtige Anzahl ist 265.
Hier zwei Möglichkeiten, wie man draufkommt.
1. Möglichkeit
Du schreibst alle Möglichkeiten auf, passt dabei höllisch auf, dass Du keine vergisst und keine doppelt zählst, und "schon" hast Du die richtige Lösung.
Bei kleiner Schrift und guter Platzeinteilung passen alle 265 Möglichkeiten sogar auf ein DIN A4 - Blatt. 
2. Möglichkeit
Du gehst iterativ vor und versuchst in zwei Schritten von "Wie wäre es bei zwei Rätseln?" und "Wie wäre es bei drei Rätseln?" auf "Wie ist es dann bei vier, fünf usw.?" zu schließen.
Schritt 1: Bei 2 vertauschten Rätseln (sagen wir Nr. 19 und 20) gibt es genau eine Möglichkeit (nämlich 20-19). Bei 3 vertauschten Rätseln (sagen wir Nr. 19, 20, 21) gibt es genau 2 Möglichkeiten (nämlich 20-21-19 und 21-19-20).
Jetzt kennen wir also die gesuchten Anzahlen A, wenn es sich um 2 bzw. um 3 vertauschte Rätsel handeln würde:
A(2) = 1 und A(3) = 2 ... So weit ist die Sache noch locker überschaubar.
Schritt 2: Nimm mal an, für n Rätsel und auch für n - 1 Rätsel hättest du das Problem bereits gelöst und die gesuchten Anzahlen A(n) und A(n - 1) herausgefunden. (Für den speziellen Wert n = 3 und n - 1 = 2 hast Du das ja auch, nämlich in Schritt 1.) Dann überlegest Du für die nächst höhere Anzahl n + 1: Kommt zu den bereits vorhandenen n Rätseln noch ein weiteres samt seinem zugehörigen Türchen dazu, so gibt es genau zwei Varianten, wie schließlich alle n + 1 Rätsel vertauscht sind, nämlich:
Variante 1: Sind alle bisherigen n Rätsel bereits gemäß Aufgabenstellung vertauscht, gibt es hierfür genau A(n) Möglichkeiten. Kommt jetzt noch eines hinzu, tauscht man das neue einfach mit irgendeinem der n bereits vorhanden Rätsel.
Anzahl der Möglichkeiten von Variante 1: n * A(n)
Variante 2: Wenn unter den n Rätseln noch genau eines bei seinem richtigen Türchen ist (n Möglichkeiten) aber alle übrigen n - 1 Rätsel gemäß Aufgabenstellung vertauscht sind (jeweils A(n - 1) Möglichkeiten), geht es auch: Kommt nun noch ein neues dazu, tausche es einfach mit demjenigen aus, das zuvor beim richtigen Türchen war.
Anzahl der Möglichkeiten von Variante 2: n * A(n - 1)
Nach kurzem Überlegen erkennt man, dass das die einzigen Varianten sind, mit denen schließlich alle n - 1 Rätsel vertauscht sind, und dass diese beiden Varianten wirklich alle Fälle überschneidungsfrei erfassen.
Fazit:
Mit der "Iterationsformel" A(n + 1) = n * A(n) + n * A(n - 1) startest Du bei A(2) = 1 und A(3) = 2 und gelangst in wenigen Schritten bis zu A(6) = 265 (und wenn Du willst auch noch weiter, was übrigens nicht uninteressant ist...)
P.S. Du könntest die Iteration sogar schon bei n = 2 und n - 1 = 1 mit A(1) = 0 beginnen.
P.P.S. Übrigens haben sich auch schon vor Dir und mir kluge Köpfe wie Euler und Bernoulli mit ähnlichen Problemen (vertauschte Briefe) befasst und sind dabei auch auf ähnliches gestoßen.
