Splitting real coins into half

There are $n$ coins, some are real and others fake. Real coins all have equal positive weight, and fake coins have zero weight. The number of real coins is $2k$ for some $k\geq 1$, but you don't know $k$. Your task is to split the coins into two halves so that each half contains $k$ real coins.

You are given a scale that, between two sets of coins, tells you which set is heavier (or if they are equal). What is the optimal number of weighings, in terms of $n$, after which you can do the task?

Note that we need at most $n$ weighings: We can start with an empty scale and add one coin at a time to the side that is lighter (if the two sides are equal, then it doesn't matter.)

If $k=1$, then we only need $\Theta(\log n)$ weighings. We can divide the coins in half and weigh the two halves. If the two halves are equal, we are done. Else, we recurse on the heavier half, which must contain both real coins. But in the question we don't know $k$.

• Your wording makes it sounds like we're chopping coins into two – Shuri2060 Jul 24 '17 at 19:55
• "and fake coins have zero weight"!!!! Don't do any weighings. Just put them on a table and blow on them. – fleablood Jul 24 '17 at 20:46
• @fleablood To put them on a table you'll have to catch them first! – Théophile Mar 8 at 18:14

You can do it in $\Theta(\log n)$ weighings. Place half of the coins on the left, half on the right, and weigh. If both sides are equal, we are done.

Otherwise we'll split both sides up into two halves, swap their left halves, and weigh again:

aaaabbbb     ccccdddd


• In summary, line up the coins and binary search for a point between the $k$th and $k+1$st real coin. It's also clear that this approach is optimal because the midpoint could fall into any of $n+1-2k$ possible positions, requiring $\lceil \log_2 (n+1-2k) \rceil$ weighs in the worst case. – Solomonoff's Secret Jul 24 '17 at 20:12