this is a classic problem which i have heard many times before. this is the “harder” of the two problems, since in this one, you do not know if the invalid item weighs more or less than the others.
solving it is only half the battle. writing up a solution that anyone including your grandma could understand, is very hard.
problem: the evil king from before sends his own assassin to take care of the evil queen who tried to poison him. of course, her trusty guards catch the assassin before any harm is done. the queen notices that the assassin is quite handsome and doesn’t really want to punish him by death. she decides to test his wisdom.
the queen gives the assassin 12 pills which are all completely identical in shape, smell, texture, size, except 1 pill has a different weight. the queen gives the man a balance and tells him that all the pills are deadly poison except for the pill of a different weight. the assassin can make three weighings and then must swallow the pill of his choice. if he lives, he will be sent back to the bad king’s kingdom. if he dies, well, thats what you get for being an assassin.
only one pill is not poison and it is the pill which has a different weight. the assassin does not know if it weighs more or less than the other pills. how can he save his skin?
Solution
this is a classic problem which i have heard many times before. this is the “harder” of the two problems, since in this one, you do not know if the invalid item weighs more or less than the others.
solving it is only half the battle. writing up a solution that anyone including your grandma could understand, is very hard.
problem: the evil king from before sends his own assassin to take care of the evil queen who tried to poison him. of course, her trusty guards catch the assassin before any harm is done. the queen notices that the assassin is quite handsome and doesn’t really want to punish him by death. she decides to test his wisdom.
the queen gives the assassin 12 pills which are all completely identical in shape, smell, texture, size, except 1 pill has a different weight. the queen gives the man a balance and tells him that all the pills are deadly poison except for the pill of a different weight. the assassin can make three weighings and then must swallow the pill of his choice. if he lives, he will be sent back to the bad king’s kingdom. if he dies, well, thats what you get for being an assassin.
only one pill is not poison and it is the pill which has a different weight. the assassin does not know if it weighs more or less than the other pills. how can he save his skin?
solution: easy.
choose any eight of the pills and put four of them on each side of the balance.
there are two possibilities:
(1) one side of the balance comes out lighter. In this case, you know that the abnormal (safe) pill is one of the pills already on the balance. label the pills on the lighter side A B C and D, and the pills on the heavier side E F G and H. label the pills not on the balance NORM (you know they’re normal pills).
(2) the balance is even. in this case, you know that the abnormal (safe) pill is one of the pills not on the balance. label the pills already on the balance NORM, and label the four pills not on the balance I J K and L.
let’s proceed with possibility (1).
consider why the side ABCD came out higher than the side EFGH. this could be because:
A is the abnormal pill, and it’s lighter than the other pills.
B is the abnormal pill, and it’s lighter than the other pills.
C is the abnormal pill, and it’s lighter than the other pills.
D is the abnormal pill, and it’s lighter than the other pills.
E is the abnormal pill, and it’s heavier than the other pills.
F is the abnormal pill, and it’s heavier than the other pills.
G is the abnormal pill, and it’s heavier than the other pills.
H is the abnormal pill, and it’s heavier than the other pills.
now let’s make another weighing, with two of the ABCD pills on either side, and one of the EFGH pills on either side. for example, let’s weigh ABE versus CDF. how would this weighing come out given each of those 8 possibilities we just listed?
if A is the light pill, the ABE/CDF weighing will come out with ABE high.
if B is the light pill, the ABE/CDF weighing will come out with ABE high.
if C is the light pill, the ABE/CDF weighing will come out with ABE low.
if D is the light pill, the ABE/CDF weighing will come out with ABE low.
if E is the heavy pill, the ABE/CDF weighing will come out with ABE low.
if F is the heavy pill, the ABE/CDF weighing will come out with ABE high.
if G is the heavy pill, the ABE/CDF weighing will come out even.
if H is the heavy pill, the ABE/CDF weighing will come out even.
OK, so we observe how the ABE versus CDF weighing actually comes out.
(a) if it comes out even, then we know that the abnormal pill is either G or H. for our third weighing, we can weigh G against one of the pills we already know to be normal (one of the pills we labelled NORM). if it comes out even, then G is normal and H must be the abnormal pill. if it comes out uneven, then G is the abnormal pill.
(b) as we can see from our chart above, if the ABE/CDF weighing comes out with ABE high, then the situation is either: A is the light pill, B is the light pill, or F is the heavy pill.
(c) as we can see from our chart above, if the ABE/CDF weighing comes out with ABE low, then the situation is either: C is the light pill, D is the light pill, or E is heavy pill.
so in either situation (b) or (c), we have two possible light pills and one possible heavy pill. what we do in that case is we put one of the possible light pills and the possible heavy pill on one side of the scale, and two NORM pills on the other side of the scale. this is our third weighing. if it comes out even, then we know that the other possible light pill is the abnormal pill. if it comes out with the two NORM pills high, then we know that one of the pills on the other side is abnormally heavy, so we know that the possible heavy pill is the culprit. if it comes out with the two NORM pills low, then we know that one of the pills on the other side is abnormally light, so we know that the possible light pill on the scale is the culprit.
that takes care of case (1), where the first weighing came out uneven.
what about case (2), where the first weighing comes out even?
then we know the abnormal pill is one of I J K or L, and we have two weighings to find the abnormal pill in.
for our second weighing, we put I and J on one side of the scale, and two NORM pills on the other.
(a) if this comes out uneven, we know the abnormal pill is I or J; we weigh I against one NORM pill to see if I is abnormal and if it isn’t, we can conclude that J is the abnormal pill.
(b) if the IJ versus 2 NORM weighing comes out even, we know the abnormal pill is K or L; we weight K against one NORM pill to see if K is abnormal and if it isn’t, we can conclude that L is the abnormal pill.