A Fake Among Eight Coins

Asked In: Google, Microsoft, Amazon, VMWare, Bloomberg

Key takeaway: This is one of the best algorithmic puzzles to learn step-by-step optimization in problem-solving. 

Puzzle Statement

There are eight identical-looking coins, and one of these coins is fake, which is lighter than genuine coins. What is the minimum number of weighings needed to identify the fake coin with a two-pan balance scale without weights?

Solution Idea 1: Brute force solution 

The basic idea would be to compare each possible pair of coins using balance. Total number of coin pairs = 8C2 = (8 x 7)/2 = 28. So in the worst case, we need to perform 28 comparisons to get the fake coin. The critical question is: can we improve the solution and find the fake coin in fewer comparisons? Let's think further!

Solution Idea 2: Using linear search

The second idea would be to compare each coin in a linear order.

• We first compare the 1st coin with the 2nd coin. If both are not of equal weight, then the lighter coin would be the fake coin.
• Otherwise, we compare the 2nd coin with the third coin. If both are not of equal weight, then the lighter coin would be the fake coin.
• Otherwise, we continue the same process of comparison until we find the fake coin. 
• In the worst case, we need to perform 7 comparisons. Here, the worst case occurs when the fake coin is among the last two coins.

Now we have improved the solution from 28 comparisons to 7 comparisons. Now the critical question is: can we think to improve the solution using a fewer number of comparisons? Let's think!

Solution Idea 3: Comparing coins in pair

Suppose we arrange the coins into 4 groups and start comparing each group. Here are the steps:

• Divide these 8 coins into 4 groups: group[1] = [1,2], group[2] = [3,4], group[3] = [5,6], group[4] = [7,8]
• Now we compare group[1] with group[2]. If group[1] will not have the same weight as group[2], then a fake coin will be present with a lighter weight group.
• If group[1] is of lighter weight, then we compare coin 1 with coin 2. Whichever is lighter, that coin will be the fake coin. 
• If group[2] is of lighter weight, then we compare coin 3 with coin 4. Whichever is lighter, that coin will be the fake coin. 
• If group[1] has the same weight as group[2], then we know coins [1,2,3,4] are good. Now we compare group[2] with the group[3]. If group[2] will not have the same weight as the group[3], then we repeat the above process and find the lighter coin in one comparison.
• If group[2] has the same weight as group[3], then we know the coins [1, 2, 3, 4, 5, 6] are good. Now we compare group[3] with the group[4] and repeat a similar procedure.

So in the worst case, we need to perform 4 comparisons: 3 comparisons for comparing the coins in a group and one comparison for identifying the fake coin in the lighter group.

Now we have improved the solution from 7 comparisons to 4 comparisons. The critical question is: can we improve the solution further and solve it using less than 4 comparisons? Let's think!

Solution Idea 4: Using the divide and conquer strategy

Another idea is to divide the coins into two equal parts and compare them to get the fake coins. Here are the steps:

• We divide the coins into two parts of 4 coins and compare them using the balance. Whichever part is lighter, the fake coin will be present in that part.
• Now we take the lighter part of 4 coins and divide them into pairs of 2 coins. We compare both pairs and again discard the heavier pair.
• Finally, we have only two coins left at the end, so the fake coin must be among these two coins. Now we compare both of them and find the lighter coin or fake coin.

This strategy is similar to the binary search algorithm, where at each step, we are performing one comparison and diving the problem into a smaller subproblem of half input size. So for 8 coins, we need to perform log8 or 3 comparisons to get the fake coins.

Now we have improved the solution from 4 comparisons to 3 comparisons :) The critical question is: can we improve the solution further and solve it using less than 3 comparisons? Is it possible? Let's think!

Solution Idea 5: The efficient solution

This is a specific instance of the problem where we need to find an effcient solution for the 8 coins. So we can deep-dive one step further and use this information to get an efficient solution. Let's think!

• From the given coins, we select two groups of three coins each and put them on the opposite cups of the scale. If their weights are the same, the fake is among the remaining two coins, and weighing them will identify the fake coin.
• If their weights are not the same, then the lighter fake is among the three lighter coins. We take any two of them and put them on the opposite cups of the scale. If they weigh the same, the third coin in the lighter group is fake; if they do not weigh the same, the lighter one is fake.

So, using the above approach, we can solve the problem in only 2 comparisons.

Solution Idea 6: Another effcient solution

The problem has an alternative solution in which the second weighing does not depend on the results of the first one. Suppose we label the coins by the letters A, B, C, D, E, F, G, H. We compare (A, B, C) against (F, G, H) on the first weighing. We weigh (A, D, F) against (C, E, H) on the second weighing.

• If ABC = FGH (the first weighing results in a balance), all these six coins are genuine, and therefore the second weighing is equivalent to weighing D against E.
• If ABC < FGH, only A, B, and C may still be fake. Therefore if on the second weighing:
• If ADF = CEH, B is fake.
• If ADF < CEH, A is fake.
• If ADF > CEH, C is fake.
• The case of ABC > FGH is symmetric to the above scenario. Think!

So, this approach also solves the problem in only 2 comparisons.

References

1. A. Levitin and M. Levitin, Algorithmic Puzzles, Oxford University Press