I will end this mini-series with the following brain teaser. This one's my favorite, because it's one of the most clever and challenging puzzles I've ever come across. Give it a go. The solution is quite beautiful.
The Infamous Twelve Pills Problem
You are given twelve pills, eleven of which are poisonous. The non-toxic pill weighs differently than the eleven toxic ones. Determine, using a two-platform relative weighing scale and no more than three weigh-ins, which is the non-toxic pill. (Note: You do not know beforehand whether the non-toxic pill is heavier or lighter than the toxic pills.) Level of difficulty: tougher than the toughest gangsta on the streets of CPT.
One of my friends suggested feeding the pills to twelve of his enemies and seeing which one survived. Not exactly what I had in mind, but it works. Now for the not-so-murderous solution...
Separate the 12 pills into 3 groups (call them groups A, B and C), each consisting of 4 pills. Place groups A and B on the scale, one group on each platform. If the weights are equal, you have two weigh-ins left and have determined that the good pill is in group C. For the second weigh-in, take 3 pills from group C and 3 pills from group A. If the weights are equal, the good pill is the remaining pill from group C. If the weights are unequal, the good pill is one of the three from group C that are on the scale, and you now know whether the good pill is heavier or lighter than the rest. The third weigh-in will then determine conclusively which is the good pill.
If, in the first weigh-in, groups A (pills A1, A2, A3 and A4) and B (pills B1, B2, B3 and B4) were found to be of unequal weight, then in the second weigh-in, put B1, B2, B3 and A4 on one platform of the scale, and C1, C2, C3 and B4 on the other platform. Depending on the relative weights, you'll be able to determine from the second weigh-in which of the following is true, and the third weigh-in then gives you the solution:
The Infamous Twelve Pills Problem
You are given twelve pills, eleven of which are poisonous. The non-toxic pill weighs differently than the eleven toxic ones. Determine, using a two-platform relative weighing scale and no more than three weigh-ins, which is the non-toxic pill. (Note: You do not know beforehand whether the non-toxic pill is heavier or lighter than the toxic pills.) Level of difficulty: tougher than the toughest gangsta on the streets of CPT.
One of my friends suggested feeding the pills to twelve of his enemies and seeing which one survived. Not exactly what I had in mind, but it works. Now for the not-so-murderous solution...
Separate the 12 pills into 3 groups (call them groups A, B and C), each consisting of 4 pills. Place groups A and B on the scale, one group on each platform. If the weights are equal, you have two weigh-ins left and have determined that the good pill is in group C. For the second weigh-in, take 3 pills from group C and 3 pills from group A. If the weights are equal, the good pill is the remaining pill from group C. If the weights are unequal, the good pill is one of the three from group C that are on the scale, and you now know whether the good pill is heavier or lighter than the rest. The third weigh-in will then determine conclusively which is the good pill.
If, in the first weigh-in, groups A (pills A1, A2, A3 and A4) and B (pills B1, B2, B3 and B4) were found to be of unequal weight, then in the second weigh-in, put B1, B2, B3 and A4 on one platform of the scale, and C1, C2, C3 and B4 on the other platform. Depending on the relative weights, you'll be able to determine from the second weigh-in which of the following is true, and the third weigh-in then gives you the solution:
- The good pill is A1, A2 or A3, and you will know whether it's heavier or lighter than the bad pills based on the result of the first weigh-in. (This statement is true if B1+B2+B3+A4 = C1+C2+C3+B4 in the second weigh-in.)
- The good pill is B1, B2 or B3, and you will know whether it's heavier or lighter than the bad pills based on the result of the first weigh-in. (This statement is true if the scale flips, i.e., the lighter side from the first weigh-in is now the heavier side in the second weigh-in, when you move B1, B2 and B3 to the other platform with A4.)
- The good pill is either A4 or B4, and you will know whether it's heavier or lighter than the bad pills based on the result of the first weigh-in. (This statement is true if the scale doesn't flip in the second weigh-in.)
No comments:
Post a Comment