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$?