0
$\begingroup$

Considering a general fake coin problem. There are $n$ coins in total and $k$ of them are fake. Fake coins are lighter than the normal ones. You only have a balance to compare two groups of coins (no amount limit). How many times you will compare at least?

Note: All the fake coins have the same weight $w_f$; all the good coins have the same weight $w_g$; $w_f < w_g$; The target is to find all the fake coins using minimum time complexity (expected $O(\log n)$).

Improve this question
$\endgroup$
2
  • $\begingroup$ Is the value of $k$ known beforehand ? $\endgroup$
    – Evargalo
    Oct 5, 2022 at 8:43
  • 1
    $\begingroup$ @Evargalo Yes, the $k$ is a known constant here. We can suppose $k <= \frac{n}{2}$ $\endgroup$
    – picker
    Oct 5, 2022 at 15:39

1 Answer 1

Reset to default
1
$\begingroup$

For $n$ coins of which $k$ are fake, there are $\binom{n}{k}$ potential assignments. Each weighing has three possible results (left heavier, right heavier, equal). So at least $\left\lceil \log_3\binom{n}{k }\right\rceil$ weighings are required to distinguish between the possibilities.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I think the number of weighing rounds is correct theoretically, but can you please provide some details of how to weigh them in each round pratically? $\endgroup$
    – picker
    Oct 4, 2022 at 14:56
  • $\begingroup$ This is a theoretical minimum, I don't think it can always be achieved. $\endgroup$
    – Florian F
    Oct 5, 2022 at 13:27
  • $\begingroup$ @FlorianF hm, interesting, I first read this answer as "the minimum number of weighings is at least this much". But I can see how it can also mean "the minimum is this much". $\endgroup$
    – justhalf
    Oct 6, 2022 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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