balance scale problem for 13 (not 12) items

The 12-item balance scale puzzle is very familiar. The object is to find the lone non-standard item (if one exists) out of a group of 12 seemingly identical items, using a balance scale and a maximum of three weighings. Did you know that it is possible to accomplish the same outcome given a set of 13 seemingly identical items? I've scoured the web for a discussion of this problem/solution and have not found one. Am I the only one that has solved this problem?

BTW: If you allow four (4) weighings on a balance scale, how many seemingly identical items can you analyze and be assured of finding the lone non-standard item within the group?

If there is sufficient interest, I will publish the answers in a future post.

• Sounds awesome, I've never heard of this kind of problem before. – Simon Hayward Nov 27 '12 at 21:03
• I just finisher (re) working the 4 "weigh" problem. It was trickier than I remembered. Back to the 3 "weigh" problem... – tom Nov 28 '12 at 20:49
• I just finished (re) working the 4 "weigh" problem. It was trickier than I remembered. Back to the 3 "weigh" problem...keep in mind that a balance scale weighing yields three (3) unique outcomes. Consequently, three properly planned weighings will yield 3**3 (or 27) unique outcomes. With 13 items, any one could be heavy, any one could be light, or they could all be the same (27 outcomes). Still, there is a logistical trick needed to make it all work, and I'm not ready to reveal it just yet. – tom Nov 28 '12 at 21:01
• You are not the only one who has solved the 13 problem. In the 12 problem, you need not only to find the odd one out, but determine whether it is light or heavy. Unlike your question, you are given that there is exactly one non-standard item. These details are important. [This link] has a solution if you are given whether the odd one is heavy or light. One extra bit of information gives one extra bit on the outcome information. They are both good puzzles. – Ross Millikan Jun 18 '13 at 3:28

You can do it in three pre-determined weighings, by numbering the coins from 1 to 13 in the style 1, -2, 3, -4, 5, &c.

1    001       6  M10     11   11M
2    0M1       7  1M1     12   MM0
3    010       8  M01     13   111
4    0MM       9  100
5    1MM      10  M0M     KG   M1M

You then weigh according to these rules. For each column, put coins numbered 1 in the left pan, and M in the right pan. If the '1' pan goes down, write '1', if the M pan goes down, write 'M'.

After three weighings, you should have a three-place sequence, like 01M. This abc gives 9a+3b+c, where M=-1. If it is an even number, reverse the sign, and that's the coin that is not fair, and whether it's overweight or underweight. So our 01M gives 9.0 + 3.1 + 1.-1 = 2, being even gives -2, so the coin numbered '2' is underweight.

This is different to the usual answer, since we always have seven coins on each pan, (you can't do it with simply six, because at any stage, you are testing for a trinary digit, and it needs here 9 coins, which is odd.

When you do the same for four or five weighings, the process is the same, but the known good is always opposite the half-point, ie 1M1M or M1M1M. You can get to 40 or 121 coins on 4 and 5 weighings, but if you are not allowed to add a known good, then you need to drop the half-coin (7 or 20 or 61) from the list.

• I can't reconcile For each column, put coins numbered 1 in the left pan, and M in the right pan with we always have seven coins on each pan. In the first column there are 5 1s and 4 Ms. In the second column 4 1s and 4Ms. In the third, 4 Ms and 5 1s. Am I reading the columns wrong? – ganbustein Dec 11 '14 at 15:37

The way to solve problems of this sort is to think about how much information you have, which is equivalent to how few possibilities remain.

Each weighing can have one of three possible outcomes: the left pan is heavier, ther right pan is heavier, or they weigh the same. You want each outcome to correspond to (roughly) the same number of remaining possibilities.

Initially, you have 26 or 27 possibilities: one item is heavier (and there are 13 choices for which that item that is), one item is lighter (out of 13), or maybe they're all the same. Since 27 = 3 * 3 * 3, you might hope that three weighings will suffice even if it's possible that they're all the same.

But for that to happen, the first weighing has to split the possibilities into three sets of exactly 9 each.

If on the first weighing you weigh 4 items against 4 others, the split is:

• Left pan is heavier means one item in the left pan is heavier or one item in the right pan is lighter. That's 8 possibilities.

• Right pan is heavier means one item in the left pan is lighter or one item in the right pan is heavier. Again 8 possibilities.

• The pans balance. This must cover the 10 or 11 remaining possibilities. We cannot resolve these in only two more weighings. (Two weighings can have only 3 * 3 = 9 outcomes.)

So, four against four won't work. What about 5 against 5? This splits the 26 or 27 possibilities into sets of size 10, 10, and 6 or 7. Again, we cannot answer the question in only 2 more weighings.

More than 4 in each pan on the first weighing leaves too many possibilities for when the scales do not balance. Fewer than 5 leaves too many possibilities when they do balance.

The problem cannot be solved in only three weighings, even if you know there is an odd item. (Unless you know something else, like the color of the odd item, or that the odd item has a different density and there is some water we can immerse the apparatus in, or we can tie them together bolo-fashion, spin them, and observe how the center of mass moves. Or the scale has more than two pans.)

UPDATE: I just realized you only need to identify the odd item, not whether it's heavy or light. That means you start with only 13 possibilities. I'll be back.

I'M BACK... Ignore the 13th item. In three weighings, you can tell if one of 12 items is odd, and if so whether it's light or heavy. I won't re-iterate this well-known solution. Re-interpret the "none of the 12 is odd" as "the so-far-ignored 13th item is odd".

You lose the ability to tell that there is an odd item, and if the odd item is the 13th you lose the ability to tell if it's light or heavy, but if you can assume there is an odd item you can always tell which it is, and sometimes (read usually) tell whether it's heavy or light.

Solution for finding the odd marble from a set of thirteen (13) seemingly identical items

1ST WEIGHING - 5 ON 5, 2ND WEIGHING 3 ON 3, 3RD WEIGHING 1 ON 1. "S" REPRESENTS A MARBLE KNOWN TO BE OF STANDARD WEIGHT, BUT IS NOT ONE OF THE 13. USE OF THIS ITEM IS CRITICAL TO THE SOLVING THE PROBLEM

"/" => LEFT SIDE IS HEAVIER "\" => RIGHT SIDE IS HEAVIER "-" => BOTH SIDES ARE EQUAL

12345/6789S (OUTCOME 1A)

126/347

1/2 => 1H
1\2 => 2H
1-2 => 7L

126\347

3/4 => 3H
3\4 => 4H
3-4 => 6L

126-347

8/9 => 9L
8\9 => 8L
8-9 => 5H

12345\6789S (OUTCOME 1B)

126\347

1/2 => 2L
1\2 => 1L
1-2 =>7H

126/347

3/4 => 4L
3\4 => 3L
3-4 => 6H

126-347

8/9 => 8H
8\9 => 9H
8-9 => 5L

12345-6789S (OUTCOME 1C)

1011/12S (you can use "S" or any of 1 through 9)

10/11 => 10H
10\11 => 11H
10-11 =>12L

1011\12S

10/11 => 11L
10\11 => 10L
10-11 => 12H

1011 - 12S

13/S => 13H
13\S => 13L
13-S => ALL IDENTICAL
• Your question didn't say you were given anything else besides the 13 objects, otherwise you might as well have given the 13 objects with the odd one out in a nice little wrapping that marks it out. Incidentally it is not hard to prove that it is impossible if you only have the 13 objects and an ordinary weighing balance. – user21820 Dec 29 '13 at 7:38

Notation

Write the following:

• $H_n =$ set of $n$ that contains a heavy coin, $L_n =$ set of $n$ that contains a light coin
• $X_n =$ set of $n$ that contains an odd one out, $S_n =$ set of $n$ standard weight coins
• $h_n =$ set that may contain a heavy, $l_n =$ set that may contain a light, $x_n =$ set that may contain an odd one out
• $h_m l_n =$ set that definitely contains an odd one out, comprised of $m$ possible heavies and $n$ possible lights
• $h_m \cup l_n =$ union of $h_m$ and $l_n$: it may contain a heavy, or a light, or neither

So the game starts with $X_{13}$

Backward Induction

It's easiest to find a solution if you work backwards from winning configurations at each stage.

Last Move

Can win from:

• $X_2$ (weigh $x_1$ vs $S_1$)
• $H_3$ or $L_3$ (weigh $h_1$ vs $h_1$, or $l_1$ vs $l_1$, resp.)
• $h_2l_1$ or $h_1l_2$ (weigh $h_1$ vs $h_1$, or $l_1$ vs $l_1$, resp.)

Second-Last Move (Second Move)

Can get to a winning last-move configuration from:

• $H_9$ or $L_9$ (weigh $h_3$ vs $h_3$ resulting in an $H_3$ and $S_6$, or $l_3$ vs $l_3$ to get $L_3$ and $S_6$, resp.)
• $X_5$ (weigh $X_2$ vs $X_1 S_1$, resulting in either $h_2l_1$, $h_1l_2$, or $X_2$ and $S_3$)
• $h_5l_4$ [$h_4l_5$] (weigh $h_2 \cup l_1$ vs $h_2 \cup l_1$ [$h_1 \cup l_2$ vs $h_1 \cup l_2$], resulting in $h_2l_1$ or $h_1l_2$ [the same])

First Move

Weigh two sets of 4 coins against each other. The result will be one of:

• two sets, $h_4l_4$ and $S_5$, if the scales don't balance;
• two sets, $X_5$ and $S_8$, if they do

Either of these are winning configurations for the second move.

The lone standard item will have weight greater or less than the remaining items.

Let us assume it has a greater weight than the rest. Though the solution will not change either way.

For 13 items:

• Divide into 2 blocks of 4 and one block of 5.
• Let them be A,B and C.
• Put both A and B on the balance. If the defective piece is in either A or B the balance will point it out. Assuming it is in B.
• Then take the B set divide it into set of 2, weigh it again. That shall point out which side has the defective item. Repeat this again. So overall 3 weighing in this case.

• If both A and B are equal, then defective item lies in C block, which has 5 items.

• Divide C into 2,2 and 1 item. Repeat the weighing process with 2 weights on the balance.

• If it is equal, then the item lying out side is the defective item.

• If it is not equal, the balance will point out, which set has defective item in it. Weigh again with 1 item on each side of the balance to get the defective item.

Total weighing: 3 turns again.

• This doesn't work if you don't know whether the odd item is heavier or lighter than the others. – TonyK Sep 1 '14 at 9:05
• It does. If the block B has that defective item, and if it weighs more than others, then needle of the balance will point to the heavier side and if it weighs less than others, the opposite will happen. – MonK Sep 1 '14 at 9:26
• It doesn't. You can't tell the difference between Block B containing a heavier item and Block A containing a lighter item. – TonyK Sep 1 '14 at 10:11
• @TonyK. Here is a dry run. Consider we have 13 marbles who weigh 3 grams each and one is an odd weighing 4 grams : 333334333333. Then, Block A : 3333.Sum 12. Block B:3343.Sum 13. Block C:33333. Sum 15. Step 1- A vs B. B is heavier. Break B into 2 parts 33 and 43. Step 2 - 33 vs 43. 43 is higher. Step 3. You get 4 as the odd one. You can't definitely compare A with C or B with C. Does this help? – MonK Sep 1 '14 at 10:44
• So what happens if, instead, one of the marbles weighs 2 grams, and ends up in A? Step 1 yields the same result. Please think about this a bit more before posting again. – TonyK Sep 1 '14 at 10:51