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