The Fake Coin Problem is a classic puzzle that involves identifying a single counterfeit coin among a set of identical-looking coins using a balance scale. The counterfeit coin differs in weight, either being lighter or heavier than the genuine ones. The objective is to determine which coin is counterfeit and, if applicable, whether it is lighter or heavier, using the fewest number of weighings possible.
The problem is to design an efficient algorithm for detecting the fake coin. An easier version of the problem—the one we discuss here assumes that the fake coin is known to be, say, lighter than the genuine one.
The most natural idea for solving this problem is to divide n coins into two piles of n/2 coins each, leaving one extra coin aside if n is odd, and put the two piles on the scale. If the piles weigh the same, the coin put aside must be fake; otherwise, we can proceed in the same manner with the lighter pile, which must be the one with the fake coin.
Table of Contents
The Basics of the Problem
Imagine you have a set of 12 coins, one of which is fake. You are given a balance scale and must find the fake coin in as few weighings as possible. The challenge lies in the fact that you don’t know whether the fake coin is lighter or heavier.
So to solve this, we can easily set up a recurrence relation for the number of weighings W(n) needed by this algorithm in the worst case:
W(n) = W([n / 2] ) + 1 for n > 1, W(1) = 0
This recurrence should look familiar to you. Indeed, it is almost identical to the one for the worst-case number of comparisons in binary search. This similarity is not really surprising, since both algorithms are based on the same technique of halving an instance size. The solution to the recurrence for the number of weighings is also very similar to the one we had for binary search: W(n) = [ log2 n ].
This stuff should look elementary by now, if not outright boring. But wait: the interesting point here is the fact that the above algorithm is not the most efficient solution. It would be more efficient to divide the coins not into two but into three piles of about n/3 coins each. After weighing two of the piles, we can reduce the instance size by a factor of three.
Accordingly, we should expect the number of weighings to be about log3 n, which is smaller than log2 n.
Pseudocode for Fake Coin Problem
function findFakeCoin(coins):
if coins.length == 1:
return coins[0]
if coins.length == 2:
return (coins[0] is lighter) ? coins[0] : coins[1]
if coins.length == 3:
return (coins[0] == coins[1]) ? coins[2] : ((coins[0] == coins[2]) ? coins[1] : coins[0])
divide the coins into three groups: group1, group2, group3
if coins.length is not a multiple of 3:
add extra coins to groups to make them equal, remember the original size
weight1 = weigh(group1, group2)
if weight1 == 0: // group1 == group2
return findFakeCoin(group3)
else if weight1 < 0: // group1 is lighter
return findFakeCoin(group1)
else: // group2 is lighter
return findFakeCoin(group2)
function weigh(groupA, groupB):
totalWeightA = sum weights of coins in groupA
totalWeightB = sum weights of coins in groupB
if totalWeightA == totalWeightB:
return 0
else if totalWeightA < totalWeightB:
return -1
else:
return 1
Strategies and Solutions
Method 1: Divide and Conquer Approach
Steps:
- Split into Three Groups: Divide coins into three equal groups.
- Weigh Two Groups:
- If both groups weigh the same, the fake coin is in the remaining group.
- If they differ, the fake is in the lighter or heavier group.
- Repeat until one coin remains.
Below is the Java Code for the this approach.
import java.util.ArrayList;
import java.util.List;
public class FakeCoinProblem {
public static void main(String[] args) {
// Example usage: Let's say we have 10 coins and the fake coin is at index 7 (0-based index)
List<Integer> coins = new ArrayList<>();
for (int i = 0; i < 10; i++) {
coins.add(10); // All coins have weight 10
}
coins.set(7, 9); // Set one coin to be lighter (weight 9)
int fakeCoinIndex = findFakeCoin(coins);
System.out.println("The fake coin is at index: " + fakeCoinIndex);
}
public static int findFakeCoin(List<Integer> coins) {
if (coins.size() == 1) {
return 0; // If there's only one coin, it must be the fake one
}
int n = coins.size();
int size = (n + 2) / 3; // Divide the coins into three nearly equal groups
List<Integer> group1 = new ArrayList<>(coins.subList(0, size));
List<Integer> group2 = new ArrayList<>(coins.subList(size, 2 * size));
List<Integer> group3 = new ArrayList<>(coins.subList(2 * size, n));
int weight1 = weigh(group1);
int weight2 = weigh(group2);
if (weight1 == weight2) {
return size * 2 + findFakeCoin(group3); // Fake coin is in group3
} else if (weight1 < weight2) {
return findFakeCoin(group1); // Fake coin is in group1
} else {
return size + findFakeCoin(group2); // Fake coin is in group2
}
}
public static int weigh(List<Integer> group) {
int totalWeight = 0;
for (int coin : group) {
totalWeight += coin;
}
return totalWeight;
}
}
Explanation
- Main Method:
- Creates a list of 10 coins with the same weight except one, which is lighter.
- Calls the findFakeCoin method to determine the index of the fake coin.
- findFakeCoin Method:
- If there’s only one coin, it must be the fake one.
- Divides the coins into three nearly equal groups.
- Weighs the first two groups to determine which group contains the fake coin.
- Recursively calls itself on the group with the fake coin until the fake coin is found.
- weigh Method:
- Calculates the total weight of a group of coins.
To visualize the ternary search approach, consider the following decision tree for 9 coins (where the fake coin is lighter):
- First Weighing: Split into 3 groups (A, B, C). Weigh A vs. B.
- If A == B → Fake is in C.
- If A < B → Fake is in A.
- If A > B → Fake is in B.
- Second Weighing: Take the suspect group (e.g., C) and split into C1, C2, C3. Weigh C1 vs. C2.
- If C1 == C2 → Fake is C3.
- Else, the lighter one is fake.
This method guarantees finding the fake coin in 2 weighings for 9 coins (log₃9 = 2). For larger sets (e.g., 27 coins), it scales to 3 weighings.
Step-by-Step Visual Solution
Maximum weighings needed: log₃N (e.g., 3 weighings for 27 coins).
Method 2: Binary Decision Tree
Steps:
- Split and Weigh: Compare two halves.
- Continue Based on Weighing:
- If the two halves balance, the fake coin is elsewhere.
- If one half is lighter or heavier, continue with the affected half.
- Repeat until isolating the fake coin.
Below is the Python Code for this approach.
def find_fake_coin_binary(coins):
left, right = 0, len(coins) - 1
while left <= right:
mid = (left + right) // 2
if weigh(coins[left:mid+1]) != weigh(coins[mid+1:right+1]):
if weigh(coins[left:mid+1]) < weigh(coins[mid+1:right+1]):
right = mid # Fake is in the left half
else:
left = mid + 1 # Fake is in the right half
else:
left = mid + 1
return coins[left]
# 'weigh' simulates weighing a group.
Method 3: Matrix Strategy (Advanced)
Steps:
- Set Up a Matrix: Design a matrix where each row represents a unique weighing configuration.
- Weigh and Analyze: Use the matrix to perform simulated weighings.
- Identify the Fake Coin: Based on outcomes, deduce the fake coin’s identity.
Below is the Python code for this approach.
import numpy as np
def setup_weight_matrix(num_coins):
matrix = np.identity(num_coins) # Simplified setup
for i in range(num_coins):
matrix[i, i] = -1 if i % 2 == 0 else 1
return matrix
def find_fake_coin_matrix(coins):
weight_matrix = setup_weight_matrix(len(coins))
for i, row in enumerate(weight_matrix):
result = weigh_with_matrix(row, coins)
if result != 0:
return i # Index of the fake coin
def weigh_with_matrix(row, coins):
return np.dot(row, coins) # Simulate weighing by dot product
While the Fake Coin Problem might seem like a simple parlor trick, its principles have real-world applications in areas such as quality control, algorithm design, and even cryptography. The logic and strategy used to solve this puzzle can be applied to any scenario where you need to identify anomalies or outliers in a large dataset.
Advanced Variant: Unknown Fake Weight
- First Weighing: Weigh 4 coins vs. 4 (for 12 coins).
- If equal → fake is in the remaining 4.
- If unequal → note which side was heavier/lighter.
- Second Weighing: Swap 3 coins between groups and re-weigh.
- The direction of imbalance reveals if the fake is heavier/lighter.
Tip: For a generalized solution, explore the "information theory" approach, where each weighing provides log₃(2) bits of information.
Performance Benchmarking
Method | Weighing’s for 9 Coins | Weighing’s for 81 Coins | Time Complexity |
Ternary Search | 2 | 4 | O(log₃ n) |
Binary Search | 4 | 7 | O(log₂ n) |
Linear Search | 9 (worst-case) | 81 | O(n) |
Real-World Applications
Beyond the Basics
The Fake Coin Problem can be extended to more complex scenarios, such as:
- Finding multiple fake coins.
- Solving the problem with an unknown number of fake coins.
- Adapting the puzzle to coins with varying degrees of deviation in weight.
- Cryptography: The problem mirrors divide-and-conquer attacks in hashing algorithms, where adversaries isolate vulnerabilities.
- Quality Control: Factories use similar logic to detect defective products in batches.
- Machine Learning: Techniques like ternary search optimize hyperparameters faster than binary methods.
Conclusion
The Fake Coin Problem is more than just a puzzle—it’s a test of logic, strategy, and analytical thinking. By mastering this problem, you not only hone your problem-solving skills but also gain insights into the power of systematic reasoning.
Related Articles
Frequently Asked Questions
The ternary search method runs in O(log₃ n) time, as each weighing reduces the problem size by a factor of 3. For example:
- 9 coins → 2 weighings (log₃9 = 2).
- 27 coins → 3 weighings (log₃27 = 3).
In a pile of real coins, the fake coin problem looks for one counterfeit coin that weighs one gram less. To identify the fake, we employ a scale and a Decrease-and-Conquer tactic. Until you locate the phony coin, one technique is to recursively split the unknown pile into three equal piles.