Solution
Two Poisoned Bottles in One Round
Show the problem again
A cellar has 8 bottles of wine, exactly two of which are poisoned. Before a single round of tasting, you assign each taster a set of bottles to drink from. A taster dies if any of the bottles they drink from is poisoned and survives otherwise. After the round you see exactly which tasters died, and from that you must be able to name the two poisoned bottles. What is the minimum number of tasters needed?
Worked solution
The answer is 6. Give each bottle a code: the set of tasters that drink it. The set of dead tasters is the union of the codes of the two poisoned bottles, so we need all C(8,2) = 28 pairwise unions to be different. Counting alone allows 5 tasters (2^5 = 32 ≥ 28), but 5 do not suffice: an exhaustive backtracking search over all choices of eight nonempty subsets of a 5-element set finds no family with distinct pairwise unions. With 6 tasters it works: use the codes 000001, 000010, 001100, 010101, 011010, 100110, 101001, 110000 (as bit-strings). A direct check shows all 28 pairwise unions are different. The minimum is therefore 6.
Source: Group-testing puzzle (pair-detecting, i.e. 2-separable binary codes); the setting is classical in combinatorial group testing, but this version is an original design for AxiomIQ.