Anlässlich seines 20-jährigen Thronjubiläums veranstaltet der umstrittene, aber sehr gerissene König eine dekadente Feier, zu der er all seine Vertrauten und Unterstützer einlädt.
Bei den Vorbereitungen der Feierlichkeiten lässt sich der König nicht lumpen und lässt unter anderem 1000 Flaschen des besten Weins aus allen Ecken des Königreichs einfahren.
Der Giftanschlag
Allerdings hat der König auch seine Feinde. Und so schleicht sich eines Nachts ein Attentäter mit einer Ampulle Gift in den Weinkeller, um den edlen Wein für die Feier zu vergiften.
Zum Glück für den König konnte eine aufmerksame Wache der Attentäter fassen, nachdem er nur eine einzige Flasche vergiften konnte. Leider ist nicht bekannt, welche der 1000 Weinflaschen vergiftet wurde.
Das sichergestellte Gift ist extrem stark, sodass selbst ein einziger Schluck bei einer Verdünnung von 1:1.000.000 noch tödlich wirkt. Die Wirkung des Gifts tritt erst nach 5 Tagen ein.
Der gerissene König möchte die Feierlichkeiten in einer Woche allerdings weder absagen, noch möchte er den teuren Wein wegschütten. Daher entschließt er sich, 10 Gefangene aus seinen Kerkern holen zu lassen und erklärt:
“999 fast randvolle Flaschen werden auch genügen. Und ein paar freie Kerkerplätze können wir ebenfalls gut gebrauchen.”
Wie plant der König, die vergiftete Weinflasche zu finden?
Tipp
Es gilt
2^{10}=1024>1000.
Lösung
Wie man dem Tipp vermutlich entnehmen kann, besteht die Idee des Königs darin, die 1000 Flaschen Wein mit Hilfe der Binärdarstellung von Zahlen zu kodieren.
Wie genau funktioniert das?
Zunächst werden die 1000 Weinflaschen von 1 bis 1000 durchnummeriert.
Auch die zehn Gefangenen erhalten jeweils eine Nummer (bzw. einen Wert). Und zwar wird dem Gefangenen n die Nummer 2^{n-1} zugewiesen, sprich:
Damit lässt sich jede Zahl von 0 bis 1023eindeutig darstellen, indem man angibt, welche der zehn Gefangenenwerte man nutzt (also aufaddiert) und welche nicht.
Bei Wikipedia ist die Funktionsweise des Dualsystems bzw. Binärsystems noch einmal ausführlich erklärt.
Kurzes Beispiel: Die Zahl 420 lässt sich darstellen als
In der sogenannten Binärschreibweise schreibt man kurz 420 = 0110100100_\text{b}.
Man beginnt also beim größten Wert, der noch kleiner ist als die umzuwandelnde Zahl. Von dort an arbeitet man sich abwärts und entscheidet jeweils, ob die nächstkleiner Potenz noch hinzuaddiert werden kann oder nicht.
Dieses Vorgehen geht immer auf.
Wie hilft das dem König?
Jede der Zahlen von 1 bis 1000 wird nun in Binärschreibweise dargestellt.
Wir beginnen also mit Flasche 1, deren Binärdarstellung 0000000001_\text{b} lautet. Demzufolge bekommt nur der 1. Gefangene (der mit dem Wert 1) einen Tropfen aus dieser Flasche verabreicht.
Flasche 2 hat die Binärdarstellung 0000000010_\text{b}. Also bekommt nur der 2. Gefangene (der mit dem Wert 2) einen Tropfen aus Flasche 2 verabreicht.
Flasche 3 hat die Binärdarstellung 0000000011_\text{b}. Hier bekommen also sowohl der 1. Gefangene (mit dem Wert 1) als auch der 2. Gefangene (mit dem Wert 2) einen Tropfen aus Flasche 3 verabreicht.
Das weitere Vorgehen schauen wir uns exemplarisch an Flasche 420 an:
Wie bereits gesehen hat diese Weinflasche 420 die Binärdarstellung 420 = 0110100100_\text{b}. Also bekommen der 3., der 6., der 8. und der 9. Gefangene jeweils einen Tropfen aus Flasche 420.
Welche Flasche ist nun vergiftet?
Nachdem alle Flaschen nach diesem Muster “verkostet” wurden, wartet der König, bis die Wirkung des Gifts einsetzt.
Die beobachtete Kombination aus vergifteten Gefangenen entspricht nun genau der Binärdarstellung der vergifteten Flasche.
Sterben also beispielsweise genau der 3., der 6., der 8. und der 9. Gefangene, während alle anderen überleben, so war Flasche 420 die vergiftete.
Diese Flasche kann er dann entsorgen und aus den übrigen Flaschen fehlen nur wenige Tropfen.
Eine Menge Wein für die Gäste wird gespart, wenn unter den gegebenen Voraussetzungen der König folgendermaßen vorgeht:
Einer der 10 Gefangenen erhält den Befehl, in 9 Gläser aus 100 verschiedenen Flaschen je einen Tropfen einzuschenken, die letzten 100 Flaschen bleiben vorerst verschlossen. Dann muss er den übrigen 9 Gefangenen diese Gläser zum Trinken geben.
1. Durchgang;
In Glas 1 kommen aus den Flaschen 1- 100 je ein Tropen.
In Glas 2 kommen aus den Flaschen 101 – 200 je ein Tropen.
…
In Glas 9 kommen aus den Flaschen 801 – 900 je ein Tropen.
Jetzt wird jedes Glas von je einem der neun übrigen Gefangenen getrunken mit der Folge, dass einer oder keiner von ihnen stirbt. Nun weiß der König, dass der vergiftete Wein in den 100 Flaschen ist, die der gestorbene Mann getrunken hat oder in den 100 Flaschen, die noch verschlossen sind. Jedenfalls hat er die Anzahl von 1000 auf 100 reduziert. In allen Flaschen fehlt nur 1 einziger Tropfen!
Jetzt gilt es den vergifteten Wein aus 100 Flaschen ausfindig zu machen, und zwar entweder mit 9 oder mit 10 Gefangenen
in 100 Flaschen fehlt kein, in 900 Flaschen je ein Tropfen.
2.a) Durchgang mit 10 Gefangenen und 100 Flaschen
Einer der 10 Gefangenen erhält den Befehl, in 9 Gläser aus 10 verschiedenen Flaschen je einen Tropfen einzuschenken, die letzten 10 Flaschen werden beiseite gestellt. Dann muss er den übrigen 9 Gefangenen diese Gläser zum Trinken geben.
In Glas 1 kommen aus den Flaschen 1- 10 je ein Tropen.
In Glas 2 kommen aus den Flaschen 11 – 20 je ein Tropen.
…
In Glas 9 kommen aus den Flaschen 81 – 90 je ein Tropen.
Jetzt wird jedes Glas von je einem der neun übrigen Gefangenen getrunken mit der Folge, dass einer oder keiner von ihnen stirbt. Nun weiß der König, dass der vergiftete Wein in den 10 Flaschen ist, die der gestorbene Mann getrunken hat oder in den 10 Flaschen, die beiseite gestellt worden sind. Jedenfalls hat er die Anzahl von 1000 nun auf 10 reduziert. Und insgesamt fehlen nur 990 Tropfen, und die Zahl der Gefangenen beträgt 9 oder 10.
2.b) Durchgang 2 mit 9 Gefangenen und 100 Flaschen
Der Vorgang läuft genau so ab, wie oben beschrieben, nur dass der Wein hier von einer anderen Person eingeschenkt wird. Das Resultat ist, was den fehlenden Wein anbelangt, dann das Gleiche, von den 9 Gefangenen bleiben gibt es jetzt noch alle 9 oder nur noch 8.
3.a) Durchgang mit 9 oder 10 Gefangenen
Um mit einen Schritt zum Ergebnis zukommen, werden nur 9 Gefangene benötig. Sind es noch alle 10, so muss einer davon wieder einschenken (der überlebt sicher). In jedes Glas kommt ein Tropfen, die 10. Flasche wird beiseite gestellt. Stirbt nach dem Trinken einer, so weiß der König, welche Flasche den vergifteten Wein enthielt, stirbt keiner, so haben alle Gefangenen überlebt, denn der vergiftete Wein ist dann in der beiseite gestellten Flasche.
3.b) Durchgang mit 8 Gefangenen und 10 Flaschen
In die Gläser für die Gefangenen 1 bis 6 werden aus den Flaschen 1 bis 6 je 1 Tropfen eingeschenkt, in das Glas für den 7. Gefangenen je ein Tropfen aus Flasche 7 und 9 und in das Glas für den 8. Gefangenen je ein Tropfen aus Flasche 8 und 9, die 10. Flasche wird beiseite gestellt.
Stirbt keiner, so ist der Wein in der 10. Flasche, die beiseite gestellt wurde.
Stirbt einer, der den Tropfen der Flaschen 1 bis 6 erhalten hat, so weiß der König, welche Flasche vergifteten Wein enthält.
Stirbt nur der 7. Gefangene, so ist der Wein in Flasche 7 vergiftet.
Stirbt nur der 8. Gefangene, so ist der Wein in Flasche 8 vergiftet.
Sterben die Gefangenen 7 und 8 beide, so ist der Wein in Flasche 9 vergiftet.
Von den zehn Gefangenen könnten im günstigsten Fall alle überleben, im ungünstigsten Fall überleben sechs.
Insgesamt musste der König dafür an Wein 900 Tropfen im ersten Durchgang, 90 Tropfen im zweiten und 9 Tropfen im dritten Durchgang opfern, und drei Tropfen fehlen nur in 9 Flaschen. Im günstigsten Fall bleiben 100 verschlossen.
Noch ein kleiner Nachtrag zu meinem ersten Kommentar:
20 Tropfen besitzen etwa ein Volumen von 1 ml.
4973 Tropfen hätte der König bei der Binärzahl-Lösung geopfert, denn so oft kommt die 1 bei den ersten 1000 Binärzahlen vor.
4973 : 20 = 248,65 ml ≈ 1/4 l
999 Tropfen hätte der König bei meiner Lösung geopfert.
999 : 20 = 49,95 ml ≈ 1/20 l
Was die Anzahl der toten Häftlinge anbelangt…
Bei der Binärzahl-Methode gibt es in
10 Fällen 1 Toten, (1, 10, 100, …, 1000000000, alle Zahlen mit nur einer 1)
45 Fällen 2 Tote, (alle Zahlen mit zweimal 1 (11, 101, 1001, …,, 1000000001)
120 Fällen 3 Tote,
210 Fällen 4 Tote,
252 Fällen 5 Tote,
209 Fällen 6 Tote,
113 Fällen 7 Tote,
36 Fällen 8 Tote,
5 Fällen 9 Tote.
Bei meiner Methode ist es möglich, dass alle überleben oder dass es nur einen oder maximal zwei Tote gibt.
Leider scheitert deine Ressourcen schonende Lösung an der Zeit: Das Fest findet in einer Woche statt, aber man stirbt erst nach 5 Tagen am Gift.
Der König kann zwischen den einzelnen Durchgängen nicht jeweils 5 Tage warten um die die Auswahlmenge der Weinflaschen zu reduzieren. Bei 3 Durchgängen (von 1000 zu 100, von 100 zu 10 und von 10 zu 1) dauert dies 15 Tage, während das Fest bereits in 7 Tagen beginnt.
Schreibe einen Kommentar