Fix $k>3.$ There are $n$ coins with positive real weights. You have a scale that, between two sets of coins, tells you which set is heavier, or if they are equal. Is it possible to perform at most $c_k\log n$ weighings (with $c_k$ depending only on $k$) after which you can divide the coins into $k$ sets with the property that between any two sets $A,B$, there exists a coin in $B$ that if you remove it, then $A$ weighs at least as much as $B$?

It seems to be true for the $k=2$ and $k=3$ cases, see Coin weighing to find similar-weight sets. I don't see how to generalize the algorithms there to $k>3.$

There exists a particularly simple division where you put the coins in a line and place cuts along the line, see Cutting numbers into parts. But I don't see how to extract an algorithm better than $c_k(\log n)^2$ from the proof.



You must log in to answer this question.

Browse other questions tagged .