Determine hollow marble with least number of weighings

combinatoricspuzzle

We have 135 boxes each containing 100 marbles which look identical and weigh 10 grams, with the exception of one box, which contains hollow marbles of 9 grams each.
By using a scale that can weight up to 999 grams, what is the least number of weightings required to determine the box with the hollow marbles?

Well, I know the method of numbering the boxes and then taking 1 marble from box 1, 2 from box 2 etc and then compare the result with
$\sum_{k=1}^{135} k*10$,
but this is 91800, so we would roughly need 100 weighings!
Maybe we can split the 135 boxes into two groups, 68+67, then from the first group weigh one of each, to see if the scale displays 680 or 679, then continue with either group which contains the hollow marble and do the same?

2nd weighing: 34 or 33

3rd: 17 or 17

And then we can apply the 1+2+3… method to determine in which of the two groups 9 or 8 are the hollow marbles.

But this way we will need 5 weighings, which I doubt is the optimum method.

Any help please?

Best Answer

You can do better than 68 + 67 on the first weighing! Try 57 + 56 + 22. Take one marble from each of the 56, and two marbles from each of the 22. Then, the scales show either "Error", or "999" or "998". If it shows "error", all 100 marbles on the scales are real, and the hollow marbles are among the 57. If it shows "999", the hollow marbles are among the 56, and if it shows "998", the hollow marbles are among the 22. I will assume worst case in the rest of the explanation, so let's say there are 57 boxes left to examine.

(If the scales say "999" rather than "error" if there are more than 999 grams worth of marbles on it, you will have to do 57 + 57 + 21 instead. This doesn't affect the rest of the algorithm.)

The 57 can be divided further into five groups of 14 + 14 + 14 + 14 + 1. Take one marble from each box in one of the 14-groups, two from each the second 14-group, three from each in the third 14-group, and four from the lone box (leaving the fourth 14-group untouched in this round). See whether the scales really show 844, and if not, how many grams are missing.

Worst case, you have 14 boxes left after the second weighing. You can now take one marble from box 1, two from box 2, and so on, leaving one box unused. If all marbles on the scales are whole, the scales will show 910, and the unused box will have hollow marbles. If not, count how many grams are missing, and that will identify the box with the hollow marbles.

This totals three weighings. I do not know that this is the best you can do, but I'll be very impressed if anyone comes up with a way to do it in 2.

Related Question