Poisoned Wine in 12 Sips

This question presents a search problem with severe resource and time constraints: one dangerous item hidden among many, a small pool of "testers," and a fixed delay before test outcomes become visible. The twist is that you cannot run tests sequentially; everything must happen in a single batch before the deadline. Candidates must reason about how to schedule and mix tests so that each tester's eventual outcome contributes maximally to narrowing down the culprit, and whether the available "experiments" are enough in principle to uniquely identify the poisoned bottle.

The solution relies on viewing each tester as a binary information channel and designing the experiment as an encoding scheme over these channels. Strong answers frame the problem in terms of bits, combinatorial design, and capacity limits: how many distinct states the overall pattern of outcomes can represent. Interviewers look for applicants who can abstract away from the story to a clean information-theoretic or algorithmic formulation, construct a systematic scheme rather than ad hoc testing, and clearly justify correctness and optimality.

What it tests

This class of problems is governed by the principle of information encoding and extraction: when you have a limited number of binary outcomes (such as alive/dead mice), you can use each outcome as a 'bit' to encode information about a larger set of possibilities. The maximum number of distinct items you can distinguish is $2^n$ where $n$ is the number of independent binary tests. The reason this works is that each test (mouse) can be assigned to a unique subset of items based on a systematic rule (like binary digits), so the combination of test results forms a unique pattern identifying the target. The power comes from parallelizing the tests: all information is gathered simultaneously, rather than sequentially, making it possible to solve the problem within strict time constraints. This method is a concrete application of combinatorial encoding, where the structure of binary numbers provides a natural mapping from outcomes to identities.