You might have heard of the riddle that asks you to identify one fake pill (poisoned) among 12 pills of identical appearance, with the fake pill being either lighter or heavier than the others. You have a pair of comparative scales at your disposal, but must only use it three times. (To increase suspense, the lives of your friends depend on your correct and timely solution of this problem.)
I would like to discuss the underlying principles of information theory and use the results of that discussion to expand the riddle.
As I have found out, it is also possible to solve this riddle if you have 13 pills, one of them poisoned. Edit: This only works if you do not have to know whether the poisoned pill is heavier or lighter than the others (however it can be unknown).
The key theme in solving this riddle is to arrange the scalings such that you get as much information as possible in the worst case scenario. Consider the idea to scale 6 pills against 6 other pills. If they have the same weight, you can be 100% certain that the 13th pill is the fake one (best case scenario), but if their weight differs, you have learnt almost nothing (namely, that the 13$^{th}$ pill is not poisoned, and that 6 specific pills are heavier than 6 others.)
The information content of an event is inversely related to its likelihood, so as it is very likely (12:1) that the 13$^{th}$ pill is not the fake one, the worst case information content is low. As there are three possible outcomes in a scaling process (left is heavier, right is heavier, and same weight) you should start by putting about a third of the pills away in the first weighting process.
Furthermore, you have to make sure to get as much information as possible from each weighting process. For starters, that means you should not do the same weighting twice (obvious, isn’t it?). Instead, rearrange the pills in a systematic way to allow for the result of the weighing to reflect different possible scenarios. I.e, if you have identified a group of 4 pills as “light” after the first weighing, put one aside, substitute one with a “heavy”, one with a “safely unpoisoned” and leave one one the same scale pan as it was before, and observe what change this causes.
Following these rules, it will be quite easy to figure out the solution to this riddle, at least it is by far easier than trying out all possible combinations of weighings and wondering whether that gave you enough information to identify the fake pill or not.
Question 1: These “rules” seem intuitive to me, but I wonder if there is some more solid information theory behind them?
Also, since a more complex riddle is a better riddle, I wonder how many pills could be tested for one fake pill, if you had 4 weighings? (Question 2). There is an obvious minimum number, for which a solution can be easily found: 25. The easy solution is: Put 13 pills aside and weigh 6 against 6. If they have equal weight, proceed with the 13 remaining pills as above. If they have different weight, proceed with the 12 pills as above. However, this wastes a lot of information, so I guess it should be possible with a much higher number of pills, although I do not know how to find that number.
My third question is to what degree would complexity of this problem rise if there were 2 poisoned fake pills (either of same or of potentially different weight)?
Best wishes,
Martin
Best Answer
It's not true that you can solve this with $13$ pills; this page explains why.
You can get an upper bound on the number of pills for which this can be solved with $k$ weighings as follows. For $n$ pills, there are $2n$ different results to distinguish ($1$ out of $n$ pills and $1$ out of the $2$ possibilities "lighter" and "heavier"). From each weighing, you get one of $3$ results, so with $k$ weighings you can differentiate $3^k$ outcomes. Thus, if you can find an ideal weighing scheme such that the remaining possible results are distributed as equally as possible among the three outcomes of each weighing, you can solve the problem for $\lfloor3^k/2\rfloor$ pills with $k$ weighings. For $3$ weighings, this yields an upper bound of $13$ pills, so this bound isn't tight, since the problem can in fact only be solved for $12$ pills. For $4$ weighings, this yields $40$ pills, but a moment's reflection shows that this is in fact unsolvable for a similar reason as the $k=3,n=13$ case.
You may also be interested in this: Finding four numbers.