Out of 80 coins, one is counterfeit. What is the minimum number of weighings need to find out the counterfeit?

2 Responses to “Out of 80 coins, one is counterfeit. What is the minimum number of weighings need to find out the counterfeit?”

1. Billy C says:

   October 4, 2009 at 8:17 am

   I assume that this is one of those problems where you are weighing the coins relative to each other on a balance scale.

   One weighing would suffice, if you happened to pick the right two coins (and if you knew whether the counterfeit was heavier or lighter).

   If you know whether the counterfeit coin is heavier or lighter, then there are 80 possible cases, corresponding each of the 80 coins. Each weighing has 3 possible outcomes (1. Left side heavier, 2. Right side heavier, 3. Sides balance), so 4 weighings can have 3^4 = 81 different outcomes, which suffices to distinguish all 80 cases.

   If you don’t know whether the counterfeit coin is heavier or lighter, then there are 160 possible outcomes, corresponding to each of the 80 coins being either heavier or lighter. Each weighing has 3 possible outcomes. Four weighings do not suffice, since they only distinguish 80 different cases. But five weighings distinguish 3^5=243 different cases, which is plenty to identify the bad coin & whether it is heavier or lighter than the rest.

   ____

   Edit: Mr. Causality has given an interesting argument, but I think his formula overestimates the number of weighings required. For instance, his formula says that 4 weighings are needed to find the counterfeit among 9 coins. My analysis says that 3 weighings are enough. Here is an algorithm showing that 3 weighings suffice:

   Divide the 9 coins into 3 piles of 3, which we represent as sets:
   Pile A: {1, 2, 3}
   Pile B: {4, 5, 6}
   Pile C: {7, 8, 9}
   In the following we will indicate which is the heavier side with the "greater than" sign; for example {1,2,3} > {4,5,6} indicates that the pile of coins 1, 2, and 3 is heavier than the pile of coins 4, 5, and 6:

   First weighing: {1,2,3} vs. {4,5,6}

   If {1,2,3} > {4,5,6}

   - Second weighing {1,4} vs. {2,5}

   - If {1,4} > {2,5}

   - Third weighing {1} vs. {4}
   - If {1} > {4}, then 1 is the counterfeit and is heavier
   - If {1} = {4}, then 5 is the counterfeit and is lighter

   - If {1,4} < {2,5}
   - Third weighing {2} vs. {5}
   - If {2} > {5}, then 2 is the counterfeit and is heavier
   - If {2} = {5}, then 4 is the counterfeit and is lighter

   - If {1,4} = {2,5}
   - Third weighing {1} vs. {3}
   - If {1} < {3} then 3 is the counterfeit and is heavier
   - If {1} = {3} then 6 is the counterfeit and is lighter

   If {1,2,3} < {4,5,6}, we follow a procedure symmetric to the one described above, which suffices to determine whether any of the coins 1-3 are counterfeit and lighter, or any of the coins 4-6 are counterfeit and heavier.

   Finally, if {1,2,3} = {4,5,6}, then
   - Second weighing {7} vs. {8}
   - If {7} > {8}
   - Third weighing {7} vs. {9}
   - If {7} > {9} then 7 is the counterfeit and is heavier
   - If {7} = {9} then 8 is the counterfeit and is lighter

   - If {7} < {8}
   - Third weighing {7} vs. {9}
   - If {7} < {9} then 7 is the counterfeit and is lighter
   - If {7} = {9} then 8 is the counterfeit and is heavier

   If {7} = {8}
   - Third weighing {7} vs. {9}
   - 9 is the counterfeit and is heavier or lighter accordingly as it compares to 7.
   ____

   Edit again: I see now the meaning of Mr. Causality’s formula. It is elegant and correct. Give him the points.
2. mrcausality says:

   October 4, 2009 at 8:17 am

   Assuming you have no information of the weight of non-counterfeit coins and you have an "old-fashioned" balance scale, the answer I get is CEILING(ln(80)/ln(2)) = 7.

   Let N(n) be the minimum # of weighings required on a balance scale to determine for sure the counterfeit among n coins where n >= 3. I will denote C(1-n) be a coin label (e.g. C4 is coin 4). Clearly, N(n+1) >= N(n).

   The first few are:

   N(3) = 2 [C1 vs C2 + C1(2) vs C3 if required]
   N(4) = 2 [C1 vs C2 + C1 vs C3(4) ]
   N(5) = 3 = 1 + N(3) [5=2+3] = 1 + N(4) [5=1+4]
   N(6) = 3 = 1 + N(3) [6=3+3] = 1 + N(4) [6=2+4]
   N(7) = 3 = 1 + N(4) [7=3+4]
   N(8) = 3 = 1 + N(4) [8=4+4]
   N(9) = 4 = 1 + N(5) [9=4+5] = 1 + N(6) [9=3+6] = 1 + N(7) [9=2+7] = 1 + N(8) [9=1+8]
   N(10) = 4 = 1 + N(8) [10=2+8] = 1+N(7) [10=3+7] = 1 + N(6) [10=4+6] = 1 + N(5) [10=5+5]
   …
   N(20) = 5 = 1 + N(10) [20 = 10 + 10] = …
   N(40) = 6 = 1 + N(20) [40 = 20 + 20] = …
   N(80) = 7 = 1 + N(40) [80 = 40 + 40] = …

   In general we have the form N(n) = CEILING(ln(n)/ln(2)) = 1 + N(n/2) [n even] or 1 + N((n+1)/2) [n odd].

   *** EDITED in light of BillyC’s comments ***

   BillyC is correct in pointing out my error. The log base needed is 3, not 2, since the scale can take 3 states. If there are n coins, and we take k measurements, there will be 3^k possible states to select the artificial coin. At a minimum, we must have 2n pieces of information to determine which coin is counterfeit (n for the each coin and 2n accounting for the fact it can be either heavier or lighter).

   Thus, we have an inequality in the weighings,

   3^k >= 2n

   k >= log3(2n)

   The minimum is then N(n) = CEILING(log3(2n)). This is consistent with BillyC’s finding for n=9 and my previous ones for n=3 … 8. For n=80, this formula yields N(80) = 5 which is indeed less than previously stated.