Comparison trees

You have 60 coins. You know that 1 coin is either lighter or heavier than the other coins. How many comparisons are needed in a worst case scenario to discover which coin is the false one and whether or not it’s light or heavier than the rest?

I had this question on a quiz the other day in my discrete math class. The answer was shown to be $\lceil \log_3 120\rceil$, which is 5.

A second question was asked:

If you know the coin is lighter than the rest and you had the same number (60), how many comparisons, worst case, would be needed?

which was $\lceil \log_3 60\rceil$, which is 4.

I was wondering if someone could explain to me why this is the correct answer. Why $\log_3$?

Solutions Collecting From Web of "Comparison trees"

In the one-coin-lighter case: Divide the 60 coins into three sets of 20. But one of the three groups in one pan of the balance and another in the other pan. If their weights are different, you know which group of 20 contains the lighter coin, and if they’re the same, then you also know which group (the one that’s not being weighed).

Divide the remaining 20 into two sets of 7 and one set of 6. Weigh the two sets of 7 against each other. Then you have either a set of 6 or a set of 7.

If the latter then in the next weighing if you use two sets of three, with one not weighed, you could narrow it to one coin and you’re done, but it you narrow it to three, you need one more weighing, with one coin in each pan. If you use two sets of two, with three coins not weighed, then no matter what the outcome you’ll need one more weighing.

Four weighings are enough.

Now notice what’s happened: each time you cut the number of coins in the pan down to $1/3$ of the previous number, possibly rounding up to the nearest integer.

$60/3=20$. Then $20/3 \approx 7$. Then $7/3\approx 3$. Then $3/3=1$. The number of times you can divide by 3 is the number of 3s you need to multiply to get 60, i.e. it’s the base-3 logarithm.

Essentially, the reason is that any weighing gives you 3 possible answers: Same weight, left side heavier, right side heavier. So if you set up your weighings properly, each weighing should divide the space of possible weight distributions into three roughly equal-sized sets.

So for the first case, you have 120 possible weight distributions (coin j is fake, j = 1…60, and it is heavier/lighter than the others), and in the second case you have 60. After one weighing, you should have only 40 (resp. 20) cases remaining, after two weighings you should have ~14 (resp. 7), etc.

This is a classic puzzle. There are lots of sites dedicated to its solution. This MathTrek column by Ivars Peterson has a pretty nice explanation.