Somebody told me a puzzle I really liked. It took me a few hours to figure out 90% of it and didn't figure it out completely until the next day. Nobody who I have asked this puzzle to has been able to figure it out.

You have 12 weights that look identical but one weighs more or less than the others. You don't know if it weights more or less, just that the weight is different. You have a balance scale you can only use three times. So you can place any number of weights on either side of the scale then look at the scale to see if it leans left, right or stays balanced. A single observation of the scale's balance with any configuration of weights counts as a use.

You need to find out which weight is different and if it weighs more or less than the rest only using the scale 3 times. Can you do it?

[As Lactose! observed, this attempt is very wrong anyway... so no need for spoiler]

Place any 6, 3 weigh on each balance ---- you can either eliminate that 6 or its one of them. either way 6 remains ---- observation 1

remove the top 2, if it balances, the odd ball, the odd ball is the remaining 2, note the weight on the scale ---- observation 3

One of the 2 removed is the odd ball. The one removed from the side less or more than the average weight observed during observation 3 is the odd ball

Or if it does not balance after removing the top 2, then the side that is equals to one of the calculated averages (say 2.5) in case 2 is among the 11, while the other is also now known to be more or less through the observation of the balance ---- observation 3

case 2b

Place the remaining 2 on the scale the one that weighs more or less than the average weigh from observation 2 is the odd ball ---- observation 3

****Not sure if this mis-mash is correct... whatever****

Fun logic problem, it comes up a lot in reasoning tests.

Of course it is also one of those "a ha!" moment tests. It is a variation on a trinary search, but most programmers are not comfortable with it and prefer a binary search.

I prefer the 9-weight version because it is less intricate.

I don't want to spoil it fully, but the solution starts with a 4/4/4 division, weighing two sets and leaving four weights off the scale. What happens next depends on the results of that weighing.

I don't want to spoil it fully, but the solution starts with a 4/4/4 division, weighing two sets and leaving four weights off the scale. What happens next depends on the results of that weighing.

Been thinking about this while eating, and I got to the 4/4 initial weighing quite quickly, but so far I've only managed to solve it for when the outcome of the first weighing is a balanced scale.. hm.

I think I managed to solve it. I PMed frob to verify instead of spoling it here.

by now you know the weight of each of the 11 as you can divide the total weight on one side by 2

You don't know the absolute weight when you compare weights, so you don't have a total weight.

You only know "this side is heavier/lighter", not "this side is x heavier".

---

EDIT: Not sure why I PMed frob when HappyCoder made the thread... hmph.

[spoiler]Yup, first divide in groups of 4.

Test 2 of em.

If same, all those weights are known to be standard.

Split the last group of 4 into 2x2 groups.
Test one group of 2 against 2 standard weights.
If same/different lets you know which group of 2 has the odd weight.
Test one weight from that group of 2 against a standard weight to find the odd one.


If different, one of the 8 weights is the odd one. The 4 from the 3rd group are known to be standard.

Record which group of 4 from the tested 2 is heavier/lighter. (aha) Now instead of only knowing which set of 2 groups contains the weight, its also known which group in the set of 2 contains it.

Split the 8 into groups of 2,2,3 where the 2,2 come from the same group of 4. Test the first two.

If same, test 2 weights from group of 3. We also know whether the weight is lighter or heavier based on whether the 2,2 came from the heavy or light side of the 4,4 test.

If same, the 3rd on is odd weight.
If different, we know which is odd weight based on which is heavier/lighter.

If different, we know whether weight is lighter or heavier based on whether 2,2 came from heavy or light side of 4,4 test (again). Thus we also know which of the groups of 2 has the weight.

So compare those 2 weights and we know which is odd one (as we know whether its the heavy or light one)[/spoiler]

huh

Solution

The 2/2 split doesn't tell you if the odd one out is heavier or lighter, but good work so far.

Im not exactly sure what part you mean (my explanation is not exactly well organized...) but I think that when combined with the results from the 4/4(/4) split it does give this information.

So assume the 2x4 groups are different weights (as mentioned)

Now, the 2x2 both come from the same group of 4. We know whether it was the lighter or heavier of the 2x4 groups. If the 2x2 are also different, we know the weight was in that group of 4, and because we know whether that group of 4 was the light or heavy one, we also know whether the odd weight is lighet or heavier.

If the 2x2 were same we know the weight was on the other group of 4, and as we know whether that was light/heavy we also know whether the weight was light/heavy.

huh

Your solution doesn't work in the following scenario:

[spoiler]4v4 -- scale is balanced

You now know that the special weight is among the last 4. Test 2 of those vs 2 normal ones:

2v2 -- scale is balanced

You know now that the special weight is among the last group of 2, but you don't know if it's lighter or heavier. Test one of them against a normal weight:

1v1 -- scale is balanced.

You now know that the last weight is the special one, but you don't know if it's heavier or lighter than a normal weight.[/spoiler]

I didn't look at all the other paths you wrote.

Damn, I thought I had it worked out but I think I am also at the "90% figured out" stage now. My solution works for almost all cases, it just can't distinguish between two possible locations and two possible relative weights (e.g. it's ambiguous whether the special weight is in location A and is lighter or whether it's in location B and is heavier, my solution can't tell the difference). I think I need to put some more thought into the problem, but not right now since it's way late.

It's definitely doable though, since your solution needs to produce log2(12 * 2) ~ 4.58 bits of information to distinguish all cases while your three weightings can extract at most log2(3 * 3 * 3) ~ 4.75 bits of information. It's just a matter of finding the right decision tree...