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

[sachins]

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 ?

 

[Bill Simpson]

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.

 

[chiro]

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.

 

[Simon Bridge]

@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.

 

[sachins]

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.

 

[Simon Bridge]

That minimum of one is "a posteriori" ... that is, you have certainly found the bad can after the fact or opening just one, if the first one is bad.

Depending on the context, that may be the correct answer.

However, the question kinda seems more like you need to find a strategy which minimizes the number of cans you have to open a priori to be certain of finding the bad can ... so you can tell someone: follow this sampling strategy for the first 100 cans (or whatever). In which case your instructions, for certainty must be to "keep using this strategy until the bad can is found". So we cannot be certain, before the fact that opening any N<400 cans will uncover the bad can.

What you can try to do is to adopt a sampling strategy that minimizes the expectation of the number of cans you'll have to open.

The strategy you have picked still looks like an elaborate sampling without replacing - how would it have any advantage over, say, picking one at random from the 400, if it is bad, then end, if good, then pick again from the remaining 399, repeat.

For that matter, is it better than just lining the cans up and checking them in order?

As asked, the question could be aimed at getting you to examine different sampling strategies.

I suspect the real question is just asking how many cans you have to check before unearthing the bad one.
In that case you'd construct the statistics - median with upper and lower quartiles say.

I've seen it asked like this:
You take refuge from a nuclear war in your fallout shelter - which is well stocked with 400 cans.
Unfortunately, too late, you discover, from the shipping manifest, that some idiot stocked 399 cans of peaches and one of beef stew ... and none of the cans have labels. How many peach meals will you look forward to eating before you get to enjoy your stew?

 

[mathman]

If you MUST find the bad can, you have no choice but to keep opening them until you find it. The order of opening the cans makes no difference, that is: there is no particular strategy.

 

[rcgldr]

If you MUST find the bad can, you have no choice but to keep opening them until you find it. The order of opening the cans makes no difference, that is: there is no particular strategy.

If the report of one can being bad is made with certainty, in the extremely rare case of opening 399 good cans, the 400th can can be assumed to be bad.

As mentioned above, this doesn't seem like the intent of the problem, and it's likely that the "bad" can is supposed to weigh differently than the other cans (or it may be known to weigh less or weigh more), in which case a strategy can be used to reduce the number of weighings.

 

[Simon Bridge]

Though - that reckons without the perversity of math professors who may well set a problem like that specifically to force students who believe there may be some minimizing strategy to the realization that there isn't ;)

 

[Hepth]

I think this is the problem:
There exists 400 cans. One can weighs differently. Find the minimum number of measurements needed to find the special can.

So you do the thing where you split it into groups and weigh them against each other. Its a common math problem.

If there is no weight difference, well then its not really a math problem.

 

[Simon Bridge]

@Hepth: that's right - see last sentence post #2.