Zwei Tueren, vier Riegel
g.j.wo...@math.utwente.nl
Du bist in einer Zelle mit zwei Tueren eingesperrt. Die beiden Tueren
liegen unmittelbar neben einander und sind von aussen durch vier Riegel
R1, R2, R3, R4 versperrt. Jeder Riegel versperrt eine der beiden Tueren,
und Du hast keine Ahnung ueber die genaue Position der Riegel. Das
koennte zum Beispiel so aussehen:
Tuer1 Tuer2
_________ _________
| | | |
| | | |
| | <=====R1=====>
<=====R2=====> | |
<=====R3=====> | |
| | <=====R4=====>
| | | |
___|_________|___|_________|____
Die Riegel werden durch drei Knoepfe A, B, C kontrolliert. Wird ein Riegel
aktiviert, so gleitet er von der einen Tuer zur anderen und versperrt die
andere:
Knopf A aktiviert (zufaellig)
R1 oder R2 oder R3 oder R4
Knopf B aktiviert (zufaellig)
(R1 und R2) oder (R2 und R3) oder (R3 und R4) oder (R4 und R1)
Knopf C aktiviert (zufaellig)
(R1 und R3) oder (R2 und R4)
Problem: Finde eine moeglichst kurze Folge von Knopf-Aktivierungen, die Dich
auf jeden Fall (und unabhaengig von der Anfangskonfiguration) befreit (= alle
Riegel sind auf einer Seite).
--
GJ Woeginger, University of Twente
Torsten Rönsch
> Problem: Finde eine moeglichst kurze Folge von Knopf-Aktivierungen, die Dich
> auf jeden Fall (und unabhaengig von der Anfangskonfiguration) befreit (= alle
> Riegel sind auf einer Seite).
Verständnisfrage: Soll diese Folge garantieren, daß *am Ende* alle Riegel auf
einer Seite sind, oder genügt es, wenn dieser Zustand *spätestens* nach dem
letzten Knopfdruck erreicht wird? M.a.W., darf man sich nach jedem einzelnen
Knopfdruck probehalber gegen die Tür stemmen?
Gruß
Torsten
Joachim Scholz
spoiler
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
> Knopf A aktiviert (zufaellig)
> R1 oder R2 oder R3 oder R4
>
> Knopf B aktiviert (zufaellig)
> (R1 und R2) oder (R2 und R3) oder (R3 und R4) oder (R4 und R1)
>
> Knopf C aktiviert (zufaellig)
> (R1 und R3) oder (R2 und R4)
>
CBCACBC
Drei Typen:
I - II - III -
- - -
- - -
- - -
(0=offen)
Eigenschaften: III: ungerade Anzahl von Riegeln bei jeder Tuer, wird
nur von A geaendert(nach II,I oder 0).
II: zwei benachbarte Riegel haben gleichen Zustand, wird von B
geaendert (nach I oder 0)
I: Riegel abwechselnd auf Tuer 1 oder 2, wird von C geaendert (nach 0).
g.j.wo...@math.utwente.nl
Torsten Rönsch <roe...@ite.inf.tu-dresden.de> wrote:
# g.j.wo...@math.utwente.nl wrote:
#
#> Problem: Finde eine moeglichst kurze Folge von Knopf-Aktivierungen, die Dich
#> auf jeden Fall (und unabhaengig von der Anfangskonfiguration) befreit (= alle
#> Riegel sind auf einer Seite).
#
# Verständnisfrage: Soll diese Folge garantieren, daß *am Ende* alle Riegel auf
# einer Seite sind, oder genügt es, wenn dieser Zustand *spätestens* nach dem
# letzten Knopfdruck erreicht wird? M.a.W., darf man sich nach jedem einzelnen
# Knopfdruck probehalber gegen die Tür stemmen?
Antwort:
Alle Riegel sollen *spätestens* nach dem letzten Knopfdruck auf einer Seite
sein. (Nehmen wir an, dass eine Tuer von selber nach aussen aufspringt,
sobald sie von keinem Riegel mehr gehalten wird).
Zusatzaufgabe:
Beweise, dass es keine Folge von Knopf-Aktivierungen gibt, die garantiert,
dass *am Ende* alle Riegel auf einer Seite sind.
_____________________________________________________________
Gerhard J. Woeginger http://www.math.utwente.nl/~woeginge/
Gerhard Woeginger
#> auf jeden Fall (und unabhaengig von der Anfangskonfiguration) befreit (= alle
#> Riegel sind auf einer Seite).
#
# Verständnisfrage: Soll diese Folge garantieren, daß *am Ende* alle Riegel auf
# einer Seite sind, oder genügt es, wenn dieser Zustand *spätestens* nach dem
# letzten Knopfdruck erreicht wird? M.a.W., darf man sich nach jedem einzelnen
# Knopfdruck probehalber gegen die Tür stemmen?
Antwort:
Torsten Rönsch
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
I wrote:
> g.j.wo...@math.utwente.nl wrote:
>
> > Problem: Finde eine moeglichst kurze Folge von Knopf-Aktivierungen, die Dich
> > auf jeden Fall (und unabhaengig von der Anfangskonfiguration) befreit (= alle
> > Riegel sind auf einer Seite).
>
> Verständnisfrage: Soll diese Folge garantieren, daß *am Ende* alle Riegel auf
> einer Seite sind,
Dann gäbe es keine Lösung. Denn die Knöpfe B und C verändern immer genau 2 Riegel,
der Knopf A immer genau 1 Riegel. D.h., B und C sind paritätserhaltend, A ist
paritätsändernd. Bei der Ausgangskonfiguration LLRR (L...links, R...rechts) kann
man *nur* mit einer geraden Anzahl von A-Aktivierungen zur Befreiung kommen,
bei LLLR nur mit einer ungeraden. Also kann's keine universelle Folge geben,
die immer die Befreiungsstellung (LLLL oder RRRR) am Ende hat.
> oder genügt es, wenn dieser Zustand *spätestens* nach dem
> letzten Knopfdruck erreicht wird? M.a.W., darf man sich nach jedem einzelnen
> Knopfdruck probehalber gegen die Tür stemmen?
Dies sei also im folgenden vorausgesetzt.
Ich biete: CBCACBC.
Beweis, daß diese Folge immer zur Befreiung führt:
Fall 1: 2 Riegel sind auf der einen Seite, 2 auf der anderen.
1a: R1 und R3 sind auf derselben Seite.
Dann sind wir nach einmaligem Drücken von C befreit.
1b: Riegel, die auf derselben Seite sind, sind (zyklisch) benachbart.
("Zyklisch" soll heißen, daß R1 und R4 auch benachbart sind.)
Nach Anwendung von C ist das immer noch so.
Drücken von B ergibt nun entweder schon die Befreiungsstellung
oder die unter 1a beschriebene Situation, nach dem nächsten C
sind wir also spätestens befreit.
Fall 2: 3 Riegel sind auf der einen Seite, 1 auf der anderen.
Nach CBC ist das immer noch so (da B, C paritätserhaltend sind).
Drücken von A bringt uns entweder zur Befreiung oder in Fall 1.
Dort sind wir spätestens nach weiterem CBC befreit.
Schneller dürfte es nicht gehen. Für Fall 1 braucht man 3 Schritte,
da weder BB noch BC noch CB noch CC zwangsläufig zur Befreiung führen.
Fall 2 läßt sich nur per A über Fall 1 lösen, da B und C Fall 2 in
sich selbst überführen. Und jedes zusätzliche Drücken von A switcht
nur von Fall 1 in Fall 2 bzw. zurück (wenn es nicht *zufällig* zur
Befreiung führt).
Gruß
Torsten
Stephan Hohe
g.j.wo...@math.utwente.nl (g.j.wo...@math.utwente.nl) schrieb...
..
.
.
..
.
..
.
..
.
..
..
..
..
Für die Riegel gibt es vier mögliche Zustände:
Zustand A:
Drei Riegel vor der einen Tür, einer vor der anderen.
Man kann sich mit Glück durch Knopf A befreien.
Zustand B:
Zwei nebeneinanderliegende Riegel vor der einen Tür, die anderen zwei
vor der anderen. Man kann sich mit Glück durch Knopf B befreien.
Zustand C:
Zwei nicht nebeneinanderliegende Riegel vor der einen Tür, die anderen
zwei (ebenfalls nicht nebeneinanderliegenden) vor der anderen. Man kann
sich mit Glück durch Knopf C befreien.
Zustand X:
Alle Riegel vor einer Tür, die andere ist frei.
Durch Druck auf Knopf A ( -A-> ) erhält man:
A -A-> X oder B oder C = X|B|C
B -A-> A
C -A-> A
Druck auf Knopf B:
A -B-> A
B -B-> X|C
C -B-> B
Druck auf Knopf C:
A -C-> A
B -C-> B
C -C-> X
Insgesamt erhält man dürch Drücken von CBCACBC (mit Prüfen der Türen nach
jedem Knopfdruck):
A|B|C -C-> A|B|X -B-> A|X|C -C-> A|X -A-> X|B|C -C-> B|X -B-> X|C -C-> X
Spätestens nach sieben Knopfdrücken ist man also frei. Ob's noch kürzer
geht, weiß ich nicht, ich konnte aber jetzt nichts Besseres finden.
Stephan
--
Alle, die pauschalisieren, sind blöd!
Burkart Venzke
>geht, weiß ich nicht, ich konnte aber jetzt nichts Besseres finden.
Schneller kann es nicht gehen, da Du sonst nicht sicher alle Möglichkeiten
hattest.
Gruß, Burkart
(...der als Lösung die 2. und 3. jeweils getauscht hatte)
--
__________________________________________________________
News suchen, lesen, schreiben mit http://newsgroups.web.de
Burkart Venzke
>Beweise, dass es keine Folge von Knopf-Aktivierungen gibt, die garantiert,
>dass *am Ende* alle Riegel auf einer Seite sind.
Da reicht ja schon die "Bit-Betrachtung", daß man nicht weiß, ob eine gerade
oder ungerade Anzahl von Sperren verschoben werden müssen.
Gruß, Burkart
Heiner Veelken
> Du bist in einer Zelle mit zwei Tueren eingesperrt. Die beiden Tueren
> koennte zum Beispiel so aussehen:
>
>
> Tuer1 Tuer2
> _________ _________
> | | | |
> | | | |
> | | <=====R1=====>
> <=====R2=====> | |
> <=====R3=====> | |
> | | <=====R4=====>
> | | | |
> ___|_________|___|_________|____
>
> Problem: Finde eine moeglichst kurze Folge von Knopf-Aktivierungen, die Dich
> auf jeden Fall (und unabhaengig von der Anfangskonfiguration) befreit (= alle
> Riegel sind auf einer Seite).
An alle die, die Ihr das gelöst habt; wie seid Ihr das angegangen. Ich
habe mich 1/2 Stunde damit beschäftigt, mir ist nix eingefallen.
Ich verstehe nicht, wie man sich auf die Schnelle eine Lösungsstrategie
für dieses Problem entwickeln kann. Wie habt Ihr gedacht?
Gruss Heiner
Burkart Venzke
Hallo Heiner,
ich dachte folgendes:
- Es reicht, wenn die linke oder rechte Tür offen ist.
- Um sicher rauszukommen, müssen alle (8) Möglichkeiten einmal durchlaufen werden.
(Die erste haben wir in der Startposition.)
- Nur die 1. Regel ändert nur eine Tür, damit ist sie gut als Verbindung für die
jeweils 4 anderen Fälle zu gebrauchen.
- Die anderen 4 Fälle lassen sich gut durch abwechsende Anwendung der 2. und 3.
Regel erreichen.
So ungefähr hatte ich gedacht.