There are 12 pieces of radioactive metal V that look identical. 11 of the pieces give the same ...
There are 12 pieces of radioactive metal V that look identical. 11 of the pieces give the same radiation count when measured, the 12th piece is a counterfeit and gives a different radiation level, which may be more or less than the other 11. We are given a radiation scale, which can take 2 sets of samples and compare their added up radiation levels to tell us if the sums are the same or if different, which set has the higher level of radiation. What is the minimum number of comparisons we need on this scale to identify the counterfeit sample and to also determine whether it has more or less radiation than the other samples ?
Answer/Solution
3
Steps/Work
First of all if you are down to just 3 pieces and you know that if the offending piece is less or more active, then it takes exactly 1 measurement to find out the offending piece. So you know you have to reduce the problem to three.
Now when you are down to either A or B after measurement 1, you need the next measurement to (a) reduce the problem set to 3 and (b) to know whether anser is more or less. Now you cannot compare a group of 4 to 4, as in the best case it will only reduce the problem to 4 elements which is not good enough.
If you have to choose a set of 3 to compare, you cannot pick any 3 on the same side from the same set (A or B) because if you do this, a quick check will show you that in every choice there is a case where you can only get down to 4 elements. Eg. If you weighed {1,2,3} v/s {5,9,10} and they were equal you're problem would only reduce to {4,6,7,8}
The easiest way to solve this then is to compare 3 to 3, and make sure each side has elements from both AB such that whatever the measurement outcome in the worst case the problem reduces to 3 elements only. Which is why the sets {1,5,9} and {2,6,7} OR {A,B,C}{A,B,B}. The extra element from C is just taken to make the problem symmetric so to say, we have 8 elements and we make it 9, to compose 3 sets of 3 each.=B
Now when you are down to either A or B after measurement 1, you need the next measurement to (a) reduce the problem set to 3 and (b) to know whether anser is more or less. Now you cannot compare a group of 4 to 4, as in the best case it will only reduce the problem to 4 elements which is not good enough.
If you have to choose a set of 3 to compare, you cannot pick any 3 on the same side from the same set (A or B) because if you do this, a quick check will show you that in every choice there is a case where you can only get down to 4 elements. Eg. If you weighed {1,2,3} v/s {5,9,10} and they were equal you're problem would only reduce to {4,6,7,8}
The easiest way to solve this then is to compare 3 to 3, and make sure each side has elements from both AB such that whatever the measurement outcome in the worst case the problem reduces to 3 elements only. Which is why the sets {1,5,9} and {2,6,7} OR {A,B,C}{A,B,B}. The extra element from C is just taken to make the problem symmetric so to say, we have 8 elements and we make it 9, to compose 3 sets of 3 each.=B