6
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ If you have more than 999 grams on the scale, does it say "999" or "error"? $\endgroup$
    – Arthur
    Commented Apr 17, 2020 at 17:39
  • $\begingroup$ @Arthur it says "Error" $\endgroup$ Commented Apr 17, 2020 at 17:41
  • 1
    $\begingroup$ Do you know why the number $135$ was chosen? From the answers, it seems that it's not a special number; the optimal number of weighings would still be $3$ with a few boxes more or less. $\endgroup$
    – joriki
    Commented Apr 17, 2020 at 18:57

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Dear Arthur and SmileyCraft you are geniuses! I upvoted both solutions and accepted Arthur's as the answer to my question, only because he uploaded it first. Thank you both very much! $\endgroup$ Commented Apr 18, 2020 at 11:59
6
$\begingroup$

If you place at most $100$ marbles on the scale, then you will be able to see exactly how many of them weigh $9$ grams. I will assume this is the only viable option. Indeed you can place more than $100$ marbles on the scale and get information out of this, but I am very confident that this is never part of an optimal strategy.

Then we can generalize the problem. Assume we have $n$ boxes with $m$ marbles. All marbles from all boxes are identical, except one box has special marbles. We have a machine that we can give an arbitrary collection of $m$ marbles, and it will tell us how many are special. The following describes the optimal strategy for this game.

For $x$ a positive integer, let $[x]$ denote the set $\{0,...,x\}$.

Any move can be described by a function $f:[m]\to[n]$ such that $f(k)$ describes the number of boxes from which we take $k$ marbles. Then we need $\sum_kf(k)=n$ and $\sum_kkf(k)\leq m$. If the machine tells us there are $k$ special marbles, then there are $f(k)$ possible boxes left to check. This means that the worst case is that there are $\max_kf(k)$ possible boxes left to check.

Thus, the goal in each step is to minimize $\max_kf(k)$ over all functions $f:[m]\to[n]$ with $\sum_kf(k)=n$ and $\sum_kkf(k)\leq m$. We can do this by means of binary search, by checking for specific values of $M$ whether or not it is possible to have $\max_kf(k)\leq M$.

To check whether $\max_kf(k)\leq M$ is possible, let $n=aM+b$ with $0\leq b<M$. Then assign $f(k)=M$ for $k<a$, $f(a)=b$ and $f(k)=0$ for $k>a$. This gives $\max_kf(k)\leq M$ and $\sum_kf(k)=n$ while minimizing $\sum_kkf(k)$. Thus, we can simply check whether we get $\sum_kkf(k)\leq m$.

Now we can apply this to the case $n=135$, $m=100$. For $M=57$ we find $f=[57,57,21]$ suffices, and for $M=56$ we find $f=[56,56,23]$ does not suffice. Therefore, the optimal strategy is to place $1$ marble from $57$ boxes and $2$ marbles from $21$ other boxes. As a result, the worst case scenario is that there are $57$ boxes left to check.

Then for $M=13$ we find $f=[13,13,13,13,5]$ suffices, and for $M=12$ we find $f=[12,12,12,12,9]$ does not suffice. Therefore, the optimal strategy is to place $1$ marble from $12$ boxes, $2$ marbles from $12$ other boxes, $3$ marbles from $12$ other boxes, and $4$ marbles from $5$ other boxes. As a result, the worst case scenario is that there are $12$ boxes left to check.

Then for $M=1$ we find $f=[1,1,1,1,1,1,1,1,1,1,1,1]$ suffices, and thus we can place $0$ marbles from the first box, $1$ marble from the secend, etc. up to $11$ marbles from the twelveth box. As a result, we will know exactly which box contains the special marbles.

This proves the optimal worst case number of weighings is three. This way, we can also find that the largest number of boxes with which it is possible in three weighings is $140$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .