Unsolvable Ball Weights Problem: Help Needed with 4 Balls and Scales

[haiha]

My friend asks me this problem, and i fail. It seems unsolvable. Can anyone help

You have to use the scales 3 times to identify 4 balls which look identical but with different weights: 1; 2; 3 and 4kg each.

Thanks.

 

[robert Ihnot]

Why not put #1 on one side and then in series do 2,3,4. If there is one case of irregularity then it is a case from the set 2,3,4, as seen at the time. If there is always irregularity, then it is #1.

 

[ice109]

putting a couple weights together allows you to figure it out, i don't want to figure out exactly how though

 

[haiha]

Why not put #1 on one side and then in series do 2,3,4. If there is one case of irregularity then it is a case from the set 2,3,4, as seen at the time. If there is always irregularity, then it is #1.

You can not do like that because you do not know which is which. Let say you put the 1kg on one scale, it takes 3 times and all other pounders will be heavier, but you do not know which one is 2, 3 or 4kg ball.

 

[ice109]

First use: put two balls on each side

this gives you three cases

4+3 vs 2+1 or 4+2 vs 3+1 or 4+1 vs 3+2
if they're unequal the heavier side has the 4.

Second Use:

switch two balls, if the heavier side stays heavier you know you switched the 3 and the 2 and you'll know the side that stayed heavier contains the 4, the other side contains the 1 and for the third use you can differentiate between the 3 and 2. if they become equal you know you switched the 1 and 2 or 3 but you know which one is the 4 and which one is the 1 so for the 3 try compare the 2 and the 3.

if they're equal to begin with

then switch two balls. whichever side is heavier has the 4 and the other side has the 1. take the ball you put on the heavier side off. if it becomes lighter the left over is a 2 you took off the 4 and it was a 3 there before. if it stays heavier it's the 4 and you took off the 3 and it was a 1 there before. if becomes even again you took off the 4 and its a 3 there and it was a 2 before.

 

[haiha]

First use: put two balls on each side

.
if they're equal to begin with

then switch two balls. whichever side is heavier has the 4 and the other side has the 1. take the ball you put on the heavier side off. if it becomes lighter the left over is a 2 you took off the 4 and it was a 3 there before. if it stays heavier it's the 4 and you took off the 3 and it was a 1 there before. if becomes even again you took off the 4 and its a 3 there and it was a 2 before.

Thank for your reply.
Anyway, there's one thing I am not so sure. There exist two unvailed situations :If you take off the 4 (from the left, the heavier), then there can be an equality : 3=2+1, and if you take off the 2, there can be another equality 4=3+1. Then you can not decide when the ball on the left equals the 2 on the right.

 

[ice109]

man... i thought i had that one taken care of but i don't

 

[CRGreathouse]

From an information standpoint, there are 4*3*2*1 = 24 possible cases and each comparison gives, at most, lg 3 bits of information. The best possible first move then reduces the number of cases to 8 (if there are equal numbers of possibilities for the left being heavier, the right being heavier, and the two being the same). Thus putting two balls on either side of the scale is an information-optimal first move since it does reduce the number of cases to 8 for any of the possible arrangements.

Weighing two balls on each side: If the two sides are equal then one side has the 4 and the 1 and the other has the 3 and the 2, but we don't know which side has which. If the sides are unequal than the heavier side has the 4 and the lighter side has the 1, but the other two could be on either side.

Now any next move that let's you determine all cases must split three cases left, three cases right, and two for the tie. (Otherwise the final move will have more than 3 cases for some arrangement.)

 

[matt grime]

It strikes me as lots of cases, but eminently doable.

Weigh

ab v cd

ac v bd

Let L, R , B mean left heavy, Right, heavy, balance resp.

If you get L, L heavier a=4, d=1, weigh off b,c

If you get R, R heavier a=1 d=4 weigh off b,c

L, then B a=4, c=1, weigh off b,d
R,B is dual d=4, b=1 weigh off a,c

B then L and B then R are similar.

This leaves L,R (and R,L is again dual). But here you must have swapped over 1,4 L,R means b=4 c=1 weigh off a,d to finish

I thnk that is all cases.

 

[ice109]

huh @ above?

is this doable in 3 weighs? does anyone know if there is a solution?

 

[CRGreathouse]

huh @ above?

is this doable in 3 weighs? does anyone know if there is a solution?

Did you read matt's post?

 

[haiha]

Hi Matt,

I still can not get your idea in the last case (too bad isn't it):

" B then L and B then R are similar.
This leaves L,R (and R,L is again dual). But here you must have swapped over 1,4 L,R means b=4 c=1 weigh off a,d to finish"

I also have thought of this but can not distinguish the 2 and 3 balls. You may swap over 1,4 or 3,2 and you did not know.

 

[ice109]

Did you read matt's post?

i can't decypher it

 

[D H]

i can't decypher it

Matt is labeling the balls a,b,c,d and then performing two of the weighings right off the bat: a+b versus c+d and a+c versus b+d. Each weighing has one of three outcomes: L=left side heavy, B=balanced. or R=right side heavy. With two weighings, three outcomes each, there are nine cases to consider: LL, LB, LR, BL, BB, BR, RL, RB, RR. Matt addressed eight of these, sometimes mapping masses to labels immediately and other times mapping to labels after one more weighing.

What about the ninth case? The one case Matt didn't cover is BB. This is obviously impossible given the masses of the balls.

 

[Moo Of Doom]

Using matt's notation, I don't see how he got a=4, c=1 from L, B. Wouldn't b=4, d=1 be just as logical? This is the case I am stuck on.

 

[D H]

Using matt's notation, I don't see how he got a=4, c=1 from L, B. Wouldn't b=4, d=1 be just as logical? This is the case I am stuck on.

Right. You know that the 1 and 4 are together in the second weighing, but you don't know which side. After looking at this for a bit, Matt's scheme fails when either weighing results in a balance. Back to the drawing board.

 

[D H]

This time for sure!

Label the four balls a,b,c,d.
Weigh ball a versus ball b, the heavier of a,b versus c. Since there are no duplicate weights, a strict ordering on balls a,b,c can be assigned. Relabel balls a,b,c as A,B,C in increasing weight order. Now weigh balls A and C versus B and d. There are three possible outcomes:

• A+C<B+d: A=1, B=2, C=3, d=4
• A+C=B+d: A=1, B=2, C=4, d=3
• A+C>B+d: A=2, B=3, C=4, d=1

 

[haiha]

Hi DH, I disagree when you say "..a strict ordering on balls a,b,c can be assigned". Say a>b, then you weigh a versus c, and a>c, but you do not know b>c or c>b.

 

[D H]

Right. Back to the drawing board once again.

I should never have started with a Bullwinkle line. To quote Rocky, "That trick never works".

 

[NateTG]

It's possible in 3.

Spoiler

Start by weighing
ab-cd
ac-bd

It's impossible for both to balance since the only pairings that balance are 2-3/1-4.

If one of the two weighings balances, then weighing the two balls that were heavy will give you the information that you need in order to identify all of the balls. (Clearly the two heavy balls are 3 and 4, and they must have been paired with 2 and 1 respectively to balance.)

If neither weighing balances, then you know that the ball that was heavy both times is 4, and the ball that was light both times is 1. Thus, weighing the other two balls will identify balls 2 and 3.
[/color]

 

[D H]

Nate, This is Matt's solution. It doesn't work. This is not true:

Clearly the two heavy balls are 3 and 4

The 4 can also be paired with the 2 for the non-balanced weighing.

 

[D H]

I'm starting to think its a trick question.

Put a ball on the scale, read its weight, and label the ball with its weight. Do the same with two other balls. The weight of the fourth ball can be inferred from the weights of the other three balls.[/color]

 

[D H]

It can't if the other weighing balances. If you start with:
4-2 1-3

There's no way to swap two balls and have it balance.

Swap the 2 and the 1.

 

[NateTG]

Swap the 2 and the 1.

Yeah, I saw that right after I posted -sorry. Didn't mean to delete out from under you.

 

[D H]

The OP never said it was a set of balance scales. We just collectively assumed this was the case. Highlight post #22.

 

[NateTG]

It's impossible:

Clearly the maximal number of possibilities that can be identified by n weighings is 3^n. Therefore, the best we can do is 27 with 3 weighings, 9 with 2 weighings, and 3 with one weighing.

Thus, if the first weighing cannot balance, it must have the possibility of leaving a branch with at least 12 possibilities, and two weighings left. Therefore, any winning strategy must have an initial weighing that can balance.
Up to equivalence, this leaves two possibilities for the initial weighing:
ab-cd
and
ab-c

If the first weighing is ab>c, this leaves 18 possibilities, which is too many.

So a winning strategy must start with ab-bc (or it's equivalent).
Thus, a winning strategy must be able to handle the ab=cd case. But since there are eight possibilities, the next weighing must also potentially balance. All choices are equivalent to:
a-bc
But the a<bc case admits 4 possibilities which is too many for the last weighing to distinguish.

Therefore, following D_H:
Weigh three of the balls. By elimination, identify the fourth ball.