[Guest]

You have nine balls, three of which are slightly heavier, and three of which are slightly lighter than the normal three. All three balls in each group have the same weight. All nine balls are identical otherwise. Your mission is to determine the group of every ball using a pair of scales.

How many weighings are needed in order to ensure the accomplishment of your mission?

Notes:

1. The difference of weight between the heavy and normal balls is not necessarily equal to the difference of weight between the light and normal balls.

2. The scales show only which side is heavier; it does not show the difference of weight.

[Guest]

Then I count 1680 ways to arrange the light/heavy/regular balls. So I'm going to say 7. Don't have a method to go with it yet though.

Edited August 12, 2010 by Tuckleton

[Guest]

a pair of scales? so two scales, one weighing you could measure 4 separate groups?

not necessarily? well are they or aren't they, be more specific, because them being equal in difference drastically changes the problem.

[Guest]

Clarification? It isn't stated, but can you weigh more than one ball per scale at a time? what i mean is...can you put three balls on one side of the scale and three on the other side? or do you have to compare the weight of two balls at the same time, one per each side of the scale? this will make a difference in the number of times that you have to weigh them.

[Guest]

76 Maximum

Scale One - 56 (1 X 8 X 7)

Scale Two - 20 (1 X 5 X 4)

Scale One: you place one ball on the scale leaving 8 possible combinations (8X7). Once solved then that would leave 6 balls.

Scale Two: you place one ball on the scale leaving 5 possible combinations (5X4)

[Guest]

I think the easiest way would be to weigh each ball individually.

Take ball #1 and put it on one side of the scale...weigh each ball against the weight of ball #1. when you have a ball that weighs the same as ball #1, separate it. once you have the two balls that weigh the same, separate ball #1 with those. this will take between 2 and 8 weighings to accomplish.

Next...take one of the leftover balls...say ball #4 and put it on one side of the scale and repeat the process with the remaining balls, separating the balls that weigh the same as ball #4 and put all them in a group. This step will take between 2 and 5 attempts to accomplish.

This will leave ball #1 with it's group and ball #4 with it's group and the three remaining balls will be the third group.

so the largest amount of weighings will be 13 and the fewest will be 4 if you get extremely lucky, but will probably fall somewhere in between.

[Guest]

Quote "Your mission is to determine the group of every ball using a pair of scales."

I think what he means is to determine if a particular ball is in the "Light" group, the "Medium" group, or the "Heavy" Group. I am not sure where these large numbers like 76 are coming from.

please clarify if i am wrong.

[Guest]

The answer is 7

You choose one ball and start to compare that one with the others one by one. You should be able to separate them into three groups based on the weight.

[Guest]

The answer is a maximum of 16 weighings or a minimum of 7 weighings. Let's first start by creating 3 groups of 3 balls each.

FIRST GROUP OF THREE BALLS (8 MAX/2 MIN WEIGHINGS):

Take ONE ball and weigh it against all the other EIGHT balls.

2/8 balls should be equal to the ONE. Therefore in eight at most or two at least weighings you have found 1 group of three balls.

With six balls still unknown from each other.

SECOND/THIRD GROUP OF THREE BALLS (5 MAX/2 MIN WEIGHINGS):

Take ONE ball and weigh it against all the other FIVE balls.

2/5 balls should be equal to the ONE. Therefore in five or less weighings you have found another 2 groups of three balls.

You have now grouped three groups of 3 balls.

GROUP EACH A, B, C.

[1st Group weighing]

Weigh A against B

Let's assume that A is heavier than B. A > B

[2nd Group weighing]

Weigh A against C

Let's assume that A is heavier than C. A > C

It is now conclusive that A is the heaviest group.

[3rd group weighing]

We must now compare B or C to see which is the normal group and which is the lightest group.

AN ADDITIONAL 3 FIXED WEIGHINGS.

THEREFORE A MAXIMUM OF "16" 13 + 3 WEIGHINGS OR

A MINIMUM OF "7 " 4 + 3 WEIGHINGS

Cheers!

Please comment if there are any flaws or mistakes I have made.

Edited August 12, 2010 by j0seph922

[Guest]

I think by "Pair of Scales" he is referring to a balance. In other words, absolute weights can't be determined--just left side vs right side. He didn't say that a light ball plus a heavy ball COULDN'T equal two medium balls, so a heavy and light ball on one side against two medium balls on the other might or might not create balance. One could weigh one pair of balls at a time sorting them as you go, but I'm sure he's looking for a faster approach.

[Guest]

If the order doesn't make any difference then the answer should be 16:

Scale One: 8 + 7 = 15 (This would identify 3 matching balls out of 9)

Scale Two: 5 + 4 = 9 (This would identify 3 matching ball out of the remaining 6)

The remaining 3 would weigh the same.

[Guest]

The answer is a maximum of 16 weighings or a minimum of 7 weighings. Let's first start by creating 3 groups of 3 balls each.

FIRST GROUP OF THREE BALLS (8 MAX/2 MIN WEIGHINGS):

Take ONE ball and weigh it against all the other EIGHT balls.

2/8 balls should be equal to the ONE. Therefore in eight at most or two at least weighings you have found 1 group of three balls.

With six balls still unknown from each other.

SECOND/THIRD GROUP OF THREE BALLS (5 MAX/2 MIN WEIGHINGS):

Take ONE ball and weigh it against all the other FIVE balls.

2/5 balls should be equal to the ONE. Therefore in five or less weighings you have found another 2 groups of three balls.

You have now grouped three groups of 3 balls.

GROUP EACH A, B, C.

[1st Group weighing]

Weigh A against B

Let's assume that A is heavier than B. A > B

[2nd Group weighing]

Weigh A against C

Let's assume that A is heavier than C. A > C

It is now conclusive that A is the heaviest group.

[3rd group weighing]

We must now compare B or C to see which is the normal group and which is the lightest group.

AN ADDITIONAL 3 FIXED WEIGHINGS.

THEREFORE A MAXIMUM OF "16" 13 + 3 WEIGHINGS OR

A MINIMUM OF "7 " 4 + 3 WEIGHINGS

Cheers!

Please comment if there are any flaws or mistakes I have made.

I think your low answer needs to be 1 lower because if A was the medium group then the weighings would be as such

A>B

A<C

then you would know with only 2 weighings.

[Guest]

As was pointed out earlier in the thread, the theoretical minimum is 7 weighings.

It's relatively easy to find a procedure for 10 weighings, a bit harder to find one for 9 weighings but there is a way to do it in maximum 8 weighings. I don't think 7 is possible.

Can anyone else find the 10,9 and 8 solutions?

One thing to note is that any ball can be positively assigned in at most 6 weighings; and in the case of 6 we have assigned 3 balls.

[Guest]

I think 16 is way too high. For starters, you only need at most 7 weighing to find a group of three equal balls (the last one need not be weighed), not 8. I am fairly certain I worked it out with 10, but that still feels very inefficient. I would guess the answer is 7, or perhaps 8 weighings.

The answer is a maximum of 16 weighings or a minimum of 7 weighings. Let's first start by creating 3 groups of 3 balls each.

FIRST GROUP OF THREE BALLS (8 MAX/2 MIN WEIGHINGS):

Take ONE ball and weigh it against all the other EIGHT balls.

2/8 balls should be equal to the ONE. Therefore in eight at most or two at least weighings you have found 1 group of three balls.

With six balls still unknown from each other.

SECOND/THIRD GROUP OF THREE BALLS (5 MAX/2 MIN WEIGHINGS):

Take ONE ball and weigh it against all the other FIVE balls.

2/5 balls should be equal to the ONE. Therefore in five or less weighings you have found another 2 groups of three balls.

You have now grouped three groups of 3 balls.

GROUP EACH A, B, C.

[1st Group weighing]

Weigh A against B

Let's assume that A is heavier than B. A > B

[2nd Group weighing]

Weigh A against C

Let's assume that A is heavier than C. A > C

It is now conclusive that A is the heaviest group.

[3rd group weighing]

We must now compare B or C to see which is the normal group and which is the lightest group.

AN ADDITIONAL 3 FIXED WEIGHINGS.

THEREFORE A MAXIMUM OF "16" 13 + 3 WEIGHINGS OR

A MINIMUM OF "7 " 4 + 3 WEIGHINGS

Cheers!

Please comment if there are any flaws or mistakes I have made.

[Guest]

As was pointed out earlier in the thread, the theoretical minimum is 7 weighings.

It's relatively easy to find a procedure for 10 weighings, a bit harder to find one for 9 weighings but there is a way to do it in maximum 8 weighings. I don't think 7 is possible.

Can anyone else find the 10,9 and 8 solutions?

One thing to note is that any ball can be positively assigned in at most 6 weighings; and in the case of 6 we have assigned 3 balls.

I've been busting my brains out on this puzzle for a while now trying to get it in 7 with no luck. I can't even seem to get it in 8! (Though I can in 9, I think). So I was wondering, does your solution with 8 use more than one ball per side at a time? I haven't really looked at using multiple balls to eliminate the uncertainties in relative weight.

[Guest]

I've been busting my brains out on this puzzle for a while now trying to get it in 7 with no luck. I can't even seem to get it in 8! (Though I can in 9, I think). So I was wondering, does your solution with 8 use more than one ball per side at a time? I haven't really looked at using multiple balls to eliminate the uncertainties in relative weight.

Multiple balls are not good because HL(Higher + Lower) vs. MM (M=medium) could give three posible results depending on the relative weights. So all my strategies involve 1 vs. 1 weighings.

But to get to 8 weighings you do need an adaptive strategy. i.e. choices for later weighings depend on the outcome of earlier weighings.

P.S. I do not have a proof that 7 is impossible.

Edited August 18, 2010 by Hawkeye

[Guest]

11 weighings are required.

First take 1 ball and weigh it with 7 other balls one by one.... No need to weigh last ball.

In max seven weighings you can get a group of 3 balls having weight equal to first ball.

Then out of balance 6 balls, weigh 1 ball with 4 balance balls one by one....No need to weigh last ball

In max 4 weighings u will get 2 groups ( of diff weight ) of 3 balls each .

so total 7+4=11 chances

[Guest]

11 weighings are required.

First take 1 ball and weigh it with 7 other balls one by one.... No need to weigh last ball.

In max seven weighings you can get a group of 3 balls having weight equal to first ball.

Then out of balance 6 balls, weigh 1 ball with 4 balance balls one by one....No need to weigh last ball

In max 4 weighings u will get 2 groups ( of diff weight ) of 3 balls each .

so total 7+4=11 chances

check at

http://www.orkut.co.in/Main#CommMsgs?cmm=50230760&tid=5504059903452500565&na=2&nst=4

as solved by Munna

[Guest]

check at

http://www.orkut.co.in/Main#CommMsgs?cmm=50230760&tid=5504059903452500565&na=2&nst=4

as solved by Munna

Is it correct ?

[Guest]

Finally came up with a working method using only 8. A lot of the things in this solution aren't optimal but I've made it that way for ease of presentation. There are 1680 cases to work through after all!

First, take 8 balls and seperate them into pairs and weigh them against each other. This will take up 4 uses on the scale. Now organize them in the following manner. Put all pairs that were equal weight together. Then orient all inequalities so that the heavier ball is on the left and put them to the right. Finally the ball you didn't weigh goes at the right end. Name the balls 1-9 from left to right.

For example I might get:

A>B C=D E<F G=H I

C=D G=H A>B F>E I (Organized)

1=2 3=4 5>6 7>8 9 (Numbered)

Note: The reason for doing this is because it reduces 1680 cases into 87 cases (Phew! )

There are 4 possible ways this could turn out:

===> (18 cases x 8 permutations)

==>> (12 cases x 24 permutations)

=>>> (21 cases x 32 permutations)

>>>> (36 cases x 16 permutations)

Let's deal with them on an individual basis:

===>

Because we have 3 seperate pairs of weights that are equal, each pair must be a different weight (Since there's only 3 of each). This means that 7,8,9 are all different. We already know 7>8 so by weighing 8vs9 and 7vs9 we can identify all three. Now take the medium one we found and weigh it against 1. The result will identify 1&2. Next weigh the medium one against 3 to identify 3&4. 5&6 are whatever is left.

==>>

Here weigh 5vs7 and 6vs8. Because we've already got 1=2 and 3=4, we cannot get the result 5=7 AND 6=8. Thus we can now identify 5,6,7 and 8.

Example:

5>7,6=8 We already know that 7>8 so 5>7>8 so 5=H, 7=M and 6=8=L

Now pick a medium one (there will always be at least one medium one, ball 7 in the example above) and use it vs 1 then vs 3 to identify 1,2,3 and 4. 9 is whatever is left.

=>>>

There are 3 ways to get a > result. H>M, H>L or M>L. We have 3 > in this result but it isn't possible for all three ways of getting > to be represented because that would give 2 each of H,M and L leaving no way for 1=2 to be true. So either all three >'s are of the same kind, or there is one odd one out. Test 1vs9. If 1=9, then all three >'s must be of the same kind, or in other words, 3=5=7 and 4=6=8. We already know 3>4 so in this case do 1vs3 and 1vs4 to figure out the weights of the 3 groups we've identified.

When 1=/=9 It's a bit more complicated. I'm struggling to find a simple way to do this part and I'm a little impatient so I'll just put down the cases. We have one of the following (The middle 3 pairs are not necessarily in that order):

1>9

a. HH HM ML ML L

b. HH HL ML ML M

c. MM HM HL HL L

1<9

d. MM ML HL HL H

e. LL ML HM HM H

f. LL HL HM HM M

So when 1>9, try 4vs9. If 4<9, then it's b. Do 3vs5 to determine the order. If 4=9, then do 6vs8. If 6=8, then it's b again. Do 3vs5 to determine the order. If 6=/=8 then the heavier of 6 and 8 is Medium. Use it against 1. If = then c. If < then a. In both cases we have all the information we need. Use similar methods for when 1<9.

My apologies that this previous part is not very elegant... but moving on!

>>>>

This one has the most cases but is nevertheless fairly straightforward. Do 1vs3 and 2vs4 if we didn't get 1=3 AND 2=4, we can sort all 4 balls. Next do 5vs7 and 6vs8. Again, if we didn't get 5=7 AND 6=8 we can sort all these balls. It is impossible to get both 1=3 2=4 AND 5=7 6=8 so we are guaranteed to have enough info to sort the rest.

For example:

1=3,2=4 Not much useful info here

5=7,6<8 We know that 7>8 and since 5=7 we get 7>8>6 so 5=7=H, 8=M and 6=L

Since we've got 2 H's already 1 and 3 must be M and 2 and 4 must be L. This leaves 9 with H and we're done.

And that's it! Perhaps a bit overcomplicated but oh well. Please let me know if any of the parts need clarification.

Edited August 20, 2010 by Tuckleton

[Guest]

And to round out my solution:

There are 9C3*6C3=1680 possible ways our 9 balls can be mixed up. We have to start somewhere so pick 2 balls and put them on the scale. Let's say it comes out like this: 1>2. Yay! We've just reduced the number of cases to 3*7C2*5C2=630. Now, we have some choices for the next weighing. We could weigh the same 2 balls again (pointless), we could pick 2 new balls or we could weigh an existing ball vs a new one. Let's look at the latter first. Imagine this was the outcome: 1>3. Uh oh. This is an unfortunate outcome since it doesn't eliminate as many cases as we need. We've still got 2*6C2*4C2+3*6C1*5C2=360 cases left. 5 weighings can only distinguish between 243 so we'd need at least 6 more here. If we had used 2 instead then 2<3 would have had the same problem. So that doesn't work.

Let's look at weighing 2 new balls on the second weighing instead. Say we get 3>4. We're gonna have to go one layer deeper after this so I'll spell out the number of cases to simplify the analysis:

a. HMHM: 5C1*4C1= 20 Cases

b. HMHL: 5C1*4C2=30 Cases

c. HMML: 5C1*4C2=30 Cases

d. HLHM: 5C1*4C2=30 Cases

e. HLHL: 5C1*4C1= 20 Cases

f. HLML: 5C1*4C2=30 Cases

g. MLHM: 5C1*4C2=30 Cases

h. MLHL: 5C1*4C2=30 Cases

i. MLML: 5C1*4C1= 20 Cases

Total: 240 Cases

So 240 is within the realm of possibility but it's gonna be tight. The next weighing needs to bring it down to 81 or less for all results. There are a number of ways the next weighing can go. 1vs3, 1vs4 (equivalent to 2vs3), 2vs4, 1vs5 (equivalent to 2vs5, 3vs5 and 4vs5) and 5vs6. Let's look at one result of each that exceeds 81:

1=3 could be a,b,d,e or i for a total of 120 cases.

1>4 could be a,b,c,d,e,f,h or i for a whopping 210 cases!

2=4 could be a,e,f,h or i for a total of 120 cases.

1>5 could be 16 cases from a, 24 from b, 18 from c, 24 from d, 16 from e,18 from f, 12 from g, 6 from h and 4 from 1. 138 cases total.

5>6 could be 7 cases from each of a, e and i as well as 12 from each of the rest. 93 cases total.

So as long as you are only weighing one ball at a time, you need at least 8. As far as weighing more than one ball at a time, it has been pointed out that it actually adds cases to the original 1680. You'd have to account for the possibilities that H+L > or = or < M+M when using 2 or more balls. Or H+H+L >=< M+M+M >=< H+L+L when using 3 or more. I don't have a proof but I'm sure this would bring the number of initial cases above 2187 making a maximum of 7 weighings theoretically impossible.

[Guest]

Simply put 1 ball on each scalebowl (or whatever they are called). Decide its a waste of time, and measure by lifting them one or two at a time.

Thats one weighting according to my brains.

[Guest]

This is another puzzle you posted from the puzzleup.com competition. I hope you aren't using this site to help you win that race 007.

[Guest]

This is another puzzle you posted from the puzzleup.com competition. I hope you aren't using this site to help you win that race 007.

Ugh, I feel so dirty now. I guess this means I won't be getting a response about my answer anytime soon

[Guest]

Ugh, I feel so dirty now. I guess this means I won't be getting a response about my answer anytime soon

Most likely not. But on the bright side, you can take your solution to that site and maybe earn some points for the competition.

[Guest]

I agree with the general answer-ISH. But don't forget deductions.

I agree with the calculations put forth so far.

Except if we are aiming for the fewest number of trials possible, then I might suggest a minimum of 4 + 2 (if the "normal" is used as part of the first two comparisons) And a maximum of 11.

I am going with 4 and 7 instead of 5 and 8 due to the fact that if the situation were put into action where we would weigh out each ball against the first, we could then, without measuring the last, know it's place among the assortment. This would be true for both the initial sorting (by the time we arrive at the 8th ball, we know where it lies) and the second comparison (the remaining 6 balls).

Also, we would be able to discover through those various trials the corresponding weights of the groups without needing to weigh them again after grouping them into their respective weight categories.

Thus it would take a minimum of 6 to 11 weighings.

Edited September 6, 2010 by Polyna