You have eight pills. One of them is poisonous. The poisonous pill weighs slightly more than the others, but otherwise they appear to be identical. You have access to a scale, but you may only use the scale twice (for some reason). How do you determine which pill is the poisonous one?The solution produced by our group (four undergraduate math majors) is as follows:
Satisfied with this solution, the other members of my study group were ready to move on. This is the myth of the right answer.
We are programmed since elementary school to find "the" answer and move on to our next assignment. Each quiz, riddle, puzzle, and problem is simply an obstacle to overcome in the ongoing mission to meet our teachers', principals', parents', and professors' approval. Why should the authority figure determine when our problem is solved?
So it's great that we found the algorithm to solve this problem with two weighs. But why stop there? Some related questions:
- Given n pills, what is the minimum number of weighs required to finding the poison pill?
- Given n pills that can be weighed with w weighs, is there an alternate weighing scheme that can find the poison pill in exactly w weighs?
- What if we don't know if the poison pill is heavier or lighter (only that it weighs a different amount)?
- What if every pill weighs a different amount, but the poison pill is still heavier than all the others?
- What if there are two poisoned pills
- Given n pills, m of which are poisoned, how many weighs are required to find the poisoned pills?
- What if the scale can only hold two or fewer pills at a time?
- Given n pills, one of which is poisoned, and a scale that can only hold k or fewer pills, how many weighs does it take to find the poisoned pill?
- Given n pills, m of which are poisoned, and a scale that can only hold k or fewer pills, how many weighs does it take to find the poisoned pills?
- Given n pills, m of which are poisoned, and a scale that can only hold exactly k pills, how many weighs does it take to find the poisoned pills?
- Suppose we would settle for knowing which is the poisoned pill with probability p, what is the minimum number of weighs?
None of my classmates asked these questions, they were satisfied with just having the answer. To be clear: my classmates are not stupid. In fact, they're all quite bright. But they (we) have been programmed to find the answer, to report the answer, then to forget the question. Somewhere in all of this answer-fetishism we have forgotten how to ask questions. We have lost our curiosity.
A good question is more interesting than a satisfying answer. Why then do we let other people ask all the questions?
This is a rather insightful post and I linked it on my Facebook in case anyone actually wants to do something interesting. I never really considered this and given how many riddles and puzzles I go out of my way to read and do for fun, it's somewhat disappointing (to me) that I've not once generated my own version or spinoff of those problems as you mention here.
ReplyDeleteAlso since I just got some free time I may go about systematically answering every question you posted here because, frankly, they are all kind of interesting to me (although not the point of this post).
Ok, a general solution for the following situation: given a scale that can accept k piles of objects and register which is heaviest (or lightest, depending on if the poison pill is heavier or lighter respectively), and n pills with 1 poisoned pill among them the answer is, it can be done in w weights where (k+1)^(w-1) >= n. Specifically, given a standard balance scale that measures 2 piles, and 9 pills one of which is poisoned, it can be found in 2 weights ((2+1)^2 = 9 >= 9 = n.
ReplyDeleteHere's how: Recall our goal is to split our objects into piles and determine information about those piles (specifically, which has the poisoned pill in it) in the most efficient manner possible. This means we want to utilize the piles we are weighting (k of them) and the pile we aren't weighting (1 of them) and gain information about each.
If we split our original batch into k+1 piles, and measure k of them, we can determine if one of those k piles is heavier (and thus has the pill) or if they are all equal, in which case the poison pill is in the unmeasured pile. Take that pile and split it again into k+1 piles and repeat. This clearly reduces our pile at each iteration to n/(k+1)^(m-1) where m is how many iterations we have maintained. By hypothesis (k+1)^(w-1) >= n, so by the w-th weighting, we have n/(k+1)^(w-1) =< 1 = 1 remaining possibilities, which means we have uniquely determined the poisoned pill.
Thus in a standard balance scale situation we can determine our poisoned pill in n pills within [log(base 3) of n] - 1 rounded down weightings.
EDIT: Wish there was an edit key, that's why there was deleted above as I made a symbolic error while typing. There may be more in here.
I am currently solving m poisoned pills which poses a much more interesting case.
This is great! I meant to solve this too, but I never did.
Delete(I think) you can include LaTeX in your posts using \$ signs. For example, your result is $w = (k+1)^{w-1} \geq n$.
Unfortunately,tThe LaTeX doesn't render on preview, only on publish.