You are given $N$ coins which look identical (assume $N = 2^k$). But actually some of them are pure gold coins (hence are heavy) and the rest are aluminum coins with thin gold plating (light). You are given one beam balance with two pans. What is the number of weighing required to separate the gold from fake coins? (all gold coins have equal weights & all fake coins too have the same weight)
Source: brainstellar.com
My approach: I think we have to use divide and conquer here, if we can divide the coins into $2$ groups with $N/2$ coins each and have $d/2$ heavy coins each (considering $d$ is total heavy coins) then we have a recursive case and we can solve that recursively. But I don't know how to get $d/2$ heavy coins here. Kindly help.
In what follows, I am interpreting the phrase "some of them are pure gold" to mean there is always at least once gold coin present.
Instead of divide-and-conquer, we can use decrease-and-conquer. This will allow us to solve the problem even when $N$ is not a power of two. I will show how to solve the problem in at most $N-1$ uses of the scale, and prove that you cannot do better in the worst case.
First, we need the base cases. It is easy to solve the $N=2$ case with one weighing. You can also solve the $N=3$ case with two weighings; by weighing any two pairs, you can deduce all of the gold coins (check this yourself). We have shown how to solve the $N$-coin problem in $N-1$ weighings, for $N\in \{2,3\}$.
For general $N\ge 4$, start by weighing two coins against each other. If they are unbalanced, we now know their weights. If they balance, we will determine their weights later. Next, find the weights of the remaining $N-2$ coins with $N-3$ weighings (this is the decrease-and-conquer step). Finally, in the case where the first two coins were balanced, weigh one of them against one of the known $N-2$ coins in order to determine whether the first pair was gold or aluminum. We have solved $N$ coins in $N-1$ weighings.
Finally, I prove that you cannot do better than $N-1$. After some number of uses of the scale, we can partition the coins into several groups, where it is known that any two coins in the same group have the same weight. Initially, each coin is in its own separate group. Whenever you weigh two coins from different groups, there are two possibilities.
If the scale does not balance, then you learn that the group containing the heavier coin is gold, and the other group is aluminum.
If the scale balances, then you learn the two groups have the same material. This means you can merge the two groups into one.
The second scenario is the worst case. If the scale balances each time, then the only information we learn is that certain groups merge together. We start with $N$ groups, and only when all the coins are in the same group can we finally deduce that all coins are the same weight, and therefore must be all gold. It takes at least $N-1$ merges to reduce $N$ groups down to $1$ group, hence at least $N-1$ uses of the scale.