Lösung: Außerirdische Angelegenheiten
Wir verwenden die folgenden Abkürzungen für die Individuen:
- F = Föderationsoffizier
- A = Alien, der das Raumschiff steuern kann
- a = Alien, der das Raumschiff nicht steuern kann
Aufgrund der Tatsache, dass die Anzahl der Föderationsoffiziere mindestens gleich der Anzahl der Aliens auf jedem Planeten sein muss, sind nur die folgenden 16 Zustände erlaubt:
| Nummer des Zustands | Planet 1 | Planet 2 |
|---|---|---|
| 1 | FFFAaa | - |
| 2 | FFFAa | a |
| 3 | FFFaa | A |
| 4 | FFFA | aa |
| 5 | FFFa | Aa |
| 6 | FFF | Aaa |
| 7 | FFAa | Fa |
| 8 | FFaa | FA |
| 9 | FA | FFaa |
| 10 | Fa | FFAa |
| 11 | Aaa | FFF |
| 12 | Aa | FFFa |
| 13 | aa | FFFA |
| 14 | A | FFFaa |
| 15 | a | FFFAa |
| 16 | - | FFFAaa |
Jetzt erstellen wir eine Liste aller möglichen Zustände und Flüge, wenn sich das Raumschiff auf Planet 1 befindet und nach Planet 2 fliegen wird. Beachte, dass wir Zustände, in denen es keine Piloten auf Planet 1 gibt, außer Acht lassen können. Dies sind die Zustände mit den Nummern 13, 15 und 16.
Beachte, dass die möglichen Flüge (maximal zwei Individuen, von denen mindestens einer ein Pilot ist) die folgenden sind: FF, F, FA, Fa, Aa und A. Wenn ein Flug jedoch zu mehr Aliens als Föderationsoffizieren auf einem der Planeten führen würde, ist dieser Flug nicht erlaubt. Zum Beispiel sind im Zustand 1 (alle Individuen auf Planet 1) die Flüge FF und F nicht erlaubt, da sie zu einem unerwünschten Zustand auf Planet 1 führen würden.
Wir kommen zu folgender Liste möglicher Zustände und Flüge, wenn sich das Raumschiff (bezeichnet mit S) auf Planet 1 befindet und nach Planet 2 fliegen wird:
| Nummer | Zustand | Mögliche Flüge | Resultierender Zustand | ||
|---|---|---|---|---|---|
| Planet 1 | Planet 2 | Planet 1 | Planet 2 | ||
| 1 | S FFFAaa | - | FA | FFaa | S FA |
| Fa | FFAa | S Fa | |||
| Aa | FFFa | S Aa | |||
| A | FFFaa | S A | |||
| 2 | S FFFAa | a | F | FFAa | S Fa |
| Aa | FFF | S Aaa | |||
| A | FFFa | S Aa | |||
| 3 | S FFFaa | A | F | FFaa | S FA |
| 4 | S FFFA | aa | FF | FA | S FFaa |
| A | FFF | S Aaa | |||
| 5 | S FFFa | Aa | FF | Fa | S FFAa |
| 6 | S FFF | Aaa | kein Flug möglich | ||
| 7 | S FFAa | Fa | FF | Aa | S FFFa |
| FA | Fa | S FFAa | |||
| Fa | FA | S FFaa | |||
| 8 | S FFaa | FA | FF | aa | S FFFA |
| Fa | Fa | S FFAa | |||
| 9 | S FA | FFaa | F | A | S FFFaa |
| FA | - | S FFFAaa | |||
| 10 | S Fa | FFAa | F | a | S FFFAa |
| Fa | - | S FFFAaa | |||
| 11 | S Aaa | FFF | Aa | a | S FFFAa |
| A | aa | S FFFA | |||
| 12 | S Aa | FFFa | Aa | - | S FFFAaa |
| A | a | S FFFAa | |||
| 14 | S A | FFFaa | A | - | S FFFAaa |
Jetzt können wir die folgenden Beobachtungen machen:
- Zustand 6 ist unmöglich. Dieser Zustand kann daher gestrichen werden.
- Jeder Zustand, der Teil der Lösung ist, muss sowohl einen eingehenden Flug als auch einen ausgehenden Flug haben (außer für den Anfangs- und Endzustand).
Das bedeutet, dass für jeden (zwischenliegenden) Zustand zwei ausgehende Flüge möglich sein müssen: der ausgehende Flug der Lösung und ein ausgehender Flug, der das Gegenteil des eingehenden Flugs der Lösung ist.
Deshalb können wir jeden (zwischenliegenden) Zustand, in dem nur ein Flug möglich ist, streichen. Dies sind die Zustände 3 und 5.
Aber wenn wir diese Zustände streichen, bedeutet das, dass "S FFFaa" und "S FFFa" nicht mehr als Teil der Lösung vorkommen können. Das bedeutet, dass für Zustand 7 einer der drei Flüge nicht mehr möglich ist und für Zustand 9 nur noch ein möglicher Flug übrig bleibt. Daher kann auch Zustand 9 gestrichen werden, was bedeutet, dass "S FA" nicht mehr als Teil der Lösung vorkommen kann. Darüber hinaus bedeutet dies, dass einer der vier Flüge für Zustand 1 unmöglich wird. - Flüge aus dem Anfangszustand mit nur einem Individuum sind sinnlos. Das liegt daran, dass im nächsten Schritt der einzige mögliche Flug die Rückkehr des Individuums ist. Daher kann der Flug durch A für Zustand 1 gestrichen werden.
- Flüge zum Endzustand mit nur einem Individuum sind unmöglich. Dieser Zustand kann nur auftreten, wenn dieses Individuum im vorherigen Schritt von Planet 2 nach Planet 1 gereist ist, was bedeutet, dass zu diesem Zeitpunkt bereits alle Individuen auf Planet 2 waren. Daher kann auch Zustand 14 gestrichen werden.
- Eine ähnliche Liste kann für die Zustände und Flüge von Planet 2 nach Planet 1 erstellt werden. Wir bezeichnen diese Zustände und Flüge als 1', 2', 3', ... 14'. Zum Beispiel bezeichnet Zustand 2 "S FFFaa" auf Planet 1 und "a" auf Planet 2. Analog dazu gibt Zustand 2' "a" auf Planet 1 und "S FFFaa" auf Planet 2 an.
Wenn wir die oben genannten Beobachtungen auf die Liste der Möglichkeiten anwenden, erhalten wir Folgendes:
| Nummer | Zustand | Mögliche Flüge | Resultierender Zustand | Bemerkungen | ||
|---|---|---|---|---|---|---|
| Planet 1 | Planet 2 | Planet 1 | Planet 2 | |||
| 1 | S FFFAaa | - | FA | FFaa | S FA | Gestrichen, weil Zustand 9 ("S FA") gestrichen wurde |
| Fa | FFAa | S Fa | Ergebnis ist Zustand 10' | |||
| Aa | FFFa | S Aa | Ergebnis ist Zustand 12' | |||
| A | FFFaa | S A | Gestrichen, weil es aus dem Anfangszustand sinnlos ist, nur ein Individuum fliegen zu lassen | |||
| 2 | S FFFAa | a | F | FFAa | S Fa | Ergebnis ist Zustand 10' |
| Aa | FFF | S Aaa | Ergebnis ist Zustand 11' | |||
| A | FFFa | S Aa | Ergebnis ist Zustand 12' | |||
| 3 | S FFFaa | A | F | FFaa | S FA | Gestrichen, weil es nur einen ausgehenden Flug gibt |
| 4 | S FFFA | aa | FF | FA | S FFaa | Ergebnis ist Zustand 8' |
| A | FFF | S Aaa | Ergebnis ist Zustand 11' | |||
| 5 | S FFFa | Aa | FF | Fa | S FFAa | Gestrichen, weil es nur einen ausgehenden Flug gibt |
| 6 | S FFF | Aaa | kein Flug möglich | Gestrichen, weil dieser Zustand nicht auftreten kann | ||
| 7 | S FFAa | Fa | FF | Aa | S FFFa | Gestrichen, weil Zustand 5 ("S FFFa") gestrichen wurde |
| FA | Fa | S FFAa | Ergebnis ist Zustand 7' | |||
| Fa | FA | S FFaa | Ergebnis ist Zustand 8' | |||
| 8 | S FFaa | FA | FF | aa | S FFFA | Ergebnis ist Zustand 4' |
| Fa | Fa | S FFAa | Ergebnis ist Zustand 7' | |||
| 9 | S FA | FFaa | F | A | S FFFaa | Gestrichen, weil Zustand 3 ("S FFFaa") gestrichen wurde |
| FA | - | S FFFAaa | Gestrichen, weil dies der einzige verbleibende ausgehende Flug ist | |||
| 10 | S Fa | FFAa | F | a | S FFFAa | Ergebnis ist Zustand 2' |
| Fa | - | S FFFAaa | Ergebnis ist der Endzustand | |||
| 11 | S Aaa | FFF | Aa | a | S FFFAa | Ergebnis ist Zustand 2' |
| A | aa | S FFFA | Ergebnis ist Zustand 4' | |||
| 12 | S Aa | FFFa | Aa | - | S FFFAaa | Ergebnis ist der Endzustand |
| A | a | S FFFAa | Ergebnis ist Zustand 2' | |||
| 14 | S A | FFFaa | A | - | S FFFAaa | Gestrichen, weil dieser Zustand nicht auftreten kann |
Jetzt können wir Folgendes sehen:
- Es gibt zwei Möglichkeiten, um vom Anfangszustand (Zustand 1) zu Zustand 2 zu gelangen:
- 1 → 10' → 2
- 1 → 12' → 2
- Es gibt zwei Möglichkeiten, um von Zustand 2' zum Endzustand zu gelangen.
- 2' → 10 → Endzustand
- 2' → 12 → Endzustand
- Es gibt genau einen möglichen Weg, um von Zustand 2 zu Zustand 2' zu gelangen:
- 2 → 11' → 4 → 8' → 7 → 7' → 8 → 4' → 11 → 2'
Wir schließen daraus, dass es vier mögliche Lösungen gibt, die unten aufgeführt sind.
Lösung 1
Planet 1 Flug Planet 2
F F F A a a
-- F a -->
F F A a F a
<-- F ----
F F F A a A a
-- A a -->
F F F A a a
<-- A ----
F F F A a a
-- F F -->
F A F F a a
<-- F a --
F F A a F a
-- F A -->
F a F F A a
<-- F a --
F F a a F A
-- F F -->
a a F F F A
<-- A ----
A a a F F F
-- A a -->
a F F F A a
<-- F ----
F a F F A a
-- F a -->
F F F A a a
Lösung 2
Planet 1 Flug Planet 2
F F F A a a
-- F a -->
F F A a F a
<-- F ----
F F F A a A a
-- A a -->
F F F A a a
<-- A ----
F F F A a a
-- F F -->
F A F F a a
<-- F a --
F F A a F a
-- F A -->
F a F F A a
<-- F a --
F F a a F A
-- F F -->
a a F F F A
<-- A ----
A a a F F F
-- A a -->
a F F F A a
<-- A ----
A a F F F a
-- A a -->
F F F A a a
Lösung 3
Planet 1 Flug Planet 2
F F F A a a
-- A a -->
F F F a A a
<-- A ----
F F F A a A a
-- A a -->
F F F A a a
<-- A ----
F F F A a a
-- F F -->
F A F F a a
<-- F a --
F F A a F a
-- F A -->
F a F F A a
<-- F a --
F F a a F A
-- F F -->
a a F F F A
<-- A ----
A a a F F F
-- A a -->
a F F F A a
<-- F ----
F a F F A a
-- F a -->
F F F A a a
Lösung 4
Planet 1 Flug Planet 2
F F F A a a
-- A a -->
F F F a A a
<-- A ----
F F F A a A a
-- A a -->
F F F A a a
<-- A ----
F F F A a a
-- F F -->
F A F F a a
<-- F a --
F F A a F a
-- F A -->
F a F F A a
<-- F a --
F F a a F A
-- F F -->
a a F F F A
<-- A ----
A a a F F F
-- A a -->
a F F F A a
<-- A ----
A a F F F a
-- A a -->
F F F A a a
Zurück zum Rätsel