[Math] A Solution to the Classic “12 Marbles, find the one of different weight” Brainteaser

puzzle

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?

Best Answer

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.

Related Question