Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
See oeis.org/A029858 which gives the number of weighings needed for n objects. –  Charles Sep 15 '11 at 13:03
    
Related: How to find the balls? –  Mike Spivey Sep 15 '11 at 13:08
    
Although this is an old question, I would like to add that this is actually an old problem from the USSR Math Olympiads. See "The USSR Olympiad Problem Book," which contains a few variants of this question. –  lyj Dec 18 '13 at 21:39

3 Answers 3

up vote 4 down vote accepted

Problems of this kind fall in the category of what's called "combinatorial group testing." The standard reference appears to be Combinatorial Group Testing and Its Applications, by Du and Hwang. In Chapter 16 they discuss your problem. I can't access the entire chapter via Google books, but, for Question 1, there is some mention of information theory. The book gives other references that are probably worth tracking down as well.

With respect to Question 2, the author of this document claims that you can determine which of $n$ pills is the fake one in $k$ weighings if and only if $n \leq (3^k-1)/2$, $n \neq 2$. (Added: The OEIS entry for these numbers confirms this.) For 4 weighings, that would give a maximum of 40 pills. He also claims to have solved several variants of this problem, in which you (1) know or don't know whether there actually is a poisoned pill, (2) know or don't know if a fake pill is heavier or lighter than a genuine one, (3) have 0, 1, or infinitely many additional pills that you know are genuine, (4) do or don't have to identify whether the pill is heavier or lighter, and (5) must plan all the weighings in advance or not.

For a slight variation on Question 3, Du and Hwang give the following results for the case in which you know that the fake pills are lighter. If there are $d$ fake pills, $n$ total pills, and $g(d,n)$ is the minimum number of weighings required to identify the $d$ fake ones, then $$g(2,n) = \left\lceil \log_3 \binom{n}{2} \right\rceil,$$ $$\left\lceil \log_3 \binom{n}{3} \right\rceil \leq g(3,n) \leq \left\lceil \log_3 \binom{n}{3} \right\rceil+2,$$ $$\left\lceil \log_3 \binom{n}{d} \right\rceil \leq g(d,n) \leq \left\lceil \log_3 \binom{n}{d} \right\rceil+ 15d.$$

They say that the proof for the $g(2,n)$ result is a very complicated case-by-case argument. Your Question 3 is somewhat more difficult than this, and there may not be any known results. They may give some more results on the variation you specifically ask for, though; I would track down a hard copy of the book.

share|improve this 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.

share|improve this answer
    
Thank you for the link! It is good to know that I’m not the only one interested in this problem ;-) Also, the riddle is only solveable with 13 pills if you do not need to know whether the fake pill is heavier or lighter than the others, which the riddle you linked requires. –  mzuba Sep 15 '11 at 12:37
    
@mzuba: Indeed, if you already know whether the fake pill is heavier or lighter than the others from the beginning, you can resolve up to 27 pills in 3 weighings: at each step just split the candidate pool into equal groups of three and weigh two of the groups against each other. –  anon Sep 15 '11 at 20:18

The arguments from information theory and coding theory give strong bounds, often within a small additive constant (independent of the $n$ = the number of coins/pills/objects) of the answer, but are not optimal in general. To determine the minimum number of weighings, or the maximum number of coins, can require an extremely complicated analysis that is sensitive to the details of the problem, including: the number of false objects, dynamic or pre-specified weighings, whether light or heavy state of the false objects is to be determined or only their identity, and whether an adversary can introduce errors.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.