Find the fake coin puzzle - why are weightings required $log_3(n)$?

Question

This is the classic counterfit coin puzzle. You are given $n$ coins and one of them lighter than all the others (the others being identical). How do you find it in the minimum number of weightings possible? The post here: https://www.geeksforgeeks.org/decision-trees-fake-coin-puzzle/ says that you can always do this in $\lceil \log_3(n) \rceil$. The general reason is that each weighing can have three outcomes. I can't make sense of this. How do the three outcomes of the weightings map to splitting $n$ three ways repeatedly until you get to one number in the leaves?

Answer 1

The idea is that you split the coins into three groups, as even as possible, and weigh two of them. The $3$ possible outcomes are

• the scale tips to one side, in which case the fake coin is on the other side
• the scale is balanced and the fake coin is in the unweighed group

Answer 2

You put $1/3$ of the coins on each pan and keep the last $1/3$ of the coins off the balance. If the coins balance, the bad coin is in the $1/3$ that are off the balance. If the coins do not balance, the fake coin is in the light $1/3$. Either way, the number of possibilities is divided by $3$ each time you use the balance.

It works the same if you don't know if the bad coin is heavy or light. Again if the two groups balance the bad one is off the scale. If they do not balance, you have $1/3$ of the coins that might be bad, but only if they are heavy and another $1/3$ that might be bad but only if they are light. This is enough information to cut the possibilities by a factor $3$ each step as well.

Answer 3

$$\lceil x \rceil = a$$

is equivalent to

$$a \lt x \le a + 1$$

Let $x = \log_3(n)$

$$a \lt \log_3(n) \le a + 1$$

Taking powers of 3,

$$3^a \lt n \le 3^{a + 1}$$

When you divide $n$ by 3, you are left with a remainder $\le 3 (\equiv n \mod 3)$ .

When you split $n$ into three almost equal piles, you have a number of the form $3k + r$ where $r \in \{0, 1, 2\}$. If you have $r = 0$, all three piles are equal. If you have $r = 1$, two of the piles are equal and the third has 1 excess. If $r = 2$, two of the piles are equal and the third has 1 less.

So, in $a < x \le a+1$ measurements, we can discern which pile is defective.

$\therefore, x = \log_3(n)$.