## The Defective Ball

You have 39 balls in front of you. All but one are of equal weight. You do not know whether the defective ball is lighter or heavier than the normal balls. You are given a comparison balance. You can use the balance only 4 times. How would you find out which is the defective ball? Is it heavier or lighter?

*Thanks to Suineg for submitting* : )

Answers can be written in the comment section below; will unmask in several days, thanks.

abcbcdcdef| Profile April 30th, 2009 - 8:45 amThis is a great puzzle, particularly ’39 balls’ is the maximum no. that using the balance 4 times can sort out. Thanks for sharing.

So, for the explanation, it’s a bit complicated but I hope you won’t feel too confused; ‘xxx’ represents balls that are normal; and ‘(…’certain brackets represent the set that I have narrowed down to; H/L

represents heavier or lighter.

1st try:

1-9,10-13:14-17,18-26

which leads to two possible results

A.balanced (27-39)

B.light:heavy(1-26), if it is heavy:light, then just reassign the numbers, I don’t bother to list out all the cases, hope you can follow.

For A,

2nd try:

27-30:31-34

which once again it leads to two results

a.balanced(35-39)

b.light:heavy(27-34),once again if it’s heavy:light, just reassign the no.

For a,(B will be for later)

3rd try:

xxx:35,36,37

which narrows down to two results

I.balanced(38,39)

II.unbalanced,35-37 will either be H/L, take note of whether it is H/L

For I,

4th try:

x:38—-balanced39)so 39 is defective

—-unbalanced38)and BTW you know if it is H/L

ForII,

4th try:

35:36—balanced37)

—unbalanced35/36)if in the 3rd try, you know that the defective ball is H, then the H ball this time is defective; same with L.

For b,(that is after the 2nd try)

3rd try:

27,28,29,31:30,x,x,x(30 and 31 switched places)

which leads to three cases

i.light:heavy(27-29, and the defective ball is L)

ii.heavy:light(30,31)

iii.balanced(32-34, the defective is H)

For i,4th: 27:28

For ii, 4th: 30:x

For iii, 4th: 32:33

(the rest is omitted for its simplicity, like previous deductions, you can determine which is defective)

Finally, we come to B (that is after 1st try)

2nd try:

1-9,14-17:10-13,xxx (—a total of 13 normal balls)

which leads to three more cases(uhhh)

‘.light:heavy(1-9, lighter)

”.heavy:light(10-17)

”’.balanced(18-26, heavier)

For’

3rd try:

1,2,3:4,5,6

if unbalanced, take the lighter set, then compare two of them to each other, either the lighter one is defective or the one that have not been weighed is.

if balanced, compare 7:8, the lighter one is defective.

For”’, it’s similar to ‘, just change ‘light’ to ‘heavy’ and the rest is the same.

For”

3rd try:

14,15,16,10:17,x,x,x

smilar to 2b, you can deduce the defective one, so I won’t bother writing it again.

—————————————————–

and that’s all, all the cases are covered, and you should be able to find out the defective ball.

I know my explanation is very complicated and messy, but I really hope you can make sense of what I have siad.

Once again, thanks for the puzzle, Suineg. I really appreciated it.

Shawn| PUZZLE GRANDMASTER | Profile April 30th, 2009 - 2:57 pmThis is a rework of the famous 12-ball problem, whose solution is well-known. Going to 39 balls reduces the problem, after step #1, to one of 13 balls. This can be solved in the same manner as the 12-ball problem to determine which ball is not the same as the others (which I won’t derive here – no need to waste ink!!), but you can’t ALWAYS tell whether the misfit ball is light or heavy. When the balance shows that every measurement you take is equal (13 vs. 13, 4 vs. 4, 3 vs. 3, and 1 vs. 1), you will be left knowing that the remaining ball must be the “different” one, but not able to prove that it is either lighter or heavier than the others.

A possible way to skirt this issue would be to place the misfit ball in one hand and any of the remaining balls in the other hand. If the difference in weight is significant enough, you will be able to tell whether the misfit ball is heavier or lighter than the others.

But I don’t think you can use the scale to positively prove the issue in 4 turns.

Obiwan| Profile May 1st, 2009 - 12:27 amPerhaps I should ask what “You can use the balance only 4 times.” actually means. Regardless, it seems simple… 1. Divide the 39 balls into sets of 13 & put 2 sets in the balance and note what happens. 2. Replace the set in one pan with the 3rd set. These two steps allow one to identify the set that has the “odd ball” and whether it’s heavier or lighter. 3. Take the odd set and put 6 balls in each pan and hold the last ball. If pans balance, then odd ball is in hand. 4. If not, then take the 6 balls in the defective pan and place 3 in each pan; then simultaneously remove one ball from each pan–if pan balances, one is holding the odd ball; if not, repeat this once. I submit I have “used” the balance pan only 4 times and am simply removing the balls one at a time and observing what happens.

Am I parsing words—is there another way to do it?

Migrated| Profile May 1st, 2009 - 7:19 amYou separate the 39 balls into 13 piles of 3. You next take 12 piles of 3 and separate them further into 4 equal groups. So you would have 3 piles of 3, or 9 balls in each group. Let’s label the 4 groups as A, B, C and D. We will call the 13th pile of 3 balls – E.

Weigh A against B. If A is heavier than B, then weigh A against C. If A is still heavier than C then the defective ball is heavier and is in A. This is because B must equal C due to those groups not having any defective balls. If A is equal to C on the second weigh, then the defective ball must be in B, and it is lighter than the rest. If A and B balance but C is heavier, then the defective is in C, same applies if C is lighter than A. If B is heavier than A, then repeat as above but change A to B where appropriate. If A = B and A = C, then the defective ball must be in either D or E.

If we have discovered that the defective ball is in A after the second weigh. We by this stage would know if it was heavier or lighter than the rest due to the previous 2 weighs depending on whether A or B was heavier or lighter. Let’s for this, assume we know it’s heavier. Take the 3 piles of 3 and weigh any two groups against each other. If they balance, the defective is in the last group of three, otherwise it would be in the heavier pile. Last weigh, you take two of the three balls and weigh them against each other. If they balance, it’s the ball not weighed, otherwise it is the heavier side. Vice versa for the lighter ball.

If the defective was in either D or E, is the tricky part. We only have 2 weighs left and 12 balls to determine. This is the part where I am stuck. So far so good. Haha! I think my method at the beginning got me stuck. Well, I did my best.

Nice puzzle Suineg.

fozzie33| Profile May 1st, 2009 - 7:40 amcompare 19 v 19, if equal, then one left out is it, if not, take one of lesser weight

compare 9 v 9, if equal, then one left out is it, if not, take one of lesser weight

compare 3 v 3, if equal, compare 1v1 of remainder, if equal, then remainder 1 is it, if not, lesser is it,

if 3v3 is less, compare 1v1 of remainder, if equal, then remainder 1 is it, if not, lesser is it,

Mashplum| PUZZLE MASTER | Profile May 2nd, 2009 - 6:22 pmThe four steps vary based upon what happens in each step, but each path uses the balance four times.

A1: Place #1-13 on one side of the balance and #14-26 on the other. If they are equal, the defect is in the group #27-39 (go to step A2.) If they are unequal, #27-39 are true (go to step B2.)

A2: Of the remaining 13 balls, place #1-9 on one side of the balance and nine known to be true on the other. If they are equal, the defect is in the group #10-13 (go to step A3.) If they are unequal, #10-13 are true and it is now known if the defect is heavy or light (go to step B3.)

B2: Remove nine balls from the heavier side and replace them with nine balls from the lighter side. Replace those nine with nine known to be true. If the sides are now equal, the defect is heavy and is one of the nine removed (go to step C3.) If the heavy side is now lighter the defect is light and is one of the nine moved (go to step C3.) If the heavy side is still heavy, either one of the original four heavies is the defect or one of the original four lights is (go to step D3.)

A3: Of the remaining four balls, place #1-3 on one side of the balance and three trues on the other. If they are equal, the defect is #4 (go to step A4.) If they are unequal, #4 is true and it is now known if the defect is heavy or light (go to step B4.)

B3: Of the remaining nine balls, place #1-3 on one side of the balance and #4-6 on the other. If they are equal, the defect is in the group #7-9 (go to step B4.) If they are unequal, the defect is in the group that is too heavy or light based on the previous step (go to step B4.)

C3: Of the remaining nine balls, place #1-3 on one side of the balance and #4-6 on the other. If they are equal, the defect is in the group #7-9 (go to step B4.) If they are unequal, the defect is in the group that is too heavy or light based on the previous step (go to step B4.)

D3: Of the remaining eight balls four are potentially too heavy and four potentially two light. Remove three balls from the heavier side and replace them with three balls from the lighter side. Replace those three with three known to be true. If the sides are now equal, the defect is heavy and is one of the three removed (go to step B4.) If the heavy side is now lighter the defect is light and is one of the three moved (go to step B4.) If the heavy side is still heavy, the original heavy is the defect or the original light is (go to step C4.)

A4: Compare the defect to any other ball to see if it is heavy or light.

B4: Of the remaining three balls, place #1 on one side of the balance and #2 on the other. If they are equal, the defect is #3. If they are unequal, the defect is the one that is too heavy or light based on the previous step.

C4: Compare the lighter ball to a known true, if it is still light, then it is the defect. Otherwise the remainder is heavy.

scottk| Profile May 3rd, 2009 - 5:50 pmi don’t think I can make this work but I’ll do my best.

split into 4 groups: 10, 10, 10, 9. weigh the first 2 ten together, if the same, weigh the third 10 against either of the first. if the same, select the 9 group. if the first 2 are different, compare either vs the third one and youll know which to select.

either way you should have weighed it twice.

if the odd ball is in the 10 group, split into 3 groups of 3, with a single ball remaining, as per teh previous steps, weigh any 2 groups of 3 together, eitehr way compare to the last group of 3. if one of the groups of 3 has the ball, select it and repeat the previous steps with single balls. if neither of the groups of 3 are it, the remaining ball is the answer.

so if it was in a group of 3, it should take you 6 steps i believe, and if it was the single ball remaining it should take only 4.

if the odd ball was in the 9 group, repeat the steps as in 10, and it will take you 6 steps.

bizarette18| PUZZLE MASTER | Profile May 5th, 2009 - 10:39 pmThis is quite hard to describe without a biro: First separate into 3×13 batches and compare two {comparison 1}. If even take 3rd lot and compare 9 of them with 9 known regular balls {comparison 2a}. If this is uneven then do 9 ball/2 step test:3v3: if even-test other 3:1v1 ; if uneven take 3 that agree with other test ( heavy or light) and test 1v1 (uneven: take the one that agrees, even: take the untested one). If comparison 2a is even -then test 3 of remaining 4 against 3 regular balls: if uneven do 3 ball test, if even- it’s the last untested ball – compare with any other for heavy/light.

If comparison 1 comes out uneven: combine 6 of first batch with 3 of second and compare with another 6 of first and 3 of second {comparison 2b}. If this is even, then compare two lots of three of remaining seven from second batch. If uneven do 3 ball test on 3 that agree (H/L) with comparison 1: if uneven compare last remaining ball from second batch with any known regular ball – if this is uneven then it’s the last remaining ball from the first batch.

If comparison 2b is uneven, then one batch of 6 and one batch of 3* agree (H/L) with comparison 1. Split and test the batch of 6 – 3v3. If uneven do the 3 ball test on the agreeing 3, if even do it on the batch of 3*.

That was fun to do, but I hope someone else puts up a better explanation than I have.

Falwan| Profile May 6th, 2009 - 4:46 amThank You…bizarette18:

Wouldn’t it be easier to draw a diagram of your “brilliant” solution and upload it as a picture?!!

st3f| Profile May 6th, 2009 - 10:58 amI can give an alternate method, but working through the solution would take a lot of space here.

We have four weighings. That gives us a possible 3^4 = 81 outcomes we can determine. We have 39 balls, each one can be heavy or light. That means that there 39*2 = 78 outcomes that we have to map onto the 81 possibles.

If we call ‘scales balanced’ zero (0), ‘scales left side down’ one (1), and ‘scales right side down’ two (2), we can express all the possible outcomes as four digit base three numbers. That allows us to write them down in a table. So 1020 is first weighting left side heavier, 2nd weighting level, third weighing right side heavier and fourth weighing level again. We can pair these up. for example the opposite of 1020 is 2010 since if, for example 1020 represents ball 16 light then 2010 will represent ball 16 heavy.

We write these out as a table and assign a ball number to each of the pairs of numbers. That gives us 40 pairs of numbers (we don’t use 0000 since that means that all the balls we have weighed are the same). But wait, weren’t there only 39 balls? Don’t worry that’s next.

Once we have out table of forty pairs we can work out which balls are in which weighing. If, for example, 1020 (again) is 16 light, it means that we’re weighing ball 16 on opposite sides of the scales in weighings 1 and 3 and not at all in weighings 2 and 4.

Once we have done this for all the balls we can work out how many balls are in each weighing. This is where we lose a solution. Since we can only weigh even numbers of balls, we remove the ball that is in and only in the weighings of odd numbered balls. We can then number the balls, weigh according to our table and solve.

All in all you’ll probably prefer bizarrette’s solution.

If we

suineg| PUZZLE MASTER | Profile May 6th, 2009 - 5:14 pmcool, I will see your answers with more detail today and sent my answer in a jpg to RK tonight in a diagram but cool, seem pretty cool and different to my answer, see ya

suineg| PUZZLE MASTER | Profile May 6th, 2009 - 10:16 pmVery cool solutions, some very complicated ones, there can be many ways to solved this problem, I already has sent my answer to RK, I apologize in advance for a little bit of a messy and bad letter, has to scan my solution, however my answer is a diagram that shows a way to solved and know for every case wich is the defective ball and if it is heavy or lighter, I hope you find it cool and helpful, see ya

RK| Founder | Profile May 6th, 2009 - 10:50 pmHere are Suineg’s scans:

http://www.smart-kit.com/wp-co.....uineg1.jpg

http://www.smart-kit.com/wp-co.....uineg2.jpg

http://www.smart-kit.com/wp-co.....uineg3.jpg

suineg| PUZZLE MASTER | Profile May 7th, 2009 - 9:51 amPlease let me know if the solution is not clear or anyone think there is a fault in it, to discuss it with more detail.

the_god_dellusion| Profile May 8th, 2009 - 3:30 amHi all. really enjoyed this puzzle, didnt sove it but got close (got to 2 balls and knowing if that one is H/L). but i have noticed sometihing while reading abcbcdcdef’s solution – If ‘A’ happens then ‘a’ then ‘I’, and if x:38 balances…u will know that 39 is the defective ball but how would u know if it is H/L?

hex| PUZZLE MASTER | Profile May 8th, 2009 - 9:29 amSuineg’s scans give a 404 error.

I had posted a short message earlier regarding the solution, but it vanished.

I’ll just mention that Frank Cole established a preset solution where he could mentally (without pen and paper) find out which ball was heavier or lighter.

RK| Founder | Profile May 8th, 2009 - 4:04 pmHi there Hex- as the site was getting updated, we lost some images, but it looks like they’re starting to come back online now.

Looked for your message, but it may have gotten lost during the update. sorry about that

RK| Founder | Profile May 8th, 2009 - 7:53 pmOk, Suineg’s scans are back up

Falwan| Profile May 8th, 2009 - 9:44 pmThere isn’t a trick I haven’t used with this one…

With every kind of division for the 39 balls, it seems you need at least 5 TURNS to do it.

Mashplum| PUZZLE MASTER | Profile May 12th, 2009 - 7:12 amSo what’s the verdict on this one?

RK| Founder | Profile May 12th, 2009 - 11:41 pmHi there Mashplum- will have to defer to others on this one; haven’t had the staying power lately to logically follow all the solutions through…

Detective Shadow| Profile June 28th, 2009 - 10:13 pmi just thought that when you can get them to two, by balancing 4 times and keep deviding them in 2 ( when the numbers are uneven just give one side an extra ball, if it is not equal in weight, pick the heavier one..

when you did this 4 times you just weigh them with your hands

=)

suineg| PUZZLE MASTER | Profile July 7th, 2009 - 8:48 pmMashplum I did not see your last comment until today (sorry), this problem can be solved in any scenary given with only 4 weightings hope my scans are useful to make that statement, cool.

sharpcastme| Profile April 19th, 2010 - 5:23 amHi….All…Is it solved yet??

My Solution:

I divide them to 13 balls a group named as A,B & C.

1st Weigh:

First weigh A & B, if they are equal, C is the defective. Let’s proceed with C as defective ball group.

2nd Weigh:

Divide 13 to 6,6 and 1. Weigh 6 balls on a side. If they are equal,,remaining ball is defective. If there is problem in either of 6 balls, will go to next weigh.

3 rd weigh:

We take defective pool and divide 6 balls to 3 on each side and weigh them.

4th Weigh:

We can find the single ball from 3 balls in this category.

Finally we resolved the defective ball..

Hex| PUZZLE MASTER | Profile April 19th, 2010 - 12:33 pmsharpcastme, we don’t know if the defective ball is heavier or lighter than the others. Consequently, in the first weighing, if A is heavier than B, you would know that the defective ball is not in C. But is it in A or in B?

lignjoslav| Profile August 13th, 2010 - 1:43 pmI am not sure if anyone solved it, but the only way to solve this is to always divide into three groups after each measurement, because the scale can give u three different outcomes = balanced, left side heavier, right side heavier. Then u leave one third on the scale, switch one third with the unmeasured ones, and switch the last third from one side to the other (actually u switch two sixths).

So we start with 3 groups of 13, and weigh A and B.

1)unbalanced. We take four from one side and switch them with four from the other. Then we replace 9 of the remaining balls with unmeasured (normal) balls. If the scale goes into balance, its in the 9 that we are not measuring. If it stays the same, it is in the 9 that we haven’t touched. If it reverses, it is in the 8 that we switched.

Now we know in which 9 or 8 the defective ball is, we have two measurements, and we know which could be heavier and which could be lighter (noting from the previous weighings). So each group is 5L and 4H, or 4H and 4L, it is the same for further proceeding. You take 3H and 3L on one side and measure them against six normal balls. If it is lighter, it is one of the 3L. If it is heavier, it is in the 3H. If it is balanced, it is in the remaining three (or two). The end is easy, if u have two, just measure one against a normal to see if it is that one or the other one. If there are 3 left, e.g. two H and one L, u measure one H against the other H. The heavier is defective, otherwise it is the third, unmeasured one.

2)balanced

This is the easier option which tells you that the defective ball is in the unmeasured 13. I suppose there are more ways to do this, but I would take 5 suspicious ones on one side, and 4 suspicious and one normal on the other. 4 suspicious ones remain unmeasured.

*if it is balanced, it is in the four unmeasured balls, and you have two more measurements, so u take two suspicious against one suspicious and one normal. If it is balanced, you it is the fourth one. If not, you know in which three is it e.g. two H and one L, and that is explained before.

*if unbalanced you have two measurements for 9 balls, either 5H and 4 L or the other way around. This procedure is explained under outcome 1).

Hex| PUZZLE MASTER | Profile August 14th, 2010 - 2:36 am@lignjoslav, the solution to this type of puzzles is well known.

Nevertheless, if I followed well your solution, you said:

“Now we know in which 9 or 8 the defective ball is: So each group is 5L and 4H, or 4H and 4L”

In fact, they are: 9L or 9H or 4H and 4L.

lignjoslav| Profile August 14th, 2010 - 10:00 amThat depends how you substitute them. I chose to take 5 from one and 4 from the other. If I took 9 from one I would have 9L or 9H. Your correction makes it more practical, but formally the same.

And as you can see, the solution not that well known…… ))

Hex| PUZZLE MASTER | Profile August 15th, 2010 - 2:36 am@lignjoslav, check out http://www.iwriteiam.nl/Ha12coins.html

Hex| PUZZLE MASTER | Profile August 15th, 2010 - 2:41 am@lignjoslav, it is well known, though maybe not to the average Joe (no offence meant to anybody here).

I tried to post a link to the general solution of this type of problems, but the anti-spam system must have suppressed it.

RK| Founder | Profile August 15th, 2010 - 1:34 pmHey there Hex and lignjoslav,

Released the link from Anti-Spam territory

Thanks

suineg| PUZZLE MASTER | Profile August 15th, 2010 - 9:28 pm@Lignjoslav: Hope my scans help.. I posted long ago the general solution for any given scenary, however I think your solution follow a similar logic.

@Hex: The 12 ball problem is a classic, but the 39 ball case is kind of the same logic but harder I guess, and I did not saw any soltions regarding that particualr case, so I post it, cool man.

Hex| PUZZLE MASTER | Profile August 16th, 2010 - 3:39 am@suineg, check out the link a few posts above and scroll down. It includes the solution for 39 balls/coins problem. I had referred even in an earlier post about Frank Cole who established a preset solution where he could mentally (without pen and paper) find out which ball was heavier or lighter.

If you guessed it on your own, then that’s cool, man (as you always say :-O )

@RK, Thanks for releasing my post from the Anti-Spam monster

Hex| PUZZLE MASTER | Profile August 16th, 2010 - 4:26 amThere is another solution by Martin Gardner. I haven’t really checked it out, but it looks interesting:

Assume that you are allowed W weighings. Write down the 3^W possible length W strings of the symbols ’0′, ’1′, and ’2′. Eliminate the three such strings that consist of only one symbol repeated W times.

For each string, find the first symbol that is different from the symbol preceeding it. Consider that pair of symbols. If that pair is not 01, 12, or 20, cross out that string. In other words, we only allow strings of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).

You will have (3^W-3)/2 strings left. This is how many coins you can handle in W weighings.

Perform W weighings as follows:

* For weighing I, take all the coins that have a 0 in string position I, and weigh them against all the coins that have a 2 in string position I.

* If the side with the 0′s in position I goes down, write down a 0. If the other side goes down, write down a 2. Otherwise, write down a 1.

After the W weighings, you have written down an W symbol string. If your string matches the string on one of the coins, then that is the odd coin, and it is heavy. If none of them match, than change every 2 to a 0 in your string, and every 0 to a 2. You will then have a string that matches one of the coins, and that coin is lighter than the others.

Note that if you only have to identify the odd coin, but don’t have to determine if it is heavy or light, you can handle (3^W-3)/2+1 coins. Label the extra coin with a string of all 1′s, and use the above method.

Note also that you can handle (3^W-3)/2+1 coins if you *do* have to determine whether it is heavy or light, provided you have a single reference coin available, which you know has the correct weight. You do this by labelling the extra coin with a string of all 2s. This results in it being placed on the same side of the scales each time, and in that side of the scales having one more coin than the other each time. So you put the reference coin on the other side of the scales to the “all 2s” coin on each weighing.

Proving that this works is straightforward, once you notice that the method of string construction makes sure that in each position, 1/3 of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a string occurs, then the string obtained by replacing each 0 with a 2 and each 2 with a 0 does not occur.

If you already know the odd coin is heavy (or light), you can handle 3^W coins. Given W weighings, there can only be 3^W possible combinations of balances, left pan heavy, and right pan heavy.

The algorithm in this case:

Divide the coins into three equal groups… A, B, and C. Weigh A against B. If a pan sinks, it contains the heavy coin, otherwise, the heavy coin is in group C. If your group size is 1, you’ve found the coin, otherwise recurse on the group containing the heavy coin.

suineg| PUZZLE MASTER | Profile August 16th, 2010 - 7:00 am@Hex:I give you my puzzle scout word, that I did not find a solution for that case, but I just saw the link, and it shows kind of a solution, but not a detailed one, like the one I give in the scans, the solution that Martin Gardner gives in incredible, he will always be one of the greatest puzzle maker-solver of all time, and I say a lot cool man, but cool.

omkar9630| Profile August 26th, 2010 - 3:39 amIts veeeeeeeery tuff

AdrianCFL| Profile July 11th, 2012 - 1:26 amI’m very bad with maths formulas and stuff like that. So according to what I can think of, this is the simplest solution:

1- separate into 3 groups of 13. Balance group A&B.

2- let’s assume that the odd ball is Lighter in group A. Add a ball from group B.

3- divide group A into 2 groups of 7 (X&Y) and weigh. (If group X is lighter, you can confirm that the odd ball is lighter and in group X (7 balls). If X & Y are equal, the odd ball is confirmed to be heavier and in group Z (6 balls)).

4- Further divide into groups of 3 and weigh. (Keep the extra ball out) Balanced means the extra ball is the odd ball.

5- Then weigh any 2 of the 3 balls and you’ll get your answer!

If A & B were equal, add any one ball from A/B and continue from step 3.

Sorry if I’m late in replying. I just found out about this site not long ago. Hope this explanation is short and clear!