4
$\begingroup$

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

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

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

ccccbbbb     aaaadddd

If the scale balances, we're done. If the scale flips sides we recurse on the left halves, and leave the right halves on the scale for the rest of the process. If the balance is unchanged, we recurse on the right halves and leave the rest on the scale for the rest of the process.

The reason this works is if swapping two equally sized portions on the scale can flip the scale, then by swapping a subset of those equally sized portions can balance the scale, because there are an even amount of real coins.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Solomonoff's Secret Jul 24 '17 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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