Vorherige Aufgabe   Übersicht 2003   Nächste Aufgabe 

Lösungen der DENKmal-Knobelaufgaben

16. Aufgabe 2003

gestellt am 6. Oktober 2003 in der Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns

Türöffner

  Aufgabe   Lösung   Antwort 

Aufgabe

In einer alten Burg wurde sich für die Schatzkammer eine besondere Sicherheitstechnik ausgedacht. Zwei Türen liegen unmittelbar nebeneinander und sind von innen durch vier Riegel R1, R2, R3, R4 versperrt. Jeder Riegel versperrt eine der beiden Türen und man hat keine Anhaltspunkte über die genaue Position der Riegel.
Das könnte zum Beispiel so aussehen:

     Tür 1          Tür 2
    _________     _________
   |         |   |         |
   |         |   |         |
   |         | <=====R1=====>
  <=====R2=====> |         |
  <=====R3=====> |         |
   |         | <=====R4=====>
   |         |   |         |
___|_________|___|_________|____

Die Riegel werden durch drei Schalter 1, 2, 3 kontrolliert. Wird ein Riegel aktiviert, so gleitet er von der einen Tür zur anderen und versperrt die andere:

Schalter 1 aktiviert (zufällig)
R1 oder R2 oder R3 oder R4

Schalter 2 aktiviert (zufällig)
(R1 und R3) oder (R2 und R4)

Schalter 3 aktiviert (zufällig)
(R1 und R2) oder (R2 und R3) oder (R3 und R4) oder (R4 und R1)

Problem:
Finde eine möglichst kurze Folge von Knopfaktivierungen, die dich auf jeden Fall (und unabhängig von der Anfangskonfiguration) in die Schatzkammer bringt (d.h. alle Riegel sind auf einer Seite).

(eingesandt von Burkart)

Lösung

Betrachtet man alle kombinierten Möglichkeiten, die Riegel R1, R2, R3 und R4 entweder zu verschieben (1) oder unbewegt zu lassen (0), und die Hintereinanderausführung als Verknüpfung, erhält man eine kommutative Gruppe G der Ordnung 16. Schreibt man die Elemente als 4-Tupel, so ist (0,0,0,0) das neutrale Element, und jedes Element ist zu sich selbst invers. Insbesondere führt die zweimalige aufeinander folgende Aktivierung eines Schalters wieder zur Ausgangsstellung der Riegel.
Die von den Schaltern ausgelösten Riegelbewegungen können als Teilmengen von G beschrieben werden:
Schalter 1: A = {(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)}
Schalter 2: B = {(1,0,1,0), (0,1,0,1)}
Schalter 3: C = {(1,1,0,0), (0,1,1,0), (0,0,1,1), (1,0,0,1)}

Es sei F = (b1, c1, b2, a1, b3, c2, b4) eine Folge von Schalteraktivierungen mit {a1} ⊂ A, {b1, b2, b3, b4} ⊂ B und {c1, c2} ⊂ C.
Es kann dann gezeigt werden, dass jede Hintereinanderausführung von Teilfolgen von F weder das neutrale Element (0,0,0,0) noch dessen Komplement (1,1,1,1) ergibt.
Ausgehend von einer Riegelstellung werden deshalb durch die schrittweise Ausführung der Folgenelemente 7 weitere verschiedene Riegelstellungen erreicht und keine zwei von ihnen sind zueinander komplementär. Auch die Menge der 8 nicht erreichbaren Riegelstellungen ist komplementärfrei. Von den beiden Riegelstellungen, bei denen sich alle Riegel auf einer Seite befinden, wird also in jedem Fall genau eine durch die Folge F erreicht.

Antwort

Die Schalterfolge 2, 3, 2, 1, 2, 3, 2 bewirkt, dass nach höchstens 7 Schalteraktivierungen eine der Türen geöffnet werden kann.