| Pretend you only had 3 coins. The idea is -- when you use the scale to measure 2 coins against each other -- you actually gain "information" about all three coins. This is because there are 3 possible scenarios: 1. the biased coin is on the right side of the scale, 2. the biased coin is on the left side of the scale, 3. or the biased coin is the coin not measured (since the scale is balanced). In essence, even though this scale only has 2 sides, you gain information proportional to having 3 sides. Hence if we were to extend this to a scenario where you had n coins, of which one was biased and others fair, you would only need log_3 n measurements total to find the biased coin. This idea has pretty neat applications. For example, if you wanted to prove that merge sort has a O(n log n) computational complexity, you can use this scale idea. |