# General Fake Coin: k fake coins out of n coins

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

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

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.