Balls question

netmaestro · Post by **netmaestro** » Thu Dec 22, 2005 1:15 am

You have 12 billiard balls, all the same size, color and weight except that one ball is a very slight amount heavier or lighter than the other 11. You don't know which. If you have a balance scale to weigh two objects (or groups) against each other, and it costs $1 per use, how much does it cost to identify the odd ball and specify whether it is heavy or light? Warning- this isn't an easy one.

srod · Post by **srod** » Thu Dec 22, 2005 1:37 am

I can determine b) in no more than $4, so I'm searching for a way of getting a) down to $3; not sure if it's possible yet!

Interesting problem.

Joakim Christiansen · Post by **Joakim Christiansen** » Thu Dec 22, 2005 1:42 am

Are you having a such problem netmaestro?

srod · Post by **srod** » Thu Dec 22, 2005 2:04 am

I think I have both down to $3, but it's getting fiddly! Double checking...

*Update: checked and confirmed. Will be very surprised if a) can be done in two uses of the scales.

netmaestro · Post by **netmaestro** » Thu Dec 22, 2005 2:13 am

Three is it. Just post your proof...

srod · Post by **srod** » Thu Dec 22, 2005 2:16 am

I'm trying to write it in pseudo-code, nearly there.

Post by **Dare2** » Thu Dec 22, 2005 2:26 am

I have to spend $5 to isolate the ball (and determine heavier/lighter).

If $5 is it, will provide proof after everyone else has done their thing. Or via PM.

rsts · Post by **rsts** » Thu Dec 22, 2005 2:29 am

I believe weights of 3 balls, 2 balls and 1 ball (against the same number) will do it.

cheers

netmaestro · Post by **netmaestro** » Thu Dec 22, 2005 2:39 am

That won't tell whether it's heavy or light.

srod · Post by **srod** » Thu Dec 22, 2005 2:45 am

It's definitely 3 uses of the scales, but it's a bugger to write out!

I'll keep trying...

srod · Post by **srod** » Thu Dec 22, 2005 2:52 am

Here we go; take a deep breath!

Label the balls; A, B, C, D, E, F, G, H, I, J, K, L

Compare 2 groups of 4 balls. If equal weight, then the misfit is in the remaining foursome, say one of ABCD. Compare ABC with 3 normal balls, e.g. JKL. If equal, then the misfit is D and a 3rd comparison will tell us whether D is under or over weight. If ABC was not equal in weight to JKL then the 2nd comparison tells us whether one of ABC was underweight or overweight. A comparison of A and B then identifies which of A, B or C is the culprit.

This takes care of the case when the original two sets of 4 balls were of equal weight.

Now assume that they were not equal; say ABCD was unequal to EFGH. Assume also (without any loss of generality) that ABCD was of a lesser weight than EFGH.

I need a colour code now; blue for balls which could be under weight, red for balls which might be overweight, and balls which are definitely normal remain black.

Compare ABCEF with DIJKL. If equal weight, then culprit is one of GH, for which one more comparison will do it. Else, if ABCEF was underweight then the culprit is one of ABC. Comparing A and B will do it. Else, (finally) if ABCEF was overweight, then the culprit is either EF or D. Comparing EF will do it.

This accounts for every possibility!

Right, is there a prize?

Post by **Dare2** » Thu Dec 22, 2005 3:16 am

hehe.

My approach was more simplistic. Balls are A to L

1: ABCD -v-EFGH (If this balances we save a buck!)
2: EFGH -v- IJKL
3: ABCD -v- IJKL

Two of three cases the scale tips. Say it went down in steps 1 and 3 on the ABCD side, oddball is in there and heavier. Still works if it goes up in ABCD, but the ball is lighter.

4: AB -v- CD

Whichever side goes down has oddball. Say AB

5: A -v- B

If A goes down, A is it.

Save a buck if step 1 balances. Oddball is in IJKL

2: ABCD -v- IJKL, if IJKL go down, heavier, else lighter

then 4 & 5 with IJKL groups.

So $5 and 1 in 3 times, $4.

netmaestro · Post by **netmaestro** » Thu Dec 22, 2005 3:30 am

Good job, srod. You have it. Not exactly identical to my solution, but yours is just as valid. Excellent work.

rsts · Post by **rsts** » Thu Dec 22, 2005 3:33 am

srod wrote:Here we go; take a deep breath!

Label the balls; A, B, C, D, E, F, G, H, I, J, K, L

I need a colour code now; blue for balls which could be under weight, red for balls which might be overweight, and balls which are definitely normal remain black.

Right, is there a prize?

blue balls, red balls, black balls - but he said they're all the same color

Just kidding

, (I realize the colors were for illustration only) - actually quite an elegant solution.

But coming from me, that might not be a compliment, since I "erred" in my solution by only determining which ball was heavy or light in three tries, but not whether it was heavy or light

Congratulations anyway - looks good to me.

netmaestro · Post by **netmaestro** » Thu Dec 22, 2005 4:21 am

Is there a prize?

Alas, the only prize on offer is "Biggest Cheapskate", which is yours (if you want it!) Again, good work