Algorithm to find minimum number of weightings required to find defective ball from a set of n balls

Question

Okay here is a puzzle I come across a lot of times- Given a set of 12 balls , one of which is defective (it weighs either less or more) . You are allow to weigh 3 times to find the defective and also tell which weighs less or more.

The solution to this problem exists, but I want to know whether we can algorithmically determine if given a set of 'n' balls what is the minimum number of times you would need to use a beam balance to determine which one is defective and how(lighter or heavier).

Answer 1

Trichotomy ! :)

Explanation : Given a set of n balls, subdivide it in 3 sets A, B and C of n/3 balls.

Compare A and B. If equal, then the defective ball is in C. etc.

So, your minimum number of times is the number of times you can divide n by three (sorry, i do not know the english word for that).

Answer 2

A wonderful algorithm by Jack Wert can be found here

• http://www.cut-the-knot.org/blue/OddCoinProblems.shtml

(as described for the case n is of the form (3^k-3)/2, but it is generalizable to other n, see the writeup below)

A shorter version and probably more readable version of that is here

• http://www.cut-the-knot.org/blue/OddCoinProblemsShort.shtml

For n of the form (3^k-3)/2, the above solution applies perfectly and the minimum number of weighings required is k.

In other cases...

---

Adapting Jack Wert's algorithm for all n.

In order to modify the above algorithm for all n, you can try the following (I haven't tried proving the correctness, though):

First check if n is of the from (3^k-3)/2. If it is, apply above algorithm.

If not,

If n = 3t (i.e. n is a multiple of 3), you find the least m > n such that m is of the form (3^k-3)/2. The number of weighings required will be k. Now form the groups 1, 3, 3^2, ..., 3^(k-2), Z, where 3^(k-2) < Z < 3^(k-1) and repeat the algorithm from Jack's solution.

Note: We would also need to generalize the method A (the case when we know if the coin is heavier of lighter), for arbitrary Z.

If n = 3t+1, try to solve for 3t (keeping one ball aside). If you don't find the odd ball among 3t, the one you kept aside is defective.

If n = 3t+2, form the groups for 3t+3, but have one group not have the one ball group. If you come to the stage when you have to rotate the one ball group, you know the defective ball is one of two balls and you can then weigh one of those two balls against one of the known good balls (from among the other 3t).

Answer 3

You could use a general planning algorithm: http://www.inf.ed.ac.uk/teaching/courses/plan/