Coin Weighing Puzzle

The Coin Weighing Puzzle is a classic logic puzzle where the player must identify a counterfeit coin among a set of identical-looking coins using only a balance scale. The fake coin differs in weight from the genuine ones (either heavier or lighter), and the player has a limited number of weighings to find it. The challenge lies in designing a weighing strategy that systematically narrows down the possibilities through logical deduction, making optimal use of every comparison.

Rules

1. You are given N coins that all look identical. One coin is counterfeit.
2. The counterfeit coin is either heavier or lighter than the genuine coins (this may or may not be specified in advance).
3. You have a balance scale that compares two groups of coins: it tips toward the heavier side or stays level if both sides are equal.
4. You have a limited number of weighings (typically 2-4 depending on the number of coins).
5. After your weighings, you must identify both which coin is counterfeit and whether it is heavier or lighter.
6. You cannot use any other measuring device — only the balance scale.

Classic Variants

| Coins | Weighings | Known heavier/lighter? | Difficulty |

|-------|-----------|----------------------|------------|

| 8 | 2 | Yes (heavier) | Easy |

| 9 | 2 | Yes (heavier) | Easy |

| 12 | 3 | No | Classic / Hard |

| 27 | 3 | Yes (heavier) | Medium |

| 13 | 3 | No | Expert |

Strategies

• Divide into Thirds: The optimal first weighing divides the coins into three equal groups (or as close as possible). Weigh group A against group B; the result tells you which third contains the counterfeit. This is because a three-way balance (left heavy, right heavy, or balanced) gives the most information per weighing.
• Information Theory: Each weighing has three possible outcomes, so K weighings can distinguish among 3^K possibilities. For 12 coins with unknown heavy/light, there are 24 possibilities (12 coins x 2 states), and 3^3 = 27 ≥ 24, so 3 weighings suffice.
• Tracking Suspicion: After each weighing, categorize coins as "possibly heavy," "possibly light," "suspect," or "cleared." Only coins that have appeared on the heavy side of a tipping scale can be "possibly heavy."
• Mixing Groups: In subsequent weighings, mix coins from different suspicion categories. By observing how the result changes when a suspect coin moves sides, you can deduce its status.
• The Reference Coin: If you have identified any coin as genuine from a previous weighing (it was on a balanced scale), you can use it as a reference in later weighings.
• Process of Elimination: Sometimes the fastest path is to eliminate coins rather than identify the fake. If a weighing balances, all coins on the scale are genuine.

Coin weighing puzzles have an ancient lineage connected to the practical need to detect counterfeit currency. Balance scales were among the earliest precision instruments, used in Mesopotamia and Egypt as far back as 5000 BCE for trade. The problem of detecting a fake coin among genuine ones has been a concern of merchants, moneylenders, and governments for millennia.

The mathematical formulation of the coin weighing puzzle entered recreational mathematics in the early 20th century. The classic 12-coin problem — find one counterfeit among 12 coins in three weighings, determining whether it is heavy or light — became famous when it appeared in various mathematics journals in the 1940s. It was popularized by mathematician Howard Grossman, who published a solution in the "American Mathematical Monthly" in 1945. The puzzle quickly became a standard in mathematical puzzle books and job interview questions.

The theoretical foundations were formalized through information theory. Claude Shannon's work on information content (1948) provided the mathematical framework to prove optimal bounds: with K weighings, one can distinguish among at most (3^K - 3)/2 coins when the heavy/light status is unknown, or (3^K - 1)/2 when it is known. This elegant connection between a physical puzzle and abstract information theory made coin weighing a favorite teaching tool in computer science and mathematics courses.

The coin weighing puzzle has remained a staple of logic puzzle collections, competitive mathematics, and technical interviews at companies like Google, Microsoft, and Goldman Sachs. Its appeal lies in the beautiful interplay between physical intuition (a balance scale) and abstract reasoning (information-theoretic optimality). Digital implementations add interactivity by letting the player perform weighings and track results visually, making the puzzle accessible to a broader audience.