0
$\begingroup$

We have 6 balls of 1,2,3,4,5 and 6 grams. How to find each one's weight using a 2 sides balance (a side can take many balls).

$\endgroup$
  • $\begingroup$ Is there any criterion? Do we only get a limited number of weighings or something? Because a bubble sort is simple, and fast enough with this few balls (only $15$ weighings, and I think the theoretical minimum is $9$, so it's not bad). $\endgroup$ – Arthur Dec 9 '16 at 15:25
  • 1
    $\begingroup$ @Arthur Thanks for your answer. Yes the goal is to find the minimum number of weighings. The theoretical minimum is 10 for sorting algorithms of 6 elements. This is a rather specific case and I wonder if we can't do it in less. $\endgroup$ – loop Dec 10 '16 at 12:33
  • $\begingroup$ I misspoke. The theoretical minimum is $6$, actually. The idea is this: There are $720$ different possibilities. For each weighing, there are three outcomes: either one side is heavier, or the other side is heavier, or they are in balance. That means that if we're clever about how we lay up the balls, we may be able to narrow it down to $240$ different possibilities with one weighing. Once more, and we can narrow it down to $80$ different possibilities. And so on. Whether there actually is such an optimal strategy, I don't know. $\endgroup$ – Arthur Dec 10 '16 at 12:46
  • $\begingroup$ Can you develop more on how you get these numbers and what method to follow to implement the strategy? $\endgroup$ – loop Dec 10 '16 at 23:21
  • $\begingroup$ And why 6 is the minimum when decreasing the different possibilities by weighing? $\endgroup$ – loop Dec 10 '16 at 23:38

Your Answer

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

Browse other questions tagged or ask your own question.