combinatorics - Prove that the scale needs to be used atleast 3 times to determine the heaviest coin

There are 8 coins identical in all respects. Except one of them weighs heavier than others.

There is a scale to weigh coins.

We need to find the minimum number of times we need to use the scale to determine the coin.

I can solve this using by using the scale three times. Like binary search

I am looking for a proof that there is no way to solve the problem with less than 3 uses of the scale. I am not sure whether that is the case. I believe it is because I can't find a way to do it in less than three.

There is a way to do it in 2 uses in the answer by Klaus. Can it be proven that 2 is indeed the minimum? I am more interested in the proof than a way to actually solve the problem.

Answer

Assuming a balance scale, you can actually do it in $2$. Weigh $3$ and $3$ random coins. If one group of $3$ weighs more, the heavier coin must be in those $3$. If the balance is equal, the heavier one must be in the remaining $2$. Now do the same again with the remaining $2$ or $3$ coins.

EDIT: As a response to the comment: Yes, it is a pigeonhole argument. At each step a coin is either weighed on the left side $(0)$, on the right side $(1)$ or not weighed $(2)$. Coins which are weighed together cannot be distinguished. So after $k$ weighings every coin is assigned a sequence, e.g. $000$, $010$, $221$ after $3$ weighings, etc. Now if there are more coins than combinations of $0$, $1$ and $2$, some coins must have the same sequence assigned, no matter how you actually perform the weighings. Those cannot be distinguished, hence you don't know which coin it is in the worst case (of course, you may always get lucky). In this case, after one weighing, every coin is assigned only one number ($0$, $1$ or $2$), hence at least two (in fact even three) coins need to have the same number assigned. Hence there is no way of doing it with only one weighing. After two weighings there are nine combinations and eight coins, hence it works with two weighings. Similarly you could prove that $3$ is the minimum if only outcome $0$ and $1$ are allowed (e.g. if every coin must be on the balance).