3

There are $n\geq 4$ coins. You are allowed to ask for the weight of any set of coins. What is the worst-case (asymptotic) minimum number of questions after which you can divide the coins into four sets with the property that between any two sets $A,B$, there exists a coin in $B$ that if you remove it, then $A$ weights at least as much as $B$?

Such a division exists by this simple algorithm: for each coin, place it in the pile with the minimum weight so far. By using $n$ questions, we can ask for the weight of each coin individually and get full information. If all coins has weight either $0$ or $1$, then we can do binary search three times to divide the coins into four sets using $O(\log n)$ questions.

pi66
  • 1,199
  • 1
    Is this research-level mathematics? – David G. Stork Aug 24 '17 at 23:07
  • 2
    There are other coin puzzles posted on this site, e.g., here and here. If those are appropriate questions for the site, I don't see how this one isn't. – pi66 Aug 24 '17 at 23:38
  • I'm pretty sure that $O(\log n)$ questions will still suffice. I would first, weigh all the coins, then, using binary search, divide the coins into four groups, $A_1,A_2,A_3,A_4$ and $O(1)$ additional coins such that by adding them to the groups we can make any $A_i$ the lightest. Doing this requires some case analysis. ps. Why the magic number four? – domotorp Dec 25 '17 at 21:26

0 Answers0