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