2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Nice. Can you then prove that 2 is minimum? $\endgroup$ – sourav goyal Feb 4 at 16:06
  • $\begingroup$ As it was too long for a comment, I edited the answer. $\endgroup$ – Klaus Feb 4 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.