The 12 Ball Problem

This is two problems, using a 2-pan balance.

Easier: You have 12 identical-seeming balls, except one is a tiny bit heavier, which you can detect with the 2-pan balance. In how few weighings can you guarantee that you can find the heavier ball?

Harder: You have 12 identical-seeming balls, except one has a weight which is a tiny bit different, which you can detect with the 2-pan balance. In how few weighings can you guarantee that you can find the different ball and whether it's heavier or lighter?


For the easier problem:

So the easier problem can be done in 3.

Plus, in the 3rd step of this first problem, we found we could find the heavier ball out of 3 with only one weighing by using the strategy of leaving one out.


For the harder problem, it's pretty easy to see it can be done in 4.

One way to do it is to weigh 6 vs 6. One side will go down and we then know that 6 are heavier or the same, and the other 6 are lighter or the same. If we label them with HS (heavier-or-same) and LS (lighter or same) (and making the L have a double stem so it uses the same weight of ink), then we can, in the 2nd weighing, weigh 3 HS and 3 LS against the other 3 HS and 3 LS and narrow it down to 6. In the 3rd weighing we can narrow it down to 3, and finish in the 4th weighing. So we can solve it in 4.

Can we solve it in 3?

We couldn't, for a long while. But if it couldn't be done in 3, perhaps I could prove it couldn't be done in 3. That process somehow led to a solution.

To describe it, first let me underline some things.

  1. We don't have to weigh all the balls in a weighing.
  2. Since we won't weigh the all the balls in the first weighing, for the second and later weighings we'll have at least 2 balls that we know are the standard (same) weight. Those could be useful.
  3. To reason about the balls, it will be handy to mark each with a unique number, plus what we know about it. So let's call them at the beginning 1/LSH, 2/LSH, ... 12/LSH, where LSH means the weight could be less, the same/standard weight, or heavier.
  4. As I weigh, if a side goes down, I know that an LSH ball on that down side is not lighter, it's either the standard weight (S) or heavier (H), so I can remove the L and call it an SH ball. Similarly, on the higher side of the balance, the balls are not heavier, so I can remove the H.
  5. An LS ball is lighter or standard. But if a ball ends up on the lower side, it's either standard or heavier. But if an LS ball ends up on the lower side, since we know it's not heavier, it must be standard, and the different ball must be one of the other ones. Similarly, an HS that ends up on the upper (lighter) side must be standard.

How many LSH balls can I solve in one weighing? The answer is just one. I have to weigh it against a standard ball.

But I could solve one LSH and either one LS or one HS in one weighing. If the LSH is the same as the standard ball, the other ball is not standard so if it was an HS, I know it's heavier, if it was an LS, it must be lighter.

And I can solve 3 balls in one weighing if each is LS or HS. If they're not all LS or all HS, I can just weigh against each other the two that are marked the same. If they're equal, it's the third one.

How many LSH balls can I solve in 2 weighings? Say this number is Max2. If I know what Max2 is, then I can remove this many balls from the initial set. If I start with 12 balls, I can weigh half of (12 - Max2) balls on the left side vs the other half on the right side. If they weigh the same, then I know the different ball is in the set of Max2 I took out, and I can find the different ball in 2 weighings.

In 2 weighings, I can certainly solve a set of 2 SLH balls. Weigh each one against a standard.

Can I do 4 if I weigh 2 against 2? I will get something like
      1/LS 2/LS and 3/SH 4/SH
Can I find out which it is in one more weighing? No. I have to weigh the lighter ones against each other or the heavier ones against each other.

Can I do 4 in 2 weighings if I weigh 2 against 1 plus a standard, and leave one SLH ball out? Yes, like:
      1/LSH 2/LSH vs 3/LSH 0/S

I'll use the word solve to mean finding the different ball and knowing whether it's heavier or lighter.

Now we know:

So I can take 4 out of the original set and just weigh 4 vs 4:
      Weighing 1: 1/LSH 2/LSH 3/LSH 4/LSH vs 5/LSH 6/LSH 7/LSH 8/LSH

If they weigh the same, I know I can find the different ball out of the 4 I set aside in 2 more weighings.

If they don't weigh the same, I know the ones on the lower pan are not lighter, and the ones on the upper pan are heavier. so it'll be a situation like:
Result: 1/LS 2/LS 3/LS 4/LS vs 5/SH 6/SH 7/SH 8/SH

These are either lighter or heavier, so I can take 3 away, say 3 heavier ones, 6/SH 7/SH 8/SH.

And then I weigh 3 of the 5 that are left vs 2 plus a standard, like:

      Weighing 2: 0/S 1/LS 2/LS vs 3/LS 4/LS 5/SH

If they weigh the same, then I know the different ball is in 6/SH 7/SH 8/SH, and I can find the heavier ball in the 3rd weighing.

If the left side goes down, 1/LS and 2/LS are not heavier, so they must be standard and one of the ones on the right is lighter. That's not 5/SH, so it must be one of 3/LS and 4/LS.
      Weighing 3: 3/LS vs 4/LS
The lighter one is the different one.

If the right side goes down, 3/LS and 4/LS are not heavier, so either 1/LS or 2/LS is lighter, or 5/SH is heavier. So I'll weigh 1/LS vs 2/LS:
      Weighing 3: 1/LS vs 2/LS   with 5/SH not weighed
The lighter one is the different one. Or if they're the same, then 5/SH is heavier and is the different one.

Thus, I can find the different one, and whether it's heavier or lighter, in 3 weighings.


Having done this, I see that after the first weighing, I could have put only 2 aside instead of 3 and weighed:
      Weighing 2: 1/LS 2/LS 6/SH vs 3/LS 4/LS 5/SH
That's a bit interesting that I could have handled 8 LSH plus one that was SH or one that was LS.

So, in the first weighing, I could have weighed 5 LSH vs 4 LSH plus a standard. So if I had a standard, I could solve 13 LSH balls!

Again, I'd put 4 to the side and in the first weighing, weigh 4 vs 5.
I'd end up with 5 balls that I know are HS and 4 that are LS, or 4 HS and 5 LS. I could put 3 to the side and in the 2nd weighing, weigh 3 vs 3.


This made me reconsider the first version of the problem where I know that all the balls are heavier. (And of course, I could also solve it if all the balls are lighter.) When I solved this simpler problem initially, I naturally split the problem into 6 vs 6. But after having done the harder problem, I saw that I could split it into 4 vs 4 with 4 left out.

What if I took the way of solving the second problem and applied it to the first?

I can find the heavier of 3 in one weighing. So I now see that in two weighings, I can find the heavier of 9!

Again, this is done by putting 3 to the side, and weighing 3 vs 3. There are 3 results, the left pan is heavier, lighter, or the same, which determine which set of balls contains the heavier one, the left pan, the right pan, or the 3 I put aside.

By applying the lessons of the second, harder problem to the first, I was able to see I can solve of the first, 9 in 2 weighings.

Using the same method, I see that in 3 weighings, if I know one of the balls is heavier, I can find the heavier ball out of 27. I can weigh 9 vs 9 with 9 left out.

So in N weighings, I can find the heavier ball out of 3^N.

By applying the lessons from solving the harder problem to the easier problem, I was able to solve the general case of the easier problem!


This gave me an idea about the second problem in more weighings.

In 4 weighings, we could split LSH 12 off and weigh 13 vs 13. So we could handle 12+26 = 38 total.

If the 13 vs 13 weigh the same, we can solve the set we put aside, the 12 LSH, in 3 weighings.

If one side goes down, we have 13 + 13 = 26 heavier and lighter ones. We already know that we can solve 27 if we know whether each is heavier or lighter, so we can certainly solve 26.

So we can do:

So we can at least do 4*(3^(N-2)) in N weighings.
This is 4, 12, 36, 108
Maybe I'll come back sometime and figure out the formula for the exact number.

It was interesting that

Why did I keep at it, looking to see what I learned, and looking at the general cases? I guess that's just what my brain does. I guess that's the kind of curiosity and persistence that over the last almost 50 years, since I started college, has made me into an expert problem solver...