Least number of trials to find a can with bad food out of a batch.

by sachins
Tags: computer algorithms, optimization, probabality, taguchi
 P: 2 hi everyone . i came across this interesting problem but am not able to figure it out . In a factory that packs food in cans , there is a report that in a particular batch of 400 cans by error a poisonous chemical has been packed instead of food item. Checking 400 cans would be a big loss but neither the manager can allow a can with poisonous chemical to remain undiscovered as it is dangerous. What is the minimum number of cans that need to be checked so that the bad Can is discovered with certainty ?
 P: 973 I think you are saying that there is one bad can in 400 cans and there is no way other than opening that bad can to detect that bad can. So open and test the cans one at a time until the bad can is discovered. The minimum number of cans that need to be tested is one. But sometimes you will not be that lucky. On average you will need to open half the cans. If you are very unlikely you will need to open 400 cans to find the bad can.
 P: 4,570 Hey sachins and welcome to the forums. If you are looking at complete certainty, then you need to check every can. If however you want to do so with some kind of probability, then you will need to use some kind of Binomial or related distribution and find a valid n value (number of cans you need to check) that corresponds to a particular probability. If everything is independent (same chance for every can to have poison) then the Binomial is your distribution and you have to solve for a value of n corresponding with your probability. If not, then you have a more complex model ranging from a PGF model (probability generating function), markov model of some order, or a model with a complex joint density function that has all kinds of dependencies. In these kinds of problems, the binomial model is often used but it may not be appropriate.
Homework
HW Helper
Thanks ∞
PF Gold
P: 11,101

Least number of trials to find a can with bad food out of a batch.

@sachins: welcome to PF;
IRL - the loss to the company of accidentally leaving the bad can in is usually much greater than that of pulling the entire batch and just chucking them is usually cheaper than checking them all ... so that's what happens.
Thus the minimum number of cans that need to be checked is zero - you know they are certainly inside the 400 batch: chuck the lot.

Where did you come across this problem?
For "certainty" you normally get some extra information - like the bad can weighing exactly 10g less than the good ones.
 P: 2 Thank you Simon, Bill And Chiro . I do think there must be more data given viz weight of bad can different from the good one . In such case there is no need to open the can . Else , one can apply any sampling method to keep checking by opening up the cans for eg : arrange the cans in a square array . Pick a random can ; if it is not bad find the half in which it lies and then again pick randomly from the other half . Again find out the half of the half in which it lies and pick the other half to choose a random can ...a dn so on till you get to a (half)^n which has just one can . Now if all of them do not have a bad can, you substract that number from 400 and begin the process again. 400 200 100 50 25 12.5 6.125 3. 1. 1 1 1 1 1 1 1 1 1 (9 cans checked , all good then repeat but with 400-9 =391 cans) 391 196 98 49 25 12.5 6. 3. 1. 1 1 1 1 1 1 1 1 1 382 .......................................... So there can be minimum one can that need to be checked . But it seems i have an inaccurate question here. It was asked by a friend to me. So if you guys come across the real version of this question do post.