What is the minimum weighting trials to be made with a two pan scale to find the lighter marble?

Question

The puzzle is as follows:

Over a table there are three bags with marbles, on the first one there are 100 blue marbles, on the second one there are 100 red marbles and on the third one there are 100 green marbles. All the marbles inside the bags are in equal weight, except two of them whose weight is slightly less from the others and identical, which are on different bags. Considering all of this, How many weighing trials at minimum must be made by using a two pan scale to find with certainty those two mysterious lighter marbles?

The choices given are as follows:

$\begin{array}{ll} 1.&\textrm{11 trials}\\ 2.&\textrm{8 trials}\\ 3.&\textrm{9 trials}\\ 4.&\textrm{10 trials}\\ \end{array}$

I'm not sure exactly how to solve this problem, my best effort goes as this:

Assuming that those bags fit in the two pan scale (hence marbles are sufficiently small) then you put in the left pan one bag and in the other the other bag.

The best thing that it can happen is that right off the bat one bag is heavier than the other because it contains the heavier marbles. The worst thing is that they are equal in weight because they both contain those mysterious lighter marbles. But either one way or another. Assuming we know beforehand there are two marbles whose weight is less than the others and those two are in two separate bags then this means that if those two bags weight the same, then those two bags contains the marbles we're looking for. While the other bag has the heavier marbles.

All of this account for one weighing trial.

Now that we discriminated those bags, we know our two bags which contains the lighter marbles we split them in groups of 50. This accounts for four groups.

Assuming that we do not mix those, we put those two groups in one pan and the other two in the other pan.

The worst that can happen is that they are even, and we still cannot tell on which side there are the ligther msrbles.

Thus a new weighing trial is needed.

This accounts for a second trial.

In the next trial, we switch the groups by fixing two groups. After doing this, the scale will reveal which side is the lighter one. Thus the heavier marbles can now be returned back to the group of the marbles which do weight more.

This accounts for our third trial.

We repeat the cycle again. But now we have 100 marbles remaining, as the other 100 went back with their set of heavier marbles. Thus, we split those in 4 groups of 25.

Assuming that it happens the same as before, we can't tell the different first, so a new weighing trial is needed.

This accounts for our fourth trial.

We repeat the weighing trial, switching the groups, and we know for sure 50 marbles are heavier and the other 50 must contain the lighter marbles.

This accounts for the fifth trial.

We now have 50 marbles whose weight must contain those two marbles. We again repeat the cycle. In this case we cannot divide 25 by 4. Remember that all the time we are keeping track on which side belongs to which bag, so we have took care not to mix the groups. So we use one of these groups of 25 (and save the other for later) from which we know it contains a ligther marble. But because 25 cannot be split in two. We take out from that group a marble, and we have two groups of 12.

We perform a new weighing trial. The best thing it can happen is both sides are even and we got our lighter marble. The worst thing is that we need a new weighing trial.

This accounts for a sixth trial.

We collect the heavier marbles as this was revealed by the scale plus the marble what we took out first and we end up with 12 ones from which we don't know where is the mysterios marble and perform a new weighing trial. This time splitting in six and six.

Again we assume that the worst thing that can happen is that we are still unable to know where is the mysterious marble.

From those we know that six are heavier as the scale revealed this to us by tilting it to one side.

This account for a seventh trial.

We now have six from which we don't know where is the ligther marble. We split them in groups of 3 and 3 and perform a new weighing trial, from it we do know the heavier ones.

This accounts for the eight trial.

Now it comes finally our last 3 marbles. From these we must take out one. In any case it will be revealed which is ligther. If the scale is even, then the one which we took out is the lighter. If one side is heavier the other resting in the other pan is the ligther one, which belongs to one bag.

Remember that we saved one group from before performing the sixth trial. Thus as we required 3 steps to discover which marble was the ligther one, this adds to the already weighing trials that we accounted.

This means $8+3=11$

Thus I conclude that at minimum we do need $11$ weighing trials for that, or choice 1. But of course, I could be overlooking something.

Can someone please check my logic?. I am not sure if it can done in less steps or in a different way, but to my understanding this is the most logical way to do it.

Thus can someone help me here?.

Answer 1

It certainly can't be done in fewer than $10$ weighings. There are $3\cdot10^2\cdot10^2$ possible answers. Each weighing gives $3$ possible answers: the pans balance, the left-hand pan is heavier, or the right-hand pan is heavier. $9$ weighings have only $3^9<3\cdot10^4$ possible outcomes, so they can't reliably distinguish between all possible answers.

I believe that it can't be done in $10$ weighings, either, but I can't say my argument is truly a rigorous proof.

To begin with, it seems like weighing one bag against another must be the way to start. This eliminates $100$ marbles in one shot, and we can't expect to do any better. Let's say that the blue marbles are all standard, and there's one light red and one light green. Then it seems to me that we can just weigh the red and green marbles separately. If after the first weighing, and oracle tells you which is the light green marble, that doesn't help you find the light red marble. Now $3^4<100$, so we'd need $5$ weighings at least to find the light red marble. In the absence of an oracle, we also need $5$ weighings to find the light green marble, so $1+5+5=11$ weighing in all.

There are a couple of points where the reasoning seems a bit iffy to me, but I'm going to post it anyway. Maybe someone can clean it up.

EDIT

As antkam's answer shows, the above reasoning is false, and $10$ weighings are possible. I'm not going to delete or edit the post, however, because antkam's answer refers to it.

Answer 2

Here is a way to do it in $10$ total weighings, which as saulspatz pointed out, is optimal.

First weighing: all of one color vs all of another color. From this you know the colors of the two lightweight or "bad" marbles. (BTW this weighing reduces the no. of possibilities from $3 \times 10^4$ to $10^4$ which is the best you can do.)

For the rest, lets assume the two colors with bad marbles are Red and Green.

At this point, what saulspatz's "oracle" argument shows is that if you never mix the two colors in a subsequent weighing, you cannot do better than $5$ more per color, or $11$ total. So the key is indeed to having further weighing(s) with both colors.

Let $R$ be a fixed subset of $81$ red marbles, and $R'$ be the remaining $19$ red marbles. Similarly let $G$ be a fixed subset of $81$ green marbles, and $G'$ be the remaining $19$ green marbles.

Second weighing: $R$ vs $G'$ plus $81-19 = 62$ blue ("good") marbles, so that there are $81$ on each side. We have $3$ possibilities:

• The most common case is $R < G' + B$. In this case we know:

  • The bad red marble is in $R$, which we can find out using $4$ more weighings because $3^4 = 81$.

  • The bad green marble is in $G$, which we can also find out using $4$ more weighings.

  • So the total no. of weighings $= 1+1+4+4 = 10$.

• The least common, and also easiest case is $R > G' + B$. In this case we know:

  • The bad red marble is in $R'$, and we can find it using $3$ more weighings coz $3^3 > 19$.

  • The bad green marble is in $G'$, another $3$ weighings.

  • So the total no. of weighings $= 8$.

• The last case, conceptually the most complicated, is $R = G' + B$. In this case, the sets containing the bad marbles can be (i) $R$ and $G'$, or, (ii) $R'$ and $G$.

Luckily, we have enough leeway to "waste" the third weighing to find out which of (i) or (ii) is true.

Third weighing (for $R = G' + B$ case): Simply weight $R$ vs $81$ blue marbles to see if $R$ contains a bad marble. Since the blues are all good, there can be only two outcomes:

• If $R$ weighs less, then we have case (i) where we know the bad marbles are in $R$ and $G'$. The one in $R$ can be found by $4$ more weighings, and the one in $G'$ can be found by $3$ more, for a total of $1 + 1 + 1 + 4 + 3 = 10$ weighings.

• If $R$ weighs equal with the blues, then we have case (ii) which is symmetric.

BTW, visualizing the $100 \times 100$ possibilities (after the first weighing) as a $100\times 100$ grid helped me solve this problem.