Determine hollow marble with least number of weighings

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.


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$.

Tags:

Puzzle

Combinatorics

Related

Solve $\lfloor{\sin x}\rfloor+\lfloor{\cos x}\rfloor=2^{1-|\sin x|}$ What is the meaning of "in particular" in this proof? Generators for the ideal of entire functions vanishing on $\mathbb Z\times\mathbb Z\subset \mathbb C\times\mathbb C$ Proving a complicated looking inequality in a simple way Prove that $N \subseteq H$ Prove that all ideals in $\mathbb{Z}[x]$ are generated by two elements. On Ramanujan's approximation, $n!\sim \sqrt{\pi}\big(\frac ne\big)^n\sqrt [6]{(2n)^3+(2n)^2+n+\frac 1{30}}$ Let $H$ be a subgroup of $G$, and suppose that $G$ acts by multiplication over the set $X:=G/H$ of the left-hand side classes of $H$ over $G$. Prove that if $m^p+n^p\equiv0\pmod p$ then $m^p+n^p\equiv0\pmod {p^2}$ where $p$ is an odd prime number. Is $g(\eta)$, as defined in the question, a Dirac delta function? Is the union of an arbitrary collection of topological spaces a topological space? Is it valid to use operations on both sides before inequality is proven?

Recent Posts