11
$\begingroup$

You have 50 marbles which look all the same. However, 25 marbles have weight l and the other 25 marbles weight h with l < h. A person creates two piles and claims he has sorted all 50 marbles by weight and pile L has all marbles with weight l and pile H has all marbles with weight h. You are given a traditional balance scale with two pans (no reading). You know which pile is pile L.

What is the minimal number of weightings required to find out if the sorting is correct?

$\endgroup$
14
$\begingroup$

5. Weigh an L vs. H. If OK, place both on one side of the scale, and add two from H to the other pan. If OK, you can now test 4H, then 8H and then the remaining 10H.

$\endgroup$
  • $\begingroup$ You should better explain what "if OK" means, i.e. that the pan with a marble from L must always show to weigh less. $\endgroup$ – Florian F Dec 14 '19 at 20:45
3
$\begingroup$

Here's a quick upper bound:

25

You can achieve this by

taking one marble from each pile at a time, and weighing them against each other. If at any time the weights are equal, or the marble from pile L is heavier than the marble from pile H, then you know the sorting is wrong. Otherwise, the sorting is correct.

$\endgroup$
  • 1
    $\begingroup$ rot13(Crefbanyyl, V fhfcrpg gung gur jubyr guvat pna or qbar va svir jrvtuvatf, gubhtu.) $\endgroup$ – Avi Dec 13 '19 at 21:37
1
$\begingroup$

I count

6 weighings.

  1. compare 1 from light pile and 1 from heavy pile to ensure light pile is actually the light pile of marbles.
  2. take light marble from step 1 and compare with second from light pile.
  3. take both light marbles from step 2 and compare with two others from light pile.
  4. take the 4 from step 3 and compare with 4 others from light pile.
  5. take the 8 from step 4 and compare with 8 more.
  6. there are 9 light marbles left in the light pile, so compare them with 9 marbles from step 5.

done

$\endgroup$
  • $\begingroup$ This works, but uses an extra weighing compared to JMP's answer: you can replace (exactly) one of the light ones with the known heavy, and as long as that single heavy makes the pan go down, you know all the marbles in the other pan were light. $\endgroup$ – Bass Dec 14 '19 at 11:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.