Kleines Labyrinth - All different
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­gurations-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.

Die dritte Spalte kürzt die in der vierten angegebene Beschrei­bung ab. Und zwar steht "x-y-z" für "You are in a f(x) f(y) f(z) passages, all different", wenn die Funktion f wie folgt definiert ist:
f(M)  - maze of
f(L)  - little
f(Tg) - twisting
f(Ty) - twisty
Es gibt sechs Reihenfolgen der Buch­staben M, L und T und zwölf, wenn dem T noch ein g oder y angehängt wird. Reali­siert sind im Laby­rinth nur elf davon. Es fehlt die Kombi­nation L-Tg-M: "You are in a little twisting maze of passages, all different."

Man könnte nun leicht meinen, es sei eine kombi­nato­rische Spie­lerei, die Don Woods im Labyrinth mit den verschie­denen Gängen umgesetzt hat. Doch dann hätte er eine weitere Position vorsehen müssen. Etwa den Raum mit dem Batterie­automaten. Aber es gibt nur elf Posi­tionen, 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, wenn D von A nach K statt nach draußen und S von K nach A statt zum Batterie­automaten führte. Das so vom Rest der Höhle abge­löste Laby­rinth ohne Ein- und Ausgang beschreibt diese Tabelle:

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

Eine Richtung r=N,S,E,... in der Zeile m=A,B,C,... und der Spalte n=A,B,C,... besagt, daß von Position 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,E,... 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 es, stünden diese zehn Permu­tationen 0,1,2,...,9 für zehn ein­fache Dre­hungen eines anschau­lichen Objek­tes mit 11 Punkten. Aber irgendwie sieht es nicht danach aus. Deshalb will ich nur noch die nahe­liegende Frage beant­worten, welche Untergruppe aller Permu­tationen von A,B,C,...,K denn durch 0,1,2,...,9 aufge­spannt wird. Die Antwort ist glück­licher­weise einfach. Es ist die gesamte Gruppe. Jede belie­bige Permu­tation kann durch eine geeig­nete Reihen­folge der zehn Himmels­rich­tungen erzeugt werden.

Es spielt hier keine Rolle, daß man im Laby­rinth mit BACK einen Schritt zurück kann. Das ist auch nicht nötig, denn dau­ernde Wieder­holung ein und der­selben Rich­tung führt letzt­lich im Kreis herum. Die rück­wär­tigen Rich­tungen zu r=0,1,2,3,... bezeichne ich mit r'. Ich benö­tige hier nur vier
0'=(KGHDC)(FIBEJA)=029
1'=(HEC)(KDFGIJBA)=123
2'=(FE)(GDKBICJHA)=217
4'=(CGB)(DIEHJKFA)=423
von allen zehn inversen Permu­ta­tionen, um die zehn Paar­vertau­schungen
x=29=(EF)
y=39=(HK)
z=53=(EG)
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)
zu konstruieren, die bildlich dargestellt
        D               K
        |               |
F---E---G---C---I---J---H---A---B
sofort klar machen, daß jede beliebige Permu­tation aus ihnen erzeug­bar ist.

Übersicht | abenteuer (pdf, 163 KB)

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