How to Detect a Counterfeit Coin: Solving the 12 Coins Puzzle

# How to Detect a Counterfeit Coin: <br> Solving the 12 Coins Puzzle ## Problem Statement Imagine you have 12 coins, one of which is counterfeit. The counterfeit coin looks identical to the others but weighs differently. However, you don't know if it’s lighter or heavier than the genuine coins. The challenge is to identify the counterfeit coin and determine whether it’s lighter or heavier using a balance scale and only three weighings. ### Variations of the Problem 1. **Simple Version**: Identify the counterfeit coin without determining if it's lighter or heavier. 2. **Difficult Version** (discussed here): Identify the counterfeit coin *and* determine whether it is lighter or heavier. The second version is more challenging, requiring careful strategy and logical reasoning. Let's dive into one possible solution. --- ## One Possible Solution This solution is one of many possible approaches. Here, we number the coins from 1 to 12 and perform three weighings. Each weighing has three possible outcomes: - **Left side is heavier** - **Balanced** - **Right side is heavier** ### Step-by-Step Solution 1. **First Weighing**: Place coins 1, 2, 3, 4 on the left side and coins 5, 6, 7, 8 on the right side. - **Left is heavier**: - Second weighing: Place coins 1, 2, 5 on the left and coins 3, 6, 9 on the right. - **Left is heavier**: - Third weighing: Place coin 1 on the left and coin 2 on the right. - If **left is heavier**: Coin 1 is counterfeit and heavier. - If **balanced**: Coin 6 is counterfeit and lighter. - If **right is heavier**: Coin 2 is counterfeit and heavier. - **Balanced**: - Third weighing: Place coin 7 on the left and coin 8 on the right. - If **left is heavier**: Coin 8 is counterfeit and lighter. - If **balanced**: Coin 4 is counterfeit and heavier. - If **right is heavier**: Coin 7 is counterfeit and lighter. - **Right is heavier**: - Third weighing: Place coin 3 on the left and coin 9 on the right. - If **left is heavier**: Coin 3 is counterfeit and heavier. - If **balanced**: Coin 5 is counterfeit and lighter. - If **right is heavier**: This outcome is **impossible**. - **Balanced**: - Second weighing: Place coins 9, 10 on the left and coins 1, 11 on the right. - **Left is heavier**: - Third weighing: Place coin 9 on the left and coin 10 on the right. - If **left is heavier**: Coin 9 is counterfeit and heavier. - If **balanced**: Coin 11 is counterfeit and lighter. - If **right is heavier**: Coin 10 is counterfeit and heavier. - **Balanced**: - Third weighing: Place coin 12 on the left and coin 1 on the right. - If **left is heavier**: Coin 12 is counterfeit and heavier. - If **balanced**: This outcome is **impossible**. - If **right is heavier**: Coin 12 is counterfeit and lighter. - **Right is heavier**: - Third weighing: Place coin 9 on the left and coin 10 on the right. - If **left is heavier**: Coin 10 is counterfeit and lighter. - If **balanced**: Coin 11 is counterfeit and heavier. - If **right is heavier**: Coin 9 is counterfeit and lighter. - **Right is heavier**: - Second weighing: Place coins 1, 2, 5 on the left and coins 3, 6, 9 on the right. - **Left is heavier**: - Third weighing: Place coin 5 on the left and coin 9 on the right. - If **left is heavier**: Coin 5 is counterfeit and heavier. - If **balanced**: Coin 3 is counterfeit and lighter. - If **right is heavier**: This outcome is **impossible**. - **Balanced**: - Third weighing: Place coin 7 on the left and coin 8 on the right. - If **left is heavier**: Coin 7 is counterfeit and heavier. - If **balanced**: Coin 4 is counterfeit and lighter. - If **right is heavier**: Coin 8 is counterfeit and heavier. - **Right is heavier**: - Third weighing: Place coin 1 on the left and coin 2 on the right. - If **left is heavier**: Coin 2 is counterfeit and lighter. - If **balanced**: Coin 6 is counterfeit and heavier. - If **right is heavier**: Coin 1 is counterfeit and lighter. Note: The "Right is heavier" case is basically symmetric to the "Left is heavier" case. --- ### Key Tip for Solving A useful trick is to identify **genuine coins** during the process. For example, if the first weighing (1, 2, 3, 4 vs. 5, 6, 7, 8) is balanced, then coins 1–8 are all genuine. These genuine coins can then serve as references in subsequent weighings. --- ### Visualization The decision tree for the entire process is visualized below. Coins filled in **gray** are the referenced genuine coins identified during the weighings, as mentioned above. Since the width of the image is quite large, feel free to download the image for better clarity. ![coin-min](https://hackmd.io/_uploads/B12uQtfrkl.png) --- ## Analysis To verify the solution, ensure that all possibilities are accounted for. Since there are 12 coins and each could be either lighter or heavier, there are $2 \cdot 12 = 24$ possible outcomes. From the step-by-step procedure: - Each weighing has 3 possible outcomes: **left heavier**, **balanced**, or **right heavier**. - With 3 weighings, there are $3^3 = 27$ possible branches in the decision tree. - Of these, 3 are logically **impossible**, leaving exactly 24 valid outcomes, which matches the problem requirements. --- ## Generalization There are some generalized versions of the problem we can ask: 1. **How many coins can we solve given $n$ weighings?** 2. **If there are $x$ coins, how many times do we need to weigh?** To solve these generalized problems, we can refer to the following: - Using information theory, it can be shown that the number of weighings $n$ and the number of coins $x$ must satisfy the inequality: $$ n \cdot \log_2(3) \geq \log_2(2x) $$ This inequality highlights the exponential growth in the number of solvable coins as the number of weighings increases. For more details, see [this reference (in Chinese)](https://www.math.sinica.edu.tw/media/pdf/d223/22303.pdf). In our example where $n = 3$ and $x = 12$, it satisfies $$ 3 \cdot \log_2(3) \geq \log_2(2 \cdot 12) $$ - Another approach uses the ternary number system. F. J. Dyson provided a proof in 1946 that the maximum number of coins, $X$, detectable by $n$ weighings is: $$ X = \frac{1}{2}(3^n - 3) $$ For example, with $n = 3$, this formula gives: $$ X = \frac{1}{2}(3^3 - 3) = 12 $$ which matches the solution to the 12-coin problem discussed earlier. A brief explanation of this method can be found [here](https://www.math.kent.edu/~soprunova/64091s15/how_to_detect_fake_coin.pdf). --- ## References 1. [如何找出劣幣？簡介訊息與熵的概念 (Chinese)](https://www.math.sinica.edu.tw/media/pdf/d223/22303.pdf) 2. [How to Detect a Counterfeit Coin](https://www.math.kent.edu/~soprunova/64091s15/how_to_detect_fake_coin.pdf) 3. [F. J. Dyson, The problem of the pennies, Mathematical Gazette, 231-234, 1946.](https://www.cambridge.org/core/journals/mathematical-gazette/article/abs/1931-the-problem-of-the-pennies/DFE3B6FA5CEDE824F9B4456EDC2DF808)