SteveJ
V:I:P
- Registriert
- 21 Apr. 2010
- Themen
- 1.052
- Beiträge
- 3.257
- Reaktionen
- 8.414
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.
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 aber 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 komplett 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?
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.
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 aber 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 komplett 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?
2^10 ("zwei hoch zehn" = 1024 > 1000.
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 nn die Nummer 2^(n−1) zugewiesen, sprich:
Damit lässt sich jede Zahl von 0 bis 1023 eindeutig darstellen, indem man angibt, welche der zehn Gefangenenwerte man nutzt (also aufaddiert) und welche nicht.
Kurzes Beispiel:
Die Zahl 420 lässt sich darstellen als
420 = 0⋅512 + 1⋅256 + 1⋅128 + 0⋅64 + 1⋅32 + 0⋅16 + 0⋅8 + 1⋅4 + 0⋅2 + 0⋅1
In der sogenannten Binärschreibweise schreibt man kurz 420 = 0110100100.
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ächstkleinere Potenz noch hinzuaddiert werden kann oder nicht.
Der größte Wert ist bei einer Binärzahl immer die ganz linke Stelle, dann geht es nach rechts abwärts...
Dieses Vorgehen geht immer auf.
Wie hilft das jetzt dem König?
Jede der Zahlen von 1 bis 1000 wird nun wie beschrieben in Binärschreibweise dargestellt.
Wir beginnen also mit Flasche 1, deren Binärdarstellung 0000000001 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.
Also bekommt nur der 2. Gefangene (der mit dem Wert 2) einen Tropfen aus Flasche 2 verabreicht.
Flasche 3 hat die Binärdarstellung 0000000011.
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 der Flasche mit der Beispielnummer 420 von oben an:
Wie bereits gesehen hat diese Flasche 420 die Binärdarstellung 420 = 0110100100.
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.
Denn nur die entsprechenden Gefangenen haben einen Tropfen aus dieser Flasche bekommen.
Diese Flasche kann er dann entsorgen und aus den übrigen Flaschen fehlen nur wenige Tropfen...
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 nn die Nummer 2^(n−1) zugewiesen, sprich:
| Gefangener | Wert |
|---|---|
| 1 | 2^0 = 1 |
| 2 | 2^1 = 2 |
| 3 | 2^2 = 4 |
| 4 | 2^3 = 8 |
| 5 | 2^4 = 16 |
| 6 | 2^5 = 32 |
| 7 | 2^6 = 64 |
| 8 | 2^7 = 128 |
| 9 | 2^8 = 256 |
| 10 | 2^9 = 512 |
Damit lässt sich jede Zahl von 0 bis 1023 eindeutig darstellen, indem man angibt, welche der zehn Gefangenenwerte man nutzt (also aufaddiert) und welche nicht.
Kurzes Beispiel:
Die Zahl 420 lässt sich darstellen als
420 = 0⋅512 + 1⋅256 + 1⋅128 + 0⋅64 + 1⋅32 + 0⋅16 + 0⋅8 + 1⋅4 + 0⋅2 + 0⋅1
In der sogenannten Binärschreibweise schreibt man kurz 420 = 0110100100.
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ächstkleinere Potenz noch hinzuaddiert werden kann oder nicht.
Der größte Wert ist bei einer Binärzahl immer die ganz linke Stelle, dann geht es nach rechts abwärts...
Dieses Vorgehen geht immer auf.
Wie hilft das jetzt dem König?
Jede der Zahlen von 1 bis 1000 wird nun wie beschrieben in Binärschreibweise dargestellt.
Wir beginnen also mit Flasche 1, deren Binärdarstellung 0000000001 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.
Also bekommt nur der 2. Gefangene (der mit dem Wert 2) einen Tropfen aus Flasche 2 verabreicht.
Flasche 3 hat die Binärdarstellung 0000000011.
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 der Flasche mit der Beispielnummer 420 von oben an:
Wie bereits gesehen hat diese Flasche 420 die Binärdarstellung 420 = 0110100100.
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.
Denn nur die entsprechenden Gefangenen haben einen Tropfen aus dieser Flasche bekommen.
Diese Flasche kann er dann entsorgen und aus den übrigen Flaschen fehlen nur wenige Tropfen...
