Dividing real coins into three sets

Question

There are $n$ coins, $3k$ of which are real (with equal positive weight) for some $k\geq 1$ and the rest fake (with zero weight), but you don't know $k$. You have a scale that, between two sets of coins, tells you which set is heavier (or if they are equal). What is the worst-case minimum number of weighings that you must use in order to divide the coins into three sets so that each set contains $k$ real coins?

Using binary search you can divide the coins into two sets with $3k/2$ real coins each using $\log n$ weighings. From here you can divide the coins into four sets with $3k/4$ real coins each using $2\log n$ more weighings, and so on. However, this doesn't allow you to get a set with $k$ real coins.

Answer 1

Partition the coins into three roughly equal subsets $A,B,C$. Use two weighings to determine the lightest of these, wlog. this is $A$. Use binary search (i.e., $\sim \log\frac n3$ weighings) to find $B'\subseteq B$ of equal weight as $A$. Similarly, find $C'\subseteq C$ of equal weight as $A$. Set $A,B',C'$ aside as three subsets having the same number $l\le k$ of real coins. Now we have reduced the problem to $n'\le n-\lfloor \frac n3\rfloor=\lceil\frac23n\rceil$ and $k'=k-l$ (which may but be $=0$). Repeat this.

Note that $n'<n$ if $n>3$. And as soon as $n\le 3$, we can stop: Either $k=1$ and $n=3$ and each coin is real and we have a straightforward solution; or $k=0$ and any partition will do.

The master theorem applied to $T(n)= T(\frac23n)+\log n $ gives us that the number of weighings this specific (possible non-optimal) method uses is $$O(\log^2n).$$

---

Remark: The expected performance of the above method may be much better: As long as $n$ and $k$ are large, a random subset of size $\frac n3$ should contain about $k\pm\sqrt k$ real coins, so we may expect $k-\sqrt k$ real coins in the lightest set, which leads roughly to $k'\approx \sqrt k$ and $n'\approx\frac n{\sqrt k}$.

Answer 2

Using binary search we can find the middle most coin(s) in $O(\log n)$ weighings. Now we know if $k$ is even or odd (by seeing if the scale balances). If $k$ is even, apply the problem recursively to both sides and combine, otherwise we continue.

Since $k$ is odd and we know the middle most coin, we know that there are the same amount of real coins to the left, and to the right. Use the middle most coin to binary search both sides for another real coin, and take them from both sides. This takes another $O(\log n)$ weighings.

Now we have three coins, and two sides with an equal amount of coins. If we write $k = 2l + 1$ since $k$ is odd, we knew there were $3k = 6l + 3$ real coins. We just took out 3 coins, and both sides have the same amount of coins, both sides have $\frac{6l + 3 - 3}{2} = 3l$ coins left. That means we can recursively apply our procedure on both sides, and then combine.

Unless I'm mistaken this algorithm takes $O(\log ^2 n)$ time, however I make no claims about it's optimality - even asymptotically.