All-Different-Labyrinth
Eigentlich kommt man leicht aus dem kleinen Labyrinth des 350-Punkte-Abenteuers mit den lauter verschie­denen Gängen heraus, weil alle Positionen anders beschrieben werden. Ohne den Raum mit dem Auto­maten (Dead End) sind es elf Posi­tionen:

A107M-Ty-LYou are in a maze of twisty little passages, all different.
B131M-Tg-LYou are in a maze of twisting little passages, all different.
C132L-M-TyYou are in a little maze of twisty passages, all different.
D133Tg-M-LYou are in a twisting maze of little passages, all different.
E134Tg-L-MYou are in a twisting little maze of passages, all different.
F135Ty-L-MYou are in a twisty little maze of passages, all different.
G136Ty-M-LYou are in a twisty maze of little passages, all different.
H137L-Ty-MYou are in a little twisty maze of passages, all different.
I138M-L-TgYou are in a maze of little twisting passages, all different.
J139M-L-TyYou are in a maze of little twisty passages, all different.
K112L-M-TgYou are in a little maze of twisting passages, all different.

Die erste Spalte gibt meine Bezeichnung, die zweite die Nummer gemäß der Höhlen-Konfi­gura­tions-​Datei wieder. Von B bis J bzw. 131 bis 139 entsprechen sie sich lückenlos. Der Eingang des Laby­rinthes liegt bei A (107), der Batterie­automat wird von K (112) aus erreicht. In der dritten Spalte ist die in der vierten angegebene Beschrei­bung abgekürzt. Und zwar steht x-y-z für „You are in a f(x) f(y) f(z) passages, all different“ mit:
f(M) für „maze of“
f(L) für „little“
f(Tg) für „twisting“
f(Ty) für „twisty“
Es gibt sechs Reihenfolgen der Buch­staben M, L, T und zwölf, wenn dem T noch ein g oder y angehängt wird. Reali­siert sind im Laby­rinth nur elf. Es fehlt L-Tg-M, womit „You are in a little twisting maze of passages, all different.“ als Beschreibung nicht vorkommt.

Man könnte nun leicht meinen, es sei eine kombi­nato­rische Spie­lerei, die Don Woods in diesem Labyrinth umgesetzt hat. Doch dann hätte er eine weitere reguläre Position vorsehen müssen, etwa den Raum mit dem Batterie­automaten. Aber es gibt nur elf, eine mehr als die zehn Rich­tungen N, S, E, W, U, D, NW, NE, SW und SE, mit denen von jeder Posi­tion aus jede der zehn übrigen erreich­bar ist, mit einer Ausnahme: Es gibt keine Verbin­dung zwischen A und K, denn von A geht es mit D nach draußen und von K mit S zum Batterie­automaten. Schließt man diese Lücke, verbindet also A und K durch D und S mitein­ander, so entsteht ein von der Außen­welt abge­trenntes Laby­rinth:

      ABCDEFGHIJK
A­SSWNESEUNWEWND
BW­SENWSWNEUDNSE
CNWU­NSWSWNEEDSE
DUDW­NESWENNWSES
ENENNWSE­EDSUWSW
FNSEDSE­WSWNENWU
GEWUSWDS­NWSENEN
HSENESDUNWN­SWEW
IDENEUWNSSE­SWNW
JSWNWEWNDSEUS­NE
KSSWNENWSENEWDU­

Die Richtung r=N,S,...,SE in Zeile m=A,B,...,K und Spalte n=A,B,...,K besagt, daß von Posi­tion m aus der Weg in Richtung r zur Posi­tion n führt. Verschiedene Richtungen führen zu verschieden Zielen und nie in den Ausgangsraum zurück, weshalb in der Tabelle die Diago­nale leer ist und in jeder Zeile jede Richtung genau einmal vorkommt. Daraus folgt nicht, daß dies für die Spalten auch der Fall ist. Es ist aber so: Jeder Raum wird von den zehn übrigen mit jeweils einer anderen Richtungsangabe erreicht. Damit bildet jede der zehn Rich­tungen r=N,S,...,SE eine Permu­tation der Posi­tionen A,B,C,...,K:
N  ist Permutation 0=(AJEBIF)(CDHGK)
S  ist Permutation 1=(ABJIGFDK)(CEH)
E  ist Permutation 2=(AHJCIBKDG)(EF)
W  ist Permutation 3=(AIEJDCFGB)(HK)
U  ist Permutation 4=(AFKJHEID)(BGC)
D  ist Permutation 5=(AKI)(BHD)(CJF)(EG)
NW ist Permutation 6=(AGHFJBDIKEC)
NE ist Permutation 7=(ADE)(BFICH)(GJK)
SW ist Permutation 8=(ACGDFHIJ)(BEK)
SE ist Permutation 9=(AEDJGIH)(BCKF)
Schön wäre, stünden diese zehn Permu­tationen 0,1,2,...,9 für zehn ein­fache Dre­hungen eines anschau­lichen Objek­tes. Doch dem ist nicht so, denn sie spannen den gesamten Raum aller Permuta­tionen der Posi­tionen A,B,...,K auf: Die Zyklen­längen der Permu­tationen p=0,1,2,4 ergeben für ihre Inver­sen p'
0'=(KGHDC)(FIBEJA)=029
1'=(HEC)(KDFGIJBA)=123
2'=(FE)(GDKBICJHA)=217
4'=(CGB)(DIEHJKFA)=423
Die Permutationen p=2,3,5 weisen neben einem Zyklus der Länge 2 einen der Länge 9 bzw. drei der Länge 3 auf. Damit ist
x=29=(EF)
y=39=(HK)
z=53=(EG)
woraus man leicht sieben weitere Paarvertauschungen
0x0'=(AJEBIF)(CDHGK)(EF)(KGHDC)(FIBEJA)=(IJ)
0y0'=(AJEBIF)(CDHGK)(HK)(KGHDC)(FIBEJA)=(DG)
0z0'=(AJEBIF)(CDHGK)(EG)(KGHDC)(FIBEJA)=(HJ)
1x1'=(ABJIGFDK)(CEH)(EF)(HEC)(KDFGIJBA)=(CG)
1z1'=(ABJIGFDK)(CEH)(EG)(HEC)(KDFGIJBA)=(CI)
2y2'=(AHJCIBKDG)(EF)(HK)(FE)(GDKBICJHA)=(AB)
4x4'=(AFKJHEID)(BGC)(EF)(CGB)(DIEHJKFA)=(AH)
gewinnt. Die bildliche Darstellung dieser zehn Vertau­schungen
        D               K
        |               |
F---E---G---C---I---J---H---A---B
macht deutlich, daß jede beliebige Permu­tation aus ihnen und damit aus p=0,1,...,9 erzeug­bar ist.

Damit ist das kleine All-Different-​Laby­rinth entzau­bert. Unge­fähr­lich so und so, denn man muß nur verhin­dern, vom West­ende der langen Halle mit S hineinzufallen. Nur wer trödelt und Batte­rien benö­tigt, muß durch dieses Laby­rinth. Für diesen Fall zeigt die Über­gangs­ta­belle stolze neun Wege, in nur vier Schritten von der Halle zum Auto­maten zu gelangen, nämlich über jeden der neun Räume B bis J einen. Zum Beispiel über F mit S-U-U-S. Auch Rückwege gibt es neun, zum Beispiel über I mit N-D-D-D. Mit Blick in die Höhlen-​Konfigu­rations-​Datei kann man sagen: Die Räume B bis J und der Batterie­raum sind die mit den höch­sten Num­mern 131 bis 140. Sie scheinen als letzte ange­klebt und dienen nur der Ver­wir­rung.

5. Wandertag | Übersicht | abenteuer (pdf, 163 KB)

... link (0 Kommentare)   ... comment