## Twelve Balls + 3

Posted by Al Gelman on December 25, 2010 – 4:31 pm

I received my set of twelve balls from the pool hall, so that I could test my solution to the twelve ball problem. But when I opened the box I saw to my horror that the manufacturer had included three extra balls! Now I had 15 identical looking balls, only one of which is either heavier, or lighter than the others. Was it even possible to solve the puzzle with three weighings on an equal arm balance? And if so, how to do it?

December 29th, 2010 at 1:06 am

Before I start, I’ll point out that I’m only doing the working to find a ‘lighter’ ball like the cue ball. I’ll keep playing around with it but I don’t think it’s possible in only three weighings to establish both the unique ball /and/ whether or not it is unique due to being lighter or heavier.

The first weighing should be six against six. If the scales are even, then the ball left over is a different weight and you can stop there. If not, whichever side is lighter is then re-weighed in two lots of three. The lighter side of the scales is then weighed again but only one against one. If one side is lighter, that’s your ball, but if the scales are even, then the ball that was left out is the light ball.

December 29th, 2010 at 1:37 am

Oops, mis-read the question there. Somehow I got 13 balls…

I’ll keep pondering.

December 29th, 2010 at 11:39 am

I would say it can’t be done with three weighings of 15 balls.

With 15 balls any one could be lighter or heavier, so 30 possible scenarios.

With three weighings each can be equal, one side lighter or one side heavier, so 3 x 3 x 3 = 27 outcomes. This could not cover 30 scenarios.

This seems to suggest that you could do it with 13 bals, but not 15.

December 29th, 2010 at 2:01 pm

Al Gelman,

Off topic:

A total set of pool balls are 16. 7 whole, 7 half, an eight ball and a cue ball (white).

The cue ball is always heavier than the others.

December 30th, 2010 at 7:12 pm

When I submitted this puzzle, I was quite convinced that a solution was possible and that I knew what it was. But then I read the Wizard of Oz’s post and I thought, uh oh. So went back and checked my solution, and sure enough it was incorrect. I thought about it for awhile, and then I saw it. With a different approach, it indeed can be done. This time I double checked my solution, and sure enough it works. So you needn’t feel as if you are wasting your time trying this puzzle. 15 balls, one of which is heavier or lighter than the others, can be solved using an equal arm balance and three weightings.

December 31st, 2010 at 1:36 am

1. Weigh 7 and 7 if they are equal the left over ball is heavier. If not, choose the heavier side and weigh 3 and 3.

2. If the two sides are equal the heavier ball is the one that is left over from this set. If not, choose the heavier side and continue.

3. Weigh 1 ball on each side, and if they are equal, the heavier ball is the one that was left out. If the sides are unequal, the heavier ball is obviously the one that is bringing the scale down/is heavier.

December 31st, 2010 at 4:57 am

Al Gelman,

I can only find the solution with 4 or 5 weightings. Are you sure it is possible with only three?

December 31st, 2010 at 2:19 pm

I think I have it. Although I am unsure how I would determine if the ball is heavier or lighter in this but I am going to assume I know that before weighing the group.

Weigh two groups of 7. If they are even, then ball 15 is the oddball.

If not…

Weigh two groups of 3 from the heavier/lighter group. If they are even, then ball 7 is the oddball.

If not…

Weigh two of the 3 balls from the heavier/lighter group. If they are even, then ball 3 is the oddball.

If not obviously one of the two on the scale is the oddball.

December 31st, 2010 at 4:01 pm

I give up! Sorry to have wasted your time. You’re quite right, you need at least 4 weithtings for 15 balls.

December 31st, 2010 at 6:42 pm

No need to feel bad about getting this puzzle wrong, Al. It happens a lot in ToM-land!

I hope this won’t stop you contributing more excellent puzzles like the four 2’s one.

Now, can we find the lighter or heavier ball out of 13 in three weighings? I don’t know, but it’s theoretically possible.

December 31st, 2010 at 7:28 pm

Thanks for the kind words WIZ. I don’t believe that 13 balls can be done in 3 weightings either. 13 balls would require ether 5 vs. 5 , and 3 , or 4 vs. 4 , and 5. I don’t see that either one of these could work.

Happy New Year!

December 31st, 2010 at 11:48 pm

I agree. With 13 balls you will always be left with at least five after the first weighing (4:4:5, 5:5:3, etc). If the odd one out is among these five then there are ten scenarios (each of the five lighter or heavier) and only nine outcomes possible from the two remaining weighings. You might get lucky and find it, but you can’t guarantee it.

Happy New Year to you, too (and to everyone else).

January 2nd, 2011 at 7:13 pm

Hi Lil’ Geek ,

I’m sorry I missed your post. in your second weighting, if the 3 vs. 3 from the heavy side is even then you have 8 (not 1) balls that are unknown. the 1 from the heavy side, and the 7 from the light side.

January 3rd, 2011 at 4:30 am

Hi, all! I am drinking in Bulgaria, so I didn’t follow the site for a while (and I will most probably keep doind this for another week), but today I glanced through this problem. It is a nice but well-known one. Actually for the good mathematitians I suggest to prove (by induction) that if you have k measurments, you can determine the fake ball among up to a set of (3^k-1)/2 balls. Hence, the above problem has a solution for 13 balls and 3 measurments (actually this is the most famous version of the whole problem and is often given at job interviews for the big companies in order to test the thinking of the applicant). Good luck in finding the strategy By the way, once you solve the partial case, the general one becomes relatively easier!

January 3rd, 2011 at 6:27 pm

Hi slavy,

I don’t quite under stand your formula. You said “you can determine the fake ball among up to a set of (3^k-1)/2 balls.” Did you mean to say

(a) N < (3^k-1)/2 or (b) N < or = (3^k-1)/2 ?

Because if you meant (b), than I disagree that it is a solution.

However (a) does work generally and of course that implies that 12 balls can be solved, but that 13 balls can not.

Let’s find out how many balls can be solved if k = 1. If we use (b) then N = 1, but that is meaningless because there is nothing for the 1 ball to be lighter or heavier than. Inequality (a) however gives 0, which is consistent.

Now let k=2 . (b) gives the answer as 4. I do not believe that you can determine which of 4 balls is heavier or lighter using two weightings. Yes it can be done if you had an additional 3 balls that you knew were normal but that is a different problem. (a) says that N= 3 , and 3 balls can be solved in two weightings. So that brings us to k=3. (a) says that N = 12 which of course we know works. (b) however says that 13 can be done. But based on the above (inductive) reasoning, and on the reasons I gave in my previous post, I do not belive that 13 is possible with 3 weightings.

In addition, even formula (a), which seems to work for k=1, k=2, and k=3, doesn’t look good for other values. If k=4 , then (a) says that N = 39, some how I don’t believe it.

January 3rd, 2011 at 8:06 pm

Hi Al. I believe that Slavy made a typo. The formula is (3^k – 3)/2

k = 1 => 0 balls

k = 2 => 3 balls

k = 3 => 12 balls

k = 4 => 39 balls

k = 5 => 120 balls

January 3rd, 2011 at 11:55 pm

Hi Chris,

I agree that your formula works, and gives the same solutions as the formula that I was calling (a). However, I still do not believe that it’s solution for k=4(which is 39) is possible. Your first weighting would have to be 14 vs. 14 , with 11 as remainder (you could not use 12 as a remainder, since that would leave an odd number.) if 14 vs. 14 is balanced, then we know that we can solve 11 balls with the remaining 3 weightings. But if 14 vs. 14 is unbalanced we have to solve 28 balls with 3 weightings which, according to your formula (or mine), is not possible. Also, Slavy in his (I’m assuming Slavy is a man, please excuse me if I’m wrong) post said that 13 could be done, but your formula (and mine too), contradicts that statement. If 13 can be done (which I very much doubt) , then that means that your formula is incorrect for k=3, but of course we have already shown that it does work for k=1,k=2, and k=3.

So what am I missing?

January 4th, 2011 at 2:15 am

Hi Slavy,

I’m glad I never had to apply for a job where you had to solve the 13 balls, 3 weighings problem!

Like Al and Chris I don’t believe that it can be done, also that your fornula (3^k-1)/2 doesn’t look right, although it gives the right answer for 2 measurements.

What do you drink in winter in Bulgaria to ward off the chill? Vodka or some local firewater?

January 4th, 2011 at 2:29 am

There is no typo in my formula I am not sure what exactly your statement of the problem is, but I guarantee you that I can constractively prove that if I have (3^k-1)/2 balls, one of which has a different weight, I can tell you which ball it is after k weighings. It is not easy but it is relatively well-known (the first time I came upon the formula was when I was 16 years old and participated in the preparation of the national mathematical team, i.e., more than 10 years ago). The “trick” is that even it may sound counterintuitive, I can tell you which ball is the fake one but I am not always able to tell you weather it is lighter or heavier. As I said the case 3 measurments 13 balls is the most famous one and an year ago I gave the problem with 4 weighings and 40 balls in a local bulgarian site (so I checked the correctness of the formula).

Wizard, in Bulgaria we have “rakia” which is the local firewater and plenty of home-made wine. So far it works against the chill

January 4th, 2011 at 3:06 am

Hi slavy,

The problem was to determine which ball was different than the others AND to determine whether it was heavier or lighter. Just finding the ball that is different is not a solution. and is actually rather easy to do.

aaaa vs. bbbb, with ccccc left. if they balance then

ccc vs. xxx with dd left. if they ballance then d vs x. (Note that in this case we cannot determine if d is heavier or lighter because if d1=x, d2 is it and there are no more weightings.)

if ccc vs xxx does not ballance (assume ccc is heavy) then

c vs. c, the heavy one is it. if equal then the third one is it. The case of aaaa vs. bbbb do not balance has already been disscussed in previous posts.

January 4th, 2011 at 5:51 am

The formula I found (on the internet, twice) was for the full determination.

I agree that 13 can be dome, but not with relative weight – except by luck.

January 4th, 2011 at 6:22 am

Also note that whatever you start with, you weigh ome third versus one third. If that balances, you have the remaining third with one ball more that the formula predicts (e.g. strting at 120 balls, you’d get 40 = 39+1), but you’d have 80 balls that you know are the same – unlike if you were merely given 40 balls initially,, and that is an important difference.

e.g. 2, if start with 12, if first 4 v 4 balanced, you’d have 4 = 1+3 remaining, which you know can be done as you’ve done it already.

I don’t know how to solve it though, regardless of whether or not the first weighing is equal.

Also I know that Slavy is right – 13 can be done, but you can only guarantee to identify the odd ball, but not its relative weight. I trust him in that his formula is true generally (for k ≥ 1).

January 4th, 2011 at 8:36 am

I’ve only just noticed that page is for a 15 ball problem, I had assumed that it was for the classic 12 ball problem. I got to it from a comment rather than the home page.

January 4th, 2011 at 2:45 pm

I disagree with you that slavy’s formula works. It works only for the much simpler problem of determining which of the balls is odd. The problem we are trying to solve is to also determine whether the odd ball is heavier or lighter. I don’t think that you would care to fly in an airplane that was designed using mathematical formulas that worked only under some lucky circumstances. Your formula, as given in post #16 does work, and it proves that you can’t determine in three weightings whether the ball is heavier or lighter, if you start with 13 balls.

January 4th, 2011 at 4:10 pm

Hi Al. Sorry, I probably wasn’t being clear enough.

For the complete (heavy/light) determination use (3^k – 3)/2

For the partial (odd ball only) determination use (3^k – 1)/2

I’m taking the second one on trust. But it’s only one ball extra, so I’m not shocked.

The first is “well known”, the second seems reasonable in view of the first.

Slavy typically only makes silly arithmetic errors, and he’s usually the first to spot them too.

January 4th, 2011 at 8:41 pm

Hi Chris,

I don’t mean to flog a dead horse, but I need to try and clarify this issue, if for no other reason than to find the fallacies in my own reasoning. First of all, I don’t believe that slavy has made any arithmetic errors in this case. I believe that he is simply solving a different problem, not the one that we have been trying to solve.

Second, I believe that the equation that you came up with only works for k=1, k=2, and k=3. For k=4 its solution is 39 and that leads to inconsistencies. No mater how I divide up the 39 balls I always wind up with the problem of solving 5 balls in two weightings. Now if you plug k=2 into your equation you get (3^2 -3)/2 =3. But because we have additional “normal” balls, then we know we can solve 4 balls in 2 weightings. However, I have been unable to solve 5 balls in 2 weightings. So your equation that works for k=2 and k=3, tells me that the same equation does not work for k= 4, and possibly other values of k. Unless, of course, I am missing something. How did you derive those equations? Do you know how to solve 39 balls?

January 4th, 2011 at 9:26 pm

Hi Al. I thought my last post should have clarified that.

The formula that Slavy posted, is for the maximum number of balls that you can handle in k weighings, where you only need to identify the dodgy ball, but not to determine if it is heavier or lighter.

For that we use (3^k – 1)/2

k = 1 => 1 balls (it automatically is the dodgy ball)

k = 2 => 4 balls

k = 3 => 13 balls

k = 4 => 40 balls

k = 5 => 121 balls

But if we have to say that it is heavier or lighter

use (3^k – 3)/2

k = 1 => 0 balls

k = 2 => 3 balls

k = 3 => 12 balls

k = 4 => 39 balls

k = 5 => 120 balls

Note that you always start off, weighing up to one third versus one third (at least I doubt that anything else will work).

In the interest of keeping everything together, note that if going for the full determination (with max 12 balls), that you’d start by weighing 4 against 4). If they balanced then you are left with the problem of 4 balls in 2 weighings, which can’t be done from cold (as 3 is the max then), but can be done, in this case, because we have just found 8 known identical balls, so we can take advantage of that.

Similarly, if you started with 39 balls, you’d start with 13 versus 13. If that balanced, you’d know that the remaining 13 must contain the odd ball. But again, that’s 1 more than the 12 from cold, but you’ve just found 26 identical balls.

I know that I’m picking the special case, but that’s only to illustrate that it’s not actually unreasonable that the problem can be solved.

The only reason that I know these results are true is because I did a Google with “twelve balls weighing problem” and similar (also use coins instead of balls).

Take a look at:

http://mathforum.org/library/drmath/view/56766.html

http://www.iwriteiam.nl/Ha12coins.html

January 4th, 2011 at 9:29 pm

Al, you’ll need to check behind the scenes, I’ve posted a reply, but it is awaiting moderation (by you) as it contains links to external sites.

January 4th, 2011 at 10:13 pm

Hi Cris,

I understand that slavy’s equation is a solution to the simpler problem, and that your equation solves the complete problem, as I said in my previous post.

My problem is that I can’t get myself to believe that your equation works for k=4, I understand that solving 13 balls with 26 known “normal” balls is different that solving 13 cold. However when I try I always get in a situation where I have to solve 5 balls in 2 weightings. first of all your equation says that only 3 balls can be solved, but of course because we have several normal balls, we can solve for 4 balls, which of course we have already done. But 5 balls is way out of range. And I have tried, but I can not do it. So if you know the solution to the 5 ball in two weightings then please tell me, or if you have the solution to the 39 balls in 4, I would love to hear it. That is why I was interested in seeing the derivation. Thanks for the link; I haven’t looked at it yet.

I did get on the page for approval or disapproval, but frankly I don’t know what to do with it. What does approval or disapproval mean in this instance? I see many posts here that are already on my post site, without my having done anything.

January 5th, 2011 at 12:00 am

Hi Al. I don’t know how you get to the point of having to weigh 5 balls in only two goes. That definitely can’t be solved.

Try this link, it’s a solution for the 120 balls problem :

http://www.cut-the-knot.org/blue/OddCoinProblems.shtml

I have no real idea why some posts need approval and some don’t. But you’ll find that by clicking on a pending post that you’ll get links that let you approve, delete, unapprove or even edit posts – but only if they are on your blog and only if you are also an author (whatever that means). Approve means to allow the post to appear publicly rather than only behind the scenes (in yellow).

January 5th, 2011 at 12:07 am

Ooops, that link was a solution to k = 7 => 1092 balls problem. But makes it clear how to do all such problems.

January 5th, 2011 at 12:24 am

Hi AL. Having just taken a fairly good look at that last link, I’d be more than happy for you to delete my post with the two links in it.

The link http://www.cut-the-knot.org/blue/OddCoinProblems.shtml

contains an excellent general solution. It’s only weakness is that what you do depends on the results of the weighings as you proceed. i.e. it doesn’t pre-ordain the weighings to be made, but probably could be readily modified to do so (it’s that good a solution).

January 5th, 2011 at 2:23 am

Hi all, I agree with Al’s post # 28. We need to see how 39 balls can be resolved in four weighings. Would someone like to demonstrate how this can be done?

The best strategy that I can come up with for four weighings involves 24 balls: Take 12 of these and weigh six against six. That will determine which group of 12 contains the odd ball. Then go from there with the 12 ball/three weighing approach that has already been shown.

But 24 balls is a long way short of 39. Perhaps one of my learned correspondents can point the way.

January 5th, 2011 at 2:37 am

I agree with Chris for the formulas and disagree that my formulation is easier than the other. They are actually absolutely the same and the extra ball plays role only in the easier case, spotted by Al in post 20. But everything else is absolutely the same. There is a nice constructive solution based on triadic number-representations but I don’t have the time now and probably in a week or so, when I will be back in Germany I can try to write it down…

January 5th, 2011 at 7:32 am

Hi everyone, the solution is here:

http://www.cut-the-knot.org/blue/OddCoinProblems.shtml

It deals with all cases (and all obvious variations on the theme). It doesn’t explain how to do what he calls “Method A”, but it’s easy to work that out. Many of the solutions require that you use “Method A” to finish off. So I’ll demonstrate it:

In Method A, you know whether the odd coin is heavy or light at the outset. Then you can find the ball amongst 3^k in k weighings. i.e. 1 weighing, 3 balls; 2 weighings, 9 balls; 3 weighings, 27 balls; 4 weighings, 81 balls etc.

In each case split the balls into 3 equally sized groups. e.g. 3 balls. put 1 ball on each side. If it balances then it the remaining ball is the one left over. If it doesn’t balance, then if you know it’s heavy then it’s on the down pan or if it’s light it’s on the up pan.

e.g. 9 balls. Weigh 3 against 3. And use the same logic as for 3 balls to find which group the ball is in – that’s 1 weighing. Now use method A again to get the individual ball.

e.g. 27 balls. 3 groups of 9. Use method a to find he group of 9. Then split the containing group in to 3 piles and use method A for 9 balls.

The recursion should be more than obvious by now, so I’ll move on to solve the 39 ball problem:

For convenience, I use a standard move “rotate” – that means, move right hand pan sub-group to the table, the left hand sub group to right pan, and the one the group that was on the table to the left pan. For the full 39 ball problem. Split the balls into 3 groups of 13. Then split the 13 balls into sub-groups of 1,3,9.

Put two groups (of 13) on the pan, note the result – weighing 1. Now rotate the sub-group of 9 balls. Observe the result – weighing 2. If the weighings caused changes, then you can easily deduce the sub-group (of 9) and if it is heavier or lighter. So finish off with method A, using a total of 2+2 = 4 weighings.

If the first 2 weighings caused no changes, the you can ignore the bags of 9. Rotate the bags of 3 and note the result – 3rd weighing. If there is a change, then you can deduce which sub-group of 3 and heavier/lighter. Use method A to finish off.

If there was no change (at the 3rd weighing), then you can also ignore the sub-groups of 3. Rotate the sub-groups of 1 – 4th weighing. There must be a change, and you can easily deduce the coin and heavier/lighter.

I hope that I’ve covered everything (e & e excepted).

January 5th, 2011 at 7:36 am

Aaargh, that should have finished with rotate the sub-groups of 1 for the 4th weighing. It’s only a typo, not a fundamental flaw.

January 5th, 2011 at 9:10 am

Would you believe that, once I had understood the method, I wrote that solution out without referring to the source site at all.

Even sillier, I had never inended to do this problem. But I’m now glad I have – I hadn’t previously considered the more general problem and the variations on it. But now I know it, it’s a doddle. So, thank you Al for pushing me.

It actually is a bit trickier if you don’t have the full set of balls. e.g. if you only had 38 or 37 say. But that’s fairly easily dealt with.

January 5th, 2011 at 10:48 pm

Hi Cris,

Your solution works beautifully. I believe that the general solution given by Jack Wert is quite brilliant. The only quibble I have with it is that his solution is based on two formulas, which are given, but not proved. ( N= 3^k) for method A, and

N= (3^k -3)/2 ). There’s no doubt in my mind that they work, but I would love to see a rigorous proof.

I wondered, like you, how the method would work for other amounts of balls. I tried 10, which should be possible with 3 weightings. Here is what I came up with.

1) AAA A = BBBB , CC

2) C1 = A (3) C2 > BBB B, CC

2) CCB A > AAA B , BB

3) A > C, A is the heavy one, A = C, B is the Light one

Or

2) CCB A < AAA B, BB

3) B(light) < C, B(light) is the odd one. B(light) = C , B(heavy) is the odd one

January 6th, 2011 at 9:44 am

Hi Al. I have to admit that the cases with missing balls looks pretty messy.

I don’t know how to establish the various formula, especially as they allegedly represent the very best that can be done.

The only thing I can readily see, is that in 1 weighing you can only get 3 possible outcomes, and so in k weighings, there can at most be 3^k outcomes. So that’s only 3^k possible bits of information. As method A seems to be entirely compatible with that (and the recursive demo I gave) was easy, I’m satisfied that method A has been proven (that’ll give Slavy the horrors).

As exactly 1 of the balls is dodgy, we cannot have a case where moving the dodgy ball doesn’t cause a change. So that eliminates 3 (independently of k) possible outcomes. But for each set of possible outcomes, half of them simply correspond to a mirror image set of operations and don’t produce genuinely unique results. Hence (3^k -3)/2. But I know that that argument is thinly disguised waffle. i.e. it is bullshit.

I can’t think of a strategy to do a proper mathematical proof I guess that by starting with k = 2 (3 balls) that you can demonstrate by simple exhaustive analysis that the equation holds. But I can’t think of how to make e.g. a recurrence procedure. With method A, finding a recurrence procedure was a doddle, but didn’t inherently establish that it wasn’t possible to do better.

May 13th, 2011 at 7:10 am

It is possible to finish with three weighings. Weigh five balls against another five. If you are trying to find the lighter ball, pick the side that is on the higher side. If there is no higher side, take both sides off the balance and take the other five. Place two on each side of the balance from the five balls you set aside. Take the lighter side. If there is no lighter side, the one ball left over is the lighter one. Take the two balls that were on the lighter side and place each one on a side. The lighter one is the ball you are looking for. If you are looking for the heavier ball, take the heavier side each time instead of the lighter side.

May 13th, 2011 at 7:19 am

I just read the question again and realized you probably dont know if the ball is lighter or heavier. If not, it is possible to find which ball it is, but it is not probable. It all depends on luck.

I am going to label the balls 1-15 to make explaining the possible solutiion easier.

You must weigh balls 1-5 against 6-10 and they must weigh the same. Then weigh balls 11-12 against 13-14. They must be the same. Then you will know ball 15 is your answer in 2 weighings. Use the third to find whether it is lighter or heavier.