Welche Flasche ist vergiftet?
Wie man eine Party vor einem Mordversuch rettet.
Ein König will ein rauschendes Fest feiern. 1000 Flaschen Wein werden geöffnet. Doch zwei Stunden vor dem Fest erfährt er, dass eine der 1000 Flaschen vergiftet ist. Bloss welche? Es stehen ihm nur 10 Vorkoster zur Verfügung und das Gift wirkt in knapp zwei Stunden. Vorausgesetzt, das Gift wirkt auch dann, wenn es mit beliebig vielen anderen Proben verdünnt ist: Mit welcher Strategie kann man die 1000 Flaschen derart testen, dass man rechtzeitig bei Festbeginn weiss, welche Flasche vergiftet ist?
Betrachten wir die Aufgabe zunächst in einer vereinfachten Variante mit 4 Flaschen und 2 Vorkostern. Der erste Vorkoster bekommt eine Mischung der ersten 2 Flaschen; der zweite Vorkoster bekommt eine Mischung aus den Flaschen 1 und 3.
| Vorkoster | Flasche 1 | Flasche 2 | Flasche 3 | Flasche 4 |
| 1 | x | x | ||
| 2 | x | x |
So gibt es eine eindeutige Lösung: Sterben beide Vorkoster, dann war das Gift in Flasche 1; stirbt keiner, war das Gift in Flasche 4; stirbt nur Vorkoster 1, war das Gift in Flasche 2, und erwischt es nur Vorkoster 2, war Flasche 3 vergiftet.
Kehren wir nun zurück zum König und den 1000 Flaschen. Oder nehmen wir 1024 Flaschen, denn das entspricht 210 (oben zeigten wir die Lösung für 22 = 4).
Man unterteilt die aufgereihten Flaschen 1 bis 1024 zuerst in die Hälfte und gibt dem ersten Vorkoster eine Mischung aus den ersten 512 (das entspricht den ersten zwei Flaschen im obigen Beispiel). Dann bekommt der zweite Vorkoster eine Mischung aus 1 bis 256 und 513 bis 768 (das erste und dritte Viertel). Dann teilt man die Gesamtzahl in Achtel, Sechzehntel und so weiter. Am Ende darf der letzte Vorkoster noch schauen, ob es eine ungerade oder gerade Flasche betrifft.
Sie wollen eine Formel? Gerne: zi = 0 bedeute, dass Vorkoster i stirbt, und zi = 1, dass er überlebt. Dann ist das Gift in Flasche
z129+ z228+ z327+ z426+ z525+ z624+ z723+ z822+ z921+ z1020 +1.
Aufgrund des Zustands der Vorkoster können Sie nun eindeutig ableiten, welche Flasche betroffen ist. Überlebt etwa der erste Vorkoster (z1 = 1), ist keine unter den ersten 512 Faschen betroffen. Wenn alle zehn Vorkoster tot umfallen, kann man einfach Flasche 1 rausnehmen und dann das rauschende Fest in vollen Zügen geniessen. Und ja: In Gesellschaftssystemen, wo das Leben des einzelnen etwas zählt, würde man alle Flaschen sicherheitshalber entsorgen.
