Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

WaFa

War was wahr, oder was?

Auf der Insel "WaFa" leben "Wa"s, die immer die Wahrheit sagen, und "Fa"s, die immer lügen. Ausser diesen beiden Gruppen gibt es keine Einheimische auf der Insel.
Während unserer Inseldurchquerung fragen wir eine am Strassenrand stehende Gruppe Einheimischer nach dem Weg. Wir erhalten folgende Reaktionen der Personen A, B, C, D, E, und G: (Füllen Sie die Buchstaben "A,B,C,D,E,G" in die Kästchen ein, um das Rätsel zu vervollständigen)
A: "Sie müssen den rechten Weg nehmen, und D lügt."
B: "Falls D lügt, sagen E und die Wahrheit."
C: "Falls die Wahrheit sagt, müssen Sie den linken Weg nehmen. "
D: "Falls B oder G die Wahrheit sagt, dann lügt E. "
E: "A oder sagen die Wahrheit."
G: "B lügt, oder sagt die Wahrheit."


Wieder treffen wir Einheimische mit den schönen Namen A(1), A(2), ... , A(11). Sie bezichtigen sich gegenseitig der Lüge:
A(1): "A(6) lügt!".
A(6): "A(8) lügt!".
A(8): "A(9) lügt!".
A(1): "A(4) lügt!".
A(4): "A(3) lügt!".
A(3): "A(7) lügt!".
A(10): "A(6) lügt!".
A(10): "A(7) lügt!".
A(3): "A(2) lügt!".
A(2): "A(11) lügt!".
A(11): "A(5) lügt!".
A(5): "A(9) lügt!".
A(11): "A(4) lügt!".

Wer lügt, wer sagt die Wahrheit? Was haben bipartite Graphen mit diesem Rätsel zu tun?


Wieder treffen wir eine Gruppe Einheimischer B1, B2, B3, ... , B15. Diésmal sind sie voll des (Eigen-)Lobes:
B1: "B2 und ich sagen die Wahrheit".
B2: "B3 und ich sagen die Wahrheit".
B3: "B4 und ich sagen die Wahrheit".
B3: "B12 und ich sagen die Wahrheit".
B4: "B1 und ich sagen die Wahrheit".
B4: "B15 und ich sagen die Wahrheit".
B5: "B7 und ich sagen die Wahrheit".
B5: "B8 und ich sagen die Wahrheit".
B6: "B5 und ich sagen die Wahrheit".
B6: "B7 und ich sagen die Wahrheit".
B6: "B12 und ich sagen die Wahrheit".
B7: "B6 und ich sagen die Wahrheit".
B7: "B11 und ich sagen die Wahrheit".
B7: "B13 und ich sagen die Wahrheit".
B8: "B9 und ich sagen die Wahrheit".
B9: "B10 und ich sagen die Wahrheit".
B10: "B11 und ich sagen die Wahrheit".
B11: "B8 und ich sagen die Wahrheit".
B11: "B9 und ich sagen die Wahrheit".
B12: "B13 und ich sagen die Wahrheit".
B12: "B15 und ich sagen die Wahrheit".
B13: "B14 und ich sagen die Wahrheit".
B14: "B12 und ich sagen die Wahrheit".
B15: "B14 und ich sagen die Wahrheit".

Offensichtlich (?) gibt es hier verschiedene Lösungen. Warum müssen keiner oder vier oder acht oder elf oder zwölf oder alle fünfzehn die Wahrheit gesagt haben? Was hat dies mit den starken Zusammenhangskomponenten eines Digraphen zu tun?


Zurück Aussagenlogik
Erich Prisner
erstellt im Mai 2000.