Spot the Fake
One of N coins is slightly heavier than the others. How large can N be if the coin can be determined with only two weighings with a set of scales?
Age
14 to 16
Challenge level
Problem
One coin among $N$ identical-looking coins is a fake and is slightly heavier than the others, which all have the same weight. To compare two groups of coins you are allowed to use a set of scales with two pans which balance exactly when the weight in each pan is the same. What is the largest value of $N$ for which the fake coin can be identified using a maximum of two such comparisons?
If you liked this problem, here is an NRICH task that challenges you to use similar mathematical ideas.
Student Solutions
At each weighing we should compare two sets of coins where each set has the same number of coins. There are three outcomes:
- Left-hand set is heavier
- Right-hand set is heavier
- The sets have equal weight.
In case 1, the fake coin is in the left-hand set, in case 2, the fake coin is in the right-hand set and in case 3 the fake coin is in neither set.
Consider the following flowchart. Each red/blue ellipse represents a weighing. If the left-hand set is heavier follow the red arrow, if the right-hand set is heavier follow the blue arrow and if the two sets are the same weight follow the purple arrow.
Image
There are $9$ possible routes through the flowchart and so there are $9$ possible outcomes. At the end of the two weighings you could end up at any outcome and we want to be able to tell which coin is fake, so we can only test at most $9$ coins.
Can we test $9$ coins? Yes. Label the coins $1$,$2$,$3$,...,$9$ and see the diagram below.
Image
For example, if the set $1$,$2$,$3$ has the same weight as $4$,$5$,$6$ the the fake coin must be one of $7$,$8$,$9$.
If $7$ is heavier than $8$ then $7$ is fake, or
if $8$ is heavier than $7$ then $8$ is fake, or
if $7$ and $8$ are the same weight then $9$ is fake.
So the largest possible value for $N$ is $9$.