Find the odd one out: 12 marbles and a pan balance

Computer Science Level 2

You have 12 indistinguishable marbles with the same weight, except one that weighs different from the remaining 11. You have a pan balance with two pans - one on each side. If you place equal weighted items on both sides, the pan balance remains balanced. If you place a heavier weight on one side, the balance tips in that direction. This pan balance can however be only used 3 times.

Now, the question is:
Can you identify the odd-weighted marble from the 12 marbles?
If so, how. If not, why not?
(note that the odd marble could be heavier or lighter than the rest)

Yes No

Vikram Mullachery by Vikram Mullachery , 47, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Yes, this can be done and not only that we should be able to identify whether the marble is heavier or lighter. Let's tabulate how to identify an odd marble when there are various numbers of marbles with the number of pan weighing attempts. We shall also account for prior knowledge (or assumption) about the odd marble - whether it is heavier or lighter in our tabulation. Assume the marbles are labeled A, B, C etc.:

Total Number of Marbles Prior Knowledge Number of attempts to Solve Explanation
2 Heavier 1 Well, weigh A against B, pick the heavier one -- just one weigh
2 Lighter 1 As above, but pick the lighter one
2 None N/A Well, in this case we don't know which marble is the odd one
3 Heavier 1 Weigh A against B. If unequal, we know C is the odd one out. Otherwise, the one that tips the scale heavier is the odd one out
3 Lighter 1 Weigh A against B. If unequal, we know C is the odd one out. Otherwise, the one that tips the scale lighter is the odd one out
3 None 2 Assume the marbles are labeled A, B, C. Weigh A against B. Tells us whether A or B is the odd one. So now, weigh A against C. This identifies the odd one and whether it is heavier or lighter
4 Heavier 2 Weigh A against B, and then A against C
4 Lighter 2 Same as above, but pick the lighter one
4 None 3 Weigh A against B. If the balance tips, replace B with C, and we know the odd one and whether it was lighter or heavier. However, if the pan balance does not tip for A against B, and again for A against C, then we need to try a third time with A against D
5 Heavier 2 Separate into 3 groups: 2 (A,B), 2 (C,D), 1(E). Weigh (A, B) vs. (C, D). If equal then E is the odd one. If the pan balance tips, towards (A,B), just weigh A vs. B
5 Lighter 2 Same as above
5 None 3 Separate into 3 groups: 2(A,B), 2(C,D), 1(E). Weigh (A, B) vs. (C, D). If the pan balance does not tip then it is easy. If the pan balance tips then, weigh (A,E) vs. (B, C). This second weigh could yield 3 different outcomes: balance does not tip, balance tips left or balance tips right. If the balance does not tip is easy since then D is the odd one (and so a third weigh to identify whether it is heavier or lighter). If the balance tips left, then we know that the odd one is A and heavier OR C and lighter. This is because B cannot be the odd one since it was on the heavier left side on the first weigh. So, in this case, for the final weigh B or E or D vs. C. If the balance tips right on the second weigh, B is the odd one and heavier

Now to solve for 12 marbles, one could proceed as above by working out the logic for each of the cases 6, 7, 8 etc. Another way to get there is to simply recognize the solution above for 4 and 5, and then use the same pattern for 12 marbles:

  • Make 3 groups of 4 marbles each
  • Weigh group 1 vs group 2
  • If they are equal, then the odd one is in group 3 (A,B,C,D). Weigh (A,B) vs. (C,Z). Z is a marble from groups 1 or 2 (and so not the odd one). Now, the scale can tip left, right or stay balanced. Balanced is the easy case and we know that D is the odd one, in which case one more weigh to figure out whether it is heavier or lighter. If the balance tips left, then the odd one is A or B and heavier OR C and lighter. In this case, the third weigh is A vs B, and the solution is the heavier one else C. On the second weigh if the pan tips right, we know the odd one is A or B and lighter OR C and heavier. So, proceed as before by weighing A vs B and picking the lighter one else C
  • If on the first weigh group 1 vs group 2, the pan tips left, then we have a little bit more work to do. Say, (A,B,C,D) vs. (T,U,V,W) and the pan tips left. Now, for the second weigh, (A,B,T) vs. (C,U,Z) where Z is from group 3 (and so a non-odd marble). This second weight has three possible outcomes: tip left, tip right or stay balanced. Staying balanced is the easy one as then the odd one is one of D and heavier or V, W and lighter (because of the first weigh). And we know how to solve this in one weigh of V vs W. If on the second weigh, the pan tips left, then the odd one is one of A, B and heavier OR U and lighter (because of the first weigh). This again we know how to solve in one go by weighing A vs. B. On the second weigh if the pan had tipped right, we know the odd one is T and lighter or C and heavier, which is again solved by weighing C vs. Z on the third attempt.

Here are a few key choices:

Decision Choices Decision Choices

0 Helpful 0 Interesting 2 Brilliant 2 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...