Can you find the fake coin?

Probability Level 2

He tells you that exactly one of the 8 coins is counterfeit and that the counterfeit coin is heavier .

He then gives you a beam balance and an User Manual. You have never seen a beam balance before, so you open the user manual and find that it says:

You can place a coin or a group of coins on the two pans of the balance. You can find which side is heavier, if any or if their weights are equal.

What is the minimum number of times you need to use the balance to surely find the counterfeit coin?

\left \lceil \log _3 8 \right \rceil

2^8

{8 \choose 3}

{8 \choose 2}

1 solution

Nanayaranaraknas Vahdam
Sep 23, 2014

I believe the option should be $\lceil \log_38\rceil$ , and not $\log_3\lceil8\rceil$ , as the latter is meaningless.

Basically, given $n$ weights with $1$ counterfeit weight, either heavier or lighter, it takes $\lceil \log_3n\rceil$ weighings to determine the counterfeit coin. The process is to split the coins into almost equal groups of $3$ , and weigh two groups at a time. This way, in one weighing, the number of coins required to be examined is reduced by $\frac{2}{3}$ . Repeating this procedure will lead you to single out one coin in the least number of steps.

Also, to generalize, if the scale could compare $k$ groups of coins at once, then the coins must be split into $k+1$ groups, and the number of weighings will be $\lceil \log_{k+1}n\rceil$

I have updated the correct answer to $\lceil \log_3 8 \rceil$ .

No one was marked wrong.

Calvin Lin Staff - 6 years, 8 months ago

You're very correct about Ceiling (Log_3(8)). Sorry for putting it the wrong way

Agnishom Chattopadhyay - 6 years, 8 months ago

nice question

math man - 6 years, 8 months ago

Can you find the fake coin?

1 solution

0 pending reports