0
$\begingroup$

The classic problem goes like this:


You are given a set of scales and 12 marbles. The scales are of the old balance variety. That is, a small dish hangs from each end of a rod that is balanced in the middle. The device enables you to conclude either that the contents of the dishes weigh the same or that the dish that falls lower has heavier contents than the other.

The 12 marbles appear to be identical. In fact, 11 of them are identical, and one is heavier than the others. You are allowed to use the scales three times if you wish, but no more. Identify the heavier marble.


The common solution I have seen online and in books is the solution which divides the 12 marbles into groups of four and weighs these groups together in a clever way so that at the end of the 3 weighs, you uniquely identify the heavier marble. I have a different approach that I want to check its validity.

My Approach:

Of the 12 marbles, divide them into two groups of 5 and leave 2 on the side. Weigh the two groups of 5 against each other. If they are of the same weight, compare the 2 marbles on the side against each other to get the heavier marble. If one of the groups of 5 is heavier than another, then throw out the other 7 and only consider this group of 5. Divide this group of 5 into two groups of 2 and leave 1 marble on the side. Weigh the two groups of 2 against each other. If they balance, the 1 on the side is the heavier marble. If one of the groups of 2 is heavier, then weigh the 2 marbles in the heavier group against each other to get the heavier marble.

Is this a good approach for this problem?

$\endgroup$
  • $\begingroup$ That seems to work. $\endgroup$ – rogerl Aug 24 '15 at 20:36
  • $\begingroup$ I think you can find the marble that's different in 3 weighings, even if you don't know whether it's heavier or lighter than the other marbles. $\endgroup$ – user84413 Aug 24 '15 at 20:44
  • $\begingroup$ The 'clever' solution you have seen is a solution to the problem where you know that one marble has a different weight, but don't know whether it's lighter or heavier. If you know that the marble is heavier (or that it is lighter), then the problem becomes much easier and requires no clever trickery, as you have discovered for yourself. $\endgroup$ – John Gowers Aug 24 '15 at 21:12
  • $\begingroup$ Does anyone know how to solve this problem using a base-three numbering system? That is, we can number the marbles and compare them in a systematic way by numbering them in base-three? $\endgroup$ – RPz Aug 24 '15 at 23:41
1
$\begingroup$

Your solution can work as well as many others, like e.g.

6v6/0 -> 2v2/2-> 1v1/0

where XvY/Z means weight X against Y, keep the heavier of them if any, Z otherwise.

Your solution has the merit to possibly require less weights in 2 cases out of 12, of course, although it can be improved a bit like this (I hope the notation for the arrow is self-explanatory):

3v3/6 -XY-> 1v1/1
      -Z--> 2v2/2 -> 1v1/0

which requires only two weights in half of the cases.

Note that you can use up to 2 weights if you have no more than 9 marbles, because you can solve 9 marbles as follows:

3v3/3 -> 1v1/1

So, another perfectly valid solution to the 12 marbles puzzle might even be:

2v2/8 -XY-> 1v1/0
      -Z--> 3v3/2 -XY-> 1v1/1
                  -Z--> 1v1/0

which requires only two weights in one third of the cases.

In general, if you have N weights at your disposal, you can solve the puzzle up to $3^N$ marbles included. With three weights, you can then have up to 27 marbles:

9v9/9 -> 3v3/3 -> 1v1/1

and it's basically the extension of a binary search with three alternatives instead: you can generally divide your lot into three partitions, and have a way forward by comparing only two of them.

$\endgroup$
0
$\begingroup$

You can solve three marbles in one weighing, knowing that one is heavier than the others. Weigh $1v1$.

If you have nine marbles, one heavier, you divide them into three threes. The first weighing identifies the rogue group, the second the rogue marble.

You can do twenty seven marbles with three weighings.

The logic of this is that the balance is either level or one of the two pans goes down. There are $27$ outcomes from three weighings.

If you know there is a dud marble, but don't know whether it is heavier or lighter, you can find the dud from thirteen marbles in three weighings - but you will only know heavier/lighter twelve times out of thirteen.

$\endgroup$

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.