Question: You are give two red balls, two green balls and two yellow balls. One ball from each color is heavier than the other one. All the heavier balls weigh the same and all the lighter balls weigh the same. You are only provided with a weighing balance. How many tries would it take to identify which one is heavier and which one is lighter?
Answer: Let’s label the balls R1, R2 (Red ones), G1, G2 (Green ones) and Y1, Y2 (Yellow ones).
First weigh R1, G1 on one side and R2, Y1 on the other.
If they are equal, we know that one of G1 or Y1 is heavy. We can just weigh them both and find out which one is heavier. If G1 is heavy, the heavier set is {G1, R2, Y2} and the others are lighter. If Y1 is heavy, the heavier set is {G2, R1, Y1}.
If R1, G1 is heavy, we know that either G1 is heavy or Y1 is light. We proceed to weigh G1, Y1 with G2, Y2. If they are equal, G1 is the heavy one. The heavier set is {G1, Y2, R1}. If G1, Y1 is heavy, G1 and Y1 are both heavy. The heavier set is {Y1, G1, R1}. If G2, Y2 is heavy, G2 and Y2 are both heavy. The heavier set is {R1, G2, Y2}.
If R2, Y1 is heavy, we know that either Y1 is heavy or G1 is light. This is similar to the case above. Try to work it out yourself before continuing with the solution. Weigh G1, Y1 with G2, Y2. If they are equal, Y1 is heavy. The heavier set is {Y1, R2, G2}. If G1, Y1 is heavy, G1 and Y1 are both heavy. The heavier set is {G1, Y1, R2}. If G2, Y2 is heavier, G2 and Y2 are both heavy. The heavier set is {G2, Y2, R2}.
Therefore, in any of these cases, we only need two tries with the balance.
If you like this puzzles, please Digg it or Tweet it to help spread the word.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
The answers provided seems to be right, but the way they have been derived at is definitely wrong. See if this works
Weigh {R1G1, R2Y1}
========================================================
If they are equal, we have only two possibilities
{HL, LH}
{LH, HL}
This says that if G1 is heavy Y1 has to light, and if G1 is light Y1 has to be heavy
Now weigh {G1, Y1}
-> Both can’t be equal
-> If left (G1) is heavy, the solution for the heavy elements is [R2, G1, Y2]
-> If right (Y1) is heavy, the solution for the heavy elements is [R1, G2, Y1]
========================================================
If left (R1G1) is heavy, we have these three possibilities for {R1G1, R2Y1}
{HL, LL}
{HH, LL}
{HH, LH}
This clearly indicates that R1 is heavy and R2 is light. It also indicates that if G1 is light, Y1 has to be light (remember this – 1)
So we should weigh pairing R2 and G1 to deduce the result.
Lets weigh {G1R2, G2Y1}
-> If they are equal, the only possibility is {HL, LH}. So the solution for the heavy elements is [R1, G1, Y1]
-> If left (G1R2) is heavy, the only possibility is {HL, LL}. The solution for the heavy elements is [R1, G1, Y2]
-> If right (G2Y1) is heavy, the only possibility is {LL, HL}. The possibility {LL, HH} doesn’t arise because of (remember this -1). So, the solution is [R1, G2, Y2]
========================================================
The derivation is similar for the third case where {R2Y1} is heavier. You’ll come across a (remember this – 2) indicating that if G1 is heavy, Y1 has to be heavy, which would make you pair {G1R1} and {G2Y1}.
[Left side is heavy ]
From the table above we know that is this happen then R1 will Always be heavy, the problem will be determining the G1 and Y1 balls. when the left is heavy then G1 and Y1 both could be heavy OR one of them could be heavy OR non of them could be heavy 😀 what the..
What the … is wrong with your reasoning?.. 🙂 I adore the 1-0 table above-makes everything easier. Thank you. Now to your problem:
“both could be heavy OR one of them could be heavy OR non of them could be heavy”
You cannot generalize to BOTH here: it’s either BOTH light(correct), OR G1 heavy and Y1=any. This excludes the possibility of the reversal: G1 cannot be light simultaneously with Y1 heavy[it will equalize the weights]. The original solution works.
more simple answer
compare r1,g1 if g1 is heavier that implies g1 and r2 are of same weight.
similarly compare y1 g1 if g1 is heavier then y2 is lighter therefore heavier set is (y1,g1,r2)
let the balls be BLUE: B1 B2
GREEN: G1 G2
RED: R1 R2
FIRST, PUT B1, G1 ON 1 SIDE AND B2 , R1 ON OTHER SIDE
CASE 1:
IF EQUAL, THEN ONE OF G1 OR R1 IS HEAVY AS B1 OR B2 IS HEAVY
SO COMPARE B1 AND B2,
IF B1 IS HEAVY THEN G1 IS LIGHTER
ELSE IF B2 IS HEAVY THEN R1 IS LIGHTER
CASE 2:
IF UNEQUAL THEN ONE OF THE PAN SIDE HAVE ALL TWO BALLS HEAVY
AND THEN REMAINING TWO BALLS CAN BE COMPARE WITH NEXT CHANCE
SO ONLY TWO CHANCE ARE ENOUGH
let hte balls be BLUE: B1 B2
GREEN: G1 G2
RED: R1 R2
FIRST, PUT B1, G1 ON 1 SIDE AND B2 , R1 ON OTHER SIDE
CASE 1:
IF EQUAL, THEN ONE OF G1 OR R1 IS HEAVY AS B1 OR B2 IS HEAVY
SO COMPARE B1 AND B2,
IF B1 IS HEAVY THEN G1 IS LIGHTER
ELSE IF B2 IS HEAVY THEN R1 IS LIGHTER
CASE 2:
IF UNEQUAL THEN ON OF THE PAN SIDE HAVE ALL TWO BALLS HEAVY
AND THEN REMAINING TWO BALLS CAN BE COMPARE WITH NEXT CHANCE
SO ONLY TWO CHANCE ARE ENOUGH
EMAIL : manjeetsinghdighalia@gmail.com
The provided answer is wrong
Nevertheless,
It can be solved in 2 tries
Ball Labels: R1, R2, G1, G2, Y1 and Y2
Higher weight : W
Smaller weight: w
L: Left Pan , R: Right Pan
First Weighing:
L R
R1,G1 G2,Y1
Case 1:
If they are equal
we can only have W+w on either scale
Second weighing:
weigh both green balls
G1 and G2 against each other
This will give you their relative weights.
And with it, the weights of the balls, R1 and
Y1 will be known
If G1 = W then R1 has to be w, & Y1 = W.
If G1 = w then R1 has to be W, & Y1=w.
Case 2:
The left pan is heavier
3 Sub-cases:
L R
R1(W) + G1(W) G2(w) + Y1(w)
R1(W) + G1(W) G2(w) + Y1(W)
R1(w) + G1(W) G2(w) + Y1(w)
The common ball in the heavier pan (green here) has to be the heavier one.
Second weighing:
Weigh R1 against Y2 (and not Y1)
Subcases:
R1=Y2 implies sub-case (i)
R1>Y2 implies sub-case (ii)
R1<Y2 implies sub-case (iii)
Case 3:
This is fundamentally the mirror image of Case 2 and can be solved accordingly.
The solution provided will not work, here is an analytical way to prove it
You have : R1 R2 G1 G2 Y1 Y2
Because we have only two weights ( heavy and light ) then lets assume all light balls weighs zero and heavy balls has the number 1, here are the possibilities.
R1 G1 R2 Y1
1- 0 0 1 0–> Right is heavy
2- 0 0 1 1–> Right is heavy
3- 0 1 1 0–> Equal
4- 0 1 1 1–> Right is heavy
——————————————————————–
5- 1 0 0 0–>Left is heavy
6- 1 0 0 1–>Equal
7- 1 1 0 0–>Left is heavy
8- 1 1 0 1–>Left is heavy
——————————————————————–
[ Both sides are equal ]
if both sides are equal then we have two possiblities ( rows 3 and 6 )
if it is case 3 then:
R1 != G1 !=Y1 AND G1 = R2
and if case 6 then:
R1 != G1 != Y1 AND G1 = R2
Actualy they are the same equation ( this is logic because to achieve the equality , knowing that R1 and R2 are different
and that we put them two different sides , then G1 should not equal Y1, one of them
is heavier and the other is lighter, AND if R1 is heavy G1 will not and vice versa.
To solve this equation we need to know only that one ball is heavy
then we will know the rest, you can know the heavy ball by comparing any two similar balls ( because you should make sure
that one of them is heavier than the other , you don’t want to compare two balls that may be equal to each other !! )
so compare R1,R2 OR G1,G2 OR Y1,Y2 , then apply the equation above.
—————————————————————————————————-
[ One of the sides is heavy than the other ]
[Left side is heavy ]
From the table above we know that is this happen then R1 will Always be heavy, the problem will be determining the G1 and Y1 balls. when the left is heavy then G1 and Y1 both could be heavy OR one of them could be heavy OR non of them could be heavy 😀 what the..
so we can’t conclude an equation of this , every thing is possible, so lets try to use the ONLY information we have
which is R1 is heavy, hmmm !!, it seems that we still need two more tries to weight!!.
before using the R1 , lets try to compare G balls and Y balls with each others and see where
this will end :
G1 G2 Y1 Y2
0 1 0 1 –> equal
0 1 1 0 –> equal
1 0 0 1 –> equal
1 0 1 0 –> equal
no benifit from doing that , each pair of balls are on different sides !! , bad move huh!
ok try this
G1 Y1 G2 Y2
0 1 1 0 –> equal
1 0 0 1 –> equal
0 0 1 1 –> Right is heavy
1 1 0 0 –> Left is heavy
If one of the sides is heavy, then we know that both of balls in the heavy side are heavy , that is cool , BUT if they are equal we have two cases !!!!
we will need a third trial !! , It seems it is not solvable.
so we should go back and use the R1 in our test. but how ? , R1 is heavy , using that we should get two information in the same time about G and Y, because we ONLY
have one more trial , we can compare R1 (which is heavy ) with Y1 or G1 , if they are equal then the second ball is heavy too as R1, but comparing with one ball will not give us any information about the other ball. ( ex R1 vs G1 will make us know if G1 is heavy or light
but we will not know about Y ) so Y should be in the equation.
if you know how to solve this email me :).
In first step: If R1, G1 is heavy we only know that R1 is heavy and that G1 is heavier or equal to Y1…