Das vergiftete Weinfass (Lösung)

Die Auflösung zum Rätsel Das vergiftete Weinfass.

Spoiler

Wenn jedes Fass von einer anderen Teilmenge der Testpersonen geprüft wird, dann lässt sich das vergiftete Fass eindeutig identifizieren: Es ist das einzige Fass, von dem alle Toten und keine Überlebenden getrunken haben. Die Frage ist nur: Gibt es überhaupt genug Teilmengen dafür?

Wenn es nur eine Testperson wäre, dann gäbe es zwei Teilmengen: Die leere Menge und die Menge, die die Person als einziges Element enthält. Mit jeder weiteren Person verdoppelt sich die Anzahl der Teilmengen, da wir die bestehenden Teilmengen kopieren und den Kopien jeweils die neue Person als Element hinzufügen können. Bei zwei Personen haben wir also schon vier Teilmengen, bei drei Personen acht Teilmengen und so weiter.

Bei zehn Personen kommen wir auf 1024 Teilmengen. Es reicht also, wir haben sogar noch ein paar ungenutzte Teilmengen übrig.

Eine von vielen praktischen Umsetzungen ginge so: Die Fässer werden mit zehnstelligen Binärzahlen durchnummeriert, also

00000 00000,
00000 00001,
00000 00010,
00000 00011,
00000 00100
und so weiter.

Jeder Testperson wird eine Stelle zugewiesen, z.B. der ersten Person die Einser-Stelle, der zweiten Person die Zweier-Stelle, der dritten Person die Vierer-Stelle und so weiter. Jede Person trinkt dann von allen Fässern, wo die ihr zugewiesene Stelle 1 ist.