One of the most classic puzzles involving balls is figuring out the odd one out using common balance.There are many levels of puzzles based on the same concept for different levels of interviews - Simple ones for phone interviews to the most gruelling 1 hour hard work needing hard ones.
Problem space
The general problem is you will be given n balls and one of them is either heavier or lighter and you are asked to find out the minimum number of weighings using a common balance required to find out the odd one out.
Example 1:8 Balls,Odd ball being heavier
This is the simplest question among the lot and is often used during phone screenings.The question is to find out the minimum number of weighings required to spot the odd heavier ball among 8 identically looking balls using a common balance.Answer is 2 and the solution is given in the next paragraph.
For simplicity let us name the balls as A1,A2,A3,B1,B2,B3,C1 and C2.We weigh with A's on one side and B's on the other side of the balance.If both sides are equal this means the heavier odd ball is among C1 and C2.We can figure out the heavier ball with one more weighing.If A's are heavier than B's then the heavier odd ball is among A's.Now we balance A1 and A2.If both are same then A3 is the odd ball or else the heavier one of A1 and A2 .Thus, we can find out the heavier ball using only 2 weighings.
Example 2:8 Balls,Odd ball can be either heavier or lighter than the rest.
This is a little trickier to solve.Let us name the 8 balls as A1,A2,A3,B1,B2,B3,C1 and C2.Now weigh with A1,A2,A3 on one side and B1,B2,B3 on the other side.If both weigh equal then the odd ball is among C1 and C2.Now we know that A's and B's are all normal ones we can weigh C1 with A1 and check whether C1 weighs the same as the normal ball.In this way, we can figure out in one weigh which of C1 and C2 is odd.Now if A's weighed more than B's then we know for sure C's are normal ones.Now lets assume A's heavier than B's and we still don't know whether the odd is among A's or B's.
We know
A1 A2 A3 < B1 B2 B3
Now we compare
A1 B2 B3 to B1 C1 C2 .
Now if the A1 B2 B3 is heavier than B1 C1 C2 Then it means the odd ball is among A1 and B1.If A1 B2 B3 is lighter than B1 C1 C2 then the odd ball is among B2 and B3.If A1 B2 B3 equal to B1 C1 C2 then odd ball is among A2 and A3.So we have zeroed down to 2 balls.Now its very easy as we can compare any of the normal ball with one of the 2 balls.So answer is 3,ie in 3 weighings we can find out the odd ball.
Problem
You are given 13 balls.The odd ball may be either heavier or lighter.Find out the odd ball in 3 weightings.(There is an equally difficult smaller version of the puzzle involving 12 balls also but because both require the same solution technique i am leaving that problem) Hint: I have already given the hint for this question.This mammoth looking task only requires the techniques already discussed in the page.If you have not read all the steps mentioned above i request you to please go through the above solutions carefully.
Solution will be posted soon ....
Pls post your solution as comment ...
Waiting for a trickier smarter solution ....
108 comments:
Split your balls into 3 groups of 4 and a spare.
Take group A + B (4 balls each) and weigh them against each other.
If they weigh differently: throw out the lighter set and weigh 2 against 2 from the smaller set. Again throw out the lighter set and weigh one and one revealing the heavier ball.
If they weigh the same: take set C and split it 2+2 and weigh. If those are the same than the last ball is the one you're looking for. If the 2+2 weigh different than take the heavier pair and weigh. This should reveal the heavier ball.
SPOILER??????????????
Adam's method seems to break down if the odd ball is lighter. Do you have to know whether the oddball is heavy/light? If not, balance 4-4, 5 leftover. If they're different do HLLvHLL and then HvH if they're equal or LvL if they're not. If the 4-4 was equal, we have five unknowns. Balance 3 unknowns against 3 regulars. If those are also equal, do an unknown against a regular. If that is equal, your final unknown is the oddball, but I can't say whether it's heavy or light.
Split the balls in 4 sets:
Set A: {A1 A2 A3 A4}
Set B: {B1 B2 B3 B4}
Set C: {C1 C2 C3 C4}
Set D: {D1}
Weigh A against B:
Case 1: A goes up and B goes down
________Weigh Set Odd: {A1 A2 A3 B1 B2} against C + D : {C1 C2 C3 C4 D1}
________Case 1: Odd goes up
________________Weigh A1 against A2
________________Case 1: A1 goes up
________________________A1 is odd
________________Case 2: A2 goes up
________________________A2 is odd
________________Case 3: balanced
________________________A3 is odd
________Case 2: Odd goes down
________________Weigh B1 against B2
________________Case 1: B1 goes down
________________________B1 is odd
________________Case 2: B2 goes down
________________________B2 is odd
________Case 3: balanced
________________Weigh B3 and B4
________________Case 1: B3 goes down
________________________B3 is odd
________________Case 2: B4 goes down
________________________B4 is odd
________________Case 3: balanced
________________________A4 is odd
Case 2: A goes up and B goes down
________Solution will mirror Case 1
Case 3: balanced
________Trivial (hint: weigh {C1 C2 C3} against {A1 A2 A3})
It involves swapping balls... the solution for the 12 balls / 1 odd / 3 weighings problem using swapping also determines details about the odd: lighter or heavier. In the 13 balls / 1 odd / 3 weighings problem isn’t always possible to determine details about the odd.
x1 x2 x3 x4 vs y1 y2 y3 y4 and 0 0 0 0 0
x1 y2 x2 vs y1 x3 0 (note the swap)
* you figure out the third
- or -
0 0 0 0 vs 0 0 0 0 and x1 x2 x3 x4 x5
x1 x2 vs x3 0
x1 0 vs x2 0 (or sub-cases)
The solution is not too trivial. You have to keep in mind which is heavier and which is lighter:
Split the 13 into groups of 4,4 and 5. call them oooo, oooo, ABCDE
1a: compare the two 4-ball groups oooo-oooo [1st comparison]
if they are = then you know that the 'o' balls are normal. goto step 1b...
if they are NOT = then you have ABCD EFGH ooooo (call the heavier group 'ABCD' and the lighter one 'EFGH') goto step 2a...
1b: AB - Co [2nd comparison]
if they are = then goto step 1d...
if AB > Co , then you know 'A or B' is a heavier ball, goto step 1c...
if AB < Co , then you know 'A or B' is a lighter ball, goto step 1c...
1c: A - B [3rd comparison]
if they are = C is The ball. Done.
if A > B, A is The Ball if a|b were heavier in step 1b. otherwise B is the ball. Done
if B > A, B is the Ball if a|b were heavier in step 1b. otherwise A is the ball. Done.
1d: D - o [3rd comparison]
if they are = E is The ball, otherwise D is The ball. Done.
2a: ABF - CDE [2nd comparison] (where A,B, C and D came from a 'heavier' group, with F and E from a lighter group)
if =, take GH and go to step 3a, Checking for the lighter one.
if ABF > CDE, that means 'A or B' are heavy or E is light (A,B, E unknown) goto 3b...
if ABF < CDE, that means 'C or D' are heavy or F is light (rename them to A,B and E now) goto 3b...
3a: G - o [3rd comparison]
if they are = The ball is H. Done.
Otherwise The ball is G. Done.
3b: A - B [3rd comparison]
if they are = The ball is E. Done.
otherwise Whichever the heavier one is, IS The ball. Done.
Given that this is more than likely an interview question for a developer or engineer, I can help but think what this allows me to conclude? Yes, he's a logical thinker and such, but aren't managing time and complexity of much more importance?
Jim
RunFatBoy - Exercise for the rest of us.
ok 13 balls is really really easy
first you have 5 v 5 v 3 groups of balls.
Weigh 5 v 5. If it is 5v5, then weigh 2 v2, then weigh 1 v 1.
If it is 3, then weigh 1 v 1, then you have it.
Simple, you guys are retarded if you cannot figure this out. Next question.
Mike, your solution doesn't work. You assume the ball is heavy, whereas we don't know if it is heavy or light. Several of your paths find 'the ball' without ever weighing it, so you can't possibly know whether it is heavy or light. hammydude12345 makes the same mistake.
I don't think the problem can be solved for 13 balls as stated. It can be solved for 13 balls if either
a) we know that the ball is heavy, or
b) we are given an extra neutral ball to play with (i.e. 14 balls - one known good one)
In general, for any number of weighings, we can cope with one more ball if given a neutral ball. Consider 1 weighing - We can't determine anything without a known neutral ball, but with a known ball we can cope with one unknown, and identify it as light or heavy. With 2 weighings we can cope with 3 balls, or 4 if given a known good one. With 3 weighings I reckon 12 balls is the maximum possible unless given a known neutral ball extra, in with case we can cope with 13.
manish, your solution fails in your 'trivial' case, where C1 C2 C3 balance A1 A2 A3. This leaves you with 2 balls (C4 D1) which you can't distinguish in one weighing and determine light/heavy.
Actually Paul, it does work.
I do not assume it's heavy. My solution is based on the fact that you do not know which is which, but remember which it is after your first comparison.
I specifically said that after you measure it, you call the 'heavy' group a distinct name, so you know which group is 'heavy' and which is 'light': "(call the heavier group 'ABCD' and the lighter one 'EFGH') goto step 2a..."
Retarded? But you're "solution" doesn't take into account heavier/lighter. It only works if you make an assumtion on whether the odd ball is heavier or lighter. Is the retarded comment really necessary, especially since your wrong?
/me agrees with paul. I solved the 12 ball once, but I have never seen 13 ball solved without the 14th neutral ball.
I don't think it works with 13 balls. Here is what I think the flaw in your logic is:
At the start of step 1b, you know that the odd ball is in ABCDE, but you don't know if the odd ball is heavy or light. If at step 1b AB = Co, then you know that either D or E is either heavy or light (you have weighed neither of them so you can't say anything about them). Now for the third weighing, suppose step 1d is D = o. If so, then E is the odd ball,
but since we've never included it in any weighing, we cannot say for sure if it's light or heavy.
I hope that makes sense (and is correct...)
Which step in my solution do you disagree with?
after the first measuring, you know it's either one of the 5-ball set ones, which is easy to do...
otherwise you have a 4v4, and you see which set of 4 is heavier and which is lighter, so you use that knowledge - intermixing them according to the logic and assuming that one of those 4 is heavy OR one of the other 4 is light.
my solution is virtually pseudocode to solve this puzzle, though i guess i should have been more clear in my naming conventions so it's easier to follow.
Tommy, you are correct that we didn't included it in any of the weighing, but you just verified my logic in that we have the oddball! Granted, it's true we don't know if it's heavy or light as in some of the other cases, we now know WHICH it is, and I think that is the actual goal of the puzzle.
reading the problem description at the top:
The general problem is you will be given n balls and one of them is either heavier or lighter and you are asked to find out the minimum number of weighings using a common balance required to find out the odd one out.
notice it doesn't say find out if it's heavy or light, it just asks you to find the odd one out.
Label 13 as follows...
a1, a2, a3, a4, a5
b1, b2, b3, b4, b5
c1, c2
d1
Weigh as follows...
a1..a5 <> b1..b5 ?
> : a1+a2 <> a3+a4 ?
> : a1 <> a2 ?
> : a1
< : a2
< : a3 <> a4 ?
> : a3
< : a4
= : a5
< : b1+b2 <> b3+b4 ?
> : b1 <> b2 ?
> : b1
< : b2
< : b3 <> b4 ?
> : b3
< : b4
= : b5
= : c1 <> c2 ?
> : c1
< : c2
= : d1
Is it not that simple?
Mike,
I think there is at least one flaw in steb 1b. You wrote
1b: AB - Co [2nd comparison]
if they are = then goto step 1d...
if AB > Co , then you know 'A or B' is a heavier ball, goto step 1c...
if AB < Co , then you know 'A or B' is a lighter ball, goto step 1c...
However,
if AB < Co ,then you DON'T know 'A of B' is a heavier ball. They may be the same weight and C may be the lighter ball.
Go out, have a beer, meet people.
No Dave, it's not that simple. Because you do not know if it's heavy or light. You assume it's heavy :)
Going with your first comparison of > : a1+a2.. assumes it's in the heavy side off the bat. Can't do that.
(with indenting!)
Label 13 as follows...
a1, a2, a3, a4, a5
b1, b2, b3, b4, b5
c1, c2
d1
Weigh as follows...
a1..a5 <> b1..b5 ?
__> : a1..a2 <> a3..a4 ?
______> : a1 <> a2 ?
__________> : a1
__________< : a2
______< : a3 <> a4 ?
__________> : a3
__________< : a4
______= : a5
__< : b1..b2 <> b3..b4 ?
______> : b1 <> b2 ?
__________> : b1
__________< : b2
______< : b3 <> b4 ?
__________> : b3
__________< : b4
______= : b5
__= : c1 <> c2 ?
______> : c1
______< : c2
______= : d1
Wish my interviews were that easy!
Mike,
I have to agree with your reading of the question. Relaxing the requirement to determine heavy or light does indeed make 13 balls possible - I was focussed on the complete identification problem, which is indeed not specifically asked for (but more interesting :-) )
Paul , what do you mean you disagree with reading of the question?!
The question explicitly does NOT ask you to find the heavy or light. IFF that IS the question then you are correct, my solution fails.
However my solution works to specifically find the Odd ball based on the question "As Posted".
darren -- reread what i wrote.
"if AB < Co , then you know 'A or B' is a lighter ball." obviously C can't be the 'lighter' ball. whatcha smokin?! Co weighs more in this case.
Got my signs wrong but my point still holds
However,
if AB > Co ,then you DON'T know 'A of B' is a heavier ball. They may be the same weight and C may be the lighter ball.
David,
Your solution would fail if b1-b5 contained a lighter ball.
Actually the insulting hammydude had it correct. We are only allowed to weigh 3 times.
Groups are 5 5 and 3.
Weigh the 5 and 5. If they are equal then the odd ball has to be in the group of 3. It is a simple matter to take one ball out of the group of 3 and weigh 2 of them. If they are equal, the one you did not weigh is the heavy one and you have accomplished your task in 2 attempts.
If they are not equal you are left with the heavy ball in one of the groups of 5. Once again remove 1 ball from the group that you know to be heavier. Weigh the group of 2 and 2. If they are equal you know the one you have withheld is your heavy ball and you have accomplished your task with 2 attempts.
You only need the third attempt if your division of the group of five results in an imbalance in the 2 and 2 division. Once you establish which 2 vs 2 group is heavier the 1 vs 1 split of that group finds the heavy ball on the 3rd attempt.
> "Given that this is more than likely an interview question for a developer or engineer, I can help but think what this allows me to conclude? Yes, he's a logical thinker and such, but aren't managing time and complexity of much more importance?
Jim"
Jim,
I think the elegance of the solution is very important. It's part of managing complexity, performance, maintainability, etc (simplicity is part of elegance).
e.g. If you have a solution that scales logarithmically instead of linearly, that means a lot for scalability, hardware costs, etc.
Also whether the solution is durable, because in most systems maintenance and support are the biggest costs.
David,
Read the question:
"The odd ball may be either heavier or lighter"
Therefore, to assume a heavier ball in your solution is wrong.
darren,
did you go to step 1c after mike's step 1b. the case you are talking about it resolved there.
Split the balls into:
Set A: {A1 A2 A3 A4}
Set B: {B1 B2 B3 B4}
Set C: {C1 C2 C3 C4}
Set D: {D1}
1st weigh:
Set A vs Set B
If A == B Then
2nd weigh:
C1C2 vs D1A1 (A1 we know is not it)
If (C1C2 == D1A1) Then
3rd weigh:
C3 vs A1
If (C3 == A1) Then
Odd = C4
ElseIf (C3 <> A1) Then
Odd = C3
If (C1C2 < D1A1) Then
3rd weigh:
C1D1 vs A1A2
If (C1D1 == A1A2) Then
Odd = C2
If (C1D1 < A1A2) Then
Odd = C1 (only C1 or C2 could be lighter)
ElseIf (C1D1 > A1A2) Then
Odd = D1 (only D1 could be heavier)
Else A < B Then
2nd weigh:
A1A2A3 vs A4B1B2
3rd weigh:
A1B1B3 vs A2A4B4
If (A1A2A3 < A4B1B2 AND A1B2B3 < A2A4B4) Then
Odd = A1
If (A1A2A3 < A4B1B2 AND A1B2B3 > A2A4B4) Then
Odd = A2
If (A1A2A3 < A4B1B2 AND A1B2B3 == A2A4B4) Then
Odd = A3
If (A1A2A3 > A4B1B2 AND A1B2B3 > A2A4B4) Then
Odd = A4
If (A1A2A3 > A4B1B2 AND A1B2B3 < A2A4B4) Then
Odd = B1
If (A1A2A3 > A4B1B2 AND A1B2B3 == A2A4B4) Then
Odd = B2
If (A1A2A3 == A4B1B2 AND A1B2B3 < A2A4B4) Then
Odd = B3
If (A1A2A3 == A4B1B2 AND A1B2B3 > A2A4B4) Then
Odd = B4
Else A > B Then
Similar to previous
Get a bucket of water and which ever one sinks, thats the Odd one out. Geez, that was pretty easy.
imram.... How in the hell are you to assume that only one ball is bouyant or not?
The solution is simple for any # O. Split the n balls into 3 groups of O/3, or as close as possible (at least two of the groups will have the same # of balls). Put the two groups that have the same number onto the scale, and if either one is heavier or lighter (depending if the extra ball is heavier or lighter) that one contains the odd ball out. If not, the group you set aside contains it. Repeat this process with the group that contains the odd ball out until only one ball remains. For any # (O) balls, the number of steps is log3(O).
@darren
heavier and lighter in this instance are interchangeable. That the scale will show they are unequal is what matters.
Yes I should have said heavier or lighter. Mea culpa, mea maxima culpa.
Oops, didn't notice that the defect of the ball was not mentioned.
To fix my last solution, if the first time that one of the weighed sides is heavier you compare the odd group out with the one of the ones on the scale, you can determine if the odd ball is heavier or lighter, and then proceed as normal. This would only add one weigh to the set, leaving log3(n)+1 steps for any #n.
If the scale shows they are unequal. Then how do you deduce that the odd ball is in the set of A and B? It can still be ball C.
@darren
Thank you I misunderstood your issue with my explanation and of course now that I revisit it I am obviously incorrect.
I have always heard this problem knowing in advance whether the odd ball is heavier or lighter.
ok so I figured out the three weighs bit, but my question is, How in the name of all that is holy are you supposed to know this stuff without being given examples before hand? I am assuming that you either have to be really smart or you're just out of luck. Am I right?
Ryan,
It may be that one of the balls is heavier because it is slightly bigger. It may therefore have the same density as the other balls and float at the same point.
Not sure if this is the same as someone else's solution, but I feel like mine is easier to understand (of course haha). Note that _(n)_ represents the nth weighing. Also note that in the last half, < can be interchanged with > (and lighter with heaver where appropriate):
Split up as a1, a2, a3, a4, b1, b2, b3, b4, c1, c2, c3, c4, c5
First weigh a1, a2, a3, a4 _1_ b1, b2, b3, b4
If they are =,
Weigh c1, c2, c3 _2_ b1, b2, b3
If they are =,
Weigh c4 _3_ b1
If different, odd man is c4
Else odd man is c5.
Else if c’s are lighter (heavier)
Weigh c1 _3_ c2
If =, odd man is c3
Else if c1 is lighter (heaver),
odd man is c1
Else odd man is c2.
Else say a’s < b’s (c’s are all normal)
Weigh a1, b1, b2, b3 _2_ b4, c1, c2, c3
If a1, b1, b2, b3 < b4, c1, c2, c3, then
either a1 is lighter or b4 is heaver.
Weigh a1 _3_ c1
If =, b4 is odd man
Else a1 is odd man.
Else if a1, b1, b2, b3 = b4, c1, c2, c3, then
we know one of the a’s is lighter.
Weigh a2 _3_ a3
If =, odd man is a4
Else if a2 is lighter, odd man is a2
Else a3.
Else a1, b1, b2, b3 > b4, c1, c2, c3, then we
know that one of the b’s is heaver.
Weigh b1_3_b2
If =, odd man is b3
Else if b1 heaver, odd man is b1.
Else odd man is b2.
Feel free to respond that I am wrong and please provide justification. Thanks!
Alisa - I believe we don't know in advance whether the odd ball is heavier or lighter.
Recursive algorithm would be
Given n balls, put n/2 balls in group A and the rest in group B
#A, #B refers to weight of balls in group A, and group B, respectively
!= is opposite of =, so not equal to
FindOddOne(group A, group B){
if #B = #A
.return A
if #B = 0 or #A = 0
.return ( A union B )
if #A != #B
.C = findOddOne( A[0,length(A)/2],
A[length(A)/2, length(A)])
.if( length(C) = 1 )
..return C
..if( length(C) = length(A) or
length(C) = length(B) )
...C =
findOddOne( B[0,length(B)/2],
B[length(B)/2, length(B) )
.return C
}
The algorithm returns the odd ball and when there is no odd ball, it will return just any ball
Balls labelled a-m.
1. Measure abcd vs efgh.
If equal, 2. ief vs jkl.
If equal, 13 is odd.
If unequal, then 3. ij vs fk. use comparisons between ief-jkl and ij-fk to tell which of ijkl is odd.
If first weighing is unequal (suppose abcd greater efgh):
2. aeij vs bcfg
If equal, d or h is odd
If aeij greater bcfg, then a,f, or g is odd. Weigh 3. af vs gj to find which.
If aeij less bcfg, then e,b, or c is odd. Weigh 3. eb vs cj to find which.
Me and the guys at the office trade puzzles all the time and this was one of our favorites. We came up with a few solutions, but there were a lot of arguments and five minute proofs making sure every case was considered (kind of like the arguments in this thread). Being the only math degree graduate, I had to come up with something more solid.
Think of it as a math problem. Each weighing can give you three possible outcomes. Left side is heavier (+1), they're equal (0), or right side is heavier (-1). Think of a series of weighings as an ordered triple.
For example, if your first weighing is equal, second weighing has left heavier, and third weighing has right side heavier, you get {0, 1, -1}. For three possible outcomes of a weighing and three weighings in order, that gives us 3^3 = 27 possible ordered triples. If we come up with a mapping of balls to ordered triples, we can solve this guy easily. One note is that you have to match up ordered triples where you flip signs of each digit (you'll see in a minute - think heavier or lighter).
So let's do some matching:
Call the balls b1, b2, b3, b4, ... ,b13
Let's match them up with some triples:
{1,0,0} + {-1,0,0} = b1
{0,1,0} + {0,-1,0} = b2
{0,0,1} + {0,0,-1} = b3
{-1,-1,0} + {1,1,0} = b4
{0,-1,-1) + {0,1,1} = b5
{-1,0,-1) + {1,0,1) = b6
{1,-1,0} + {-1,1,0} = b7
{0,1,-1} + {0,-1,1} = b8
{1,0,-1} + {-1,0,1} = b9
{1,1,-1} + {-1,-1,1} = b10
{-1,1,1} + {1,-1,-1} = b11
{1,-1,1} + {-1,1,-1} = b12
{0,0,0} = b13
We left out {1,1,1} and {-1,-1,-1} but everything else is there and unique (if I typed it in correctly...).
Now we just need to arrange the balls into three weighings so that each ball matches the triples we put it with.
First weighing: b1 b7 b10 b12 vs b4 b6 b9 b11
Second weighing: b2 b8 b10 b11 vs b4 b5 b7 b12
Third weighing: b3 b9 b11 b12 vs b5 b6 b8 b10
Let's take an example...
Say you do the three weighings and get {1,0,0}. This maps to b1. Looking at the weighings, it couldn't be any other ball, because b1 is the only one represented in just the first weighing. If you do some quick logic, you can see that he's heavier. This is why we had to group triples with opposite sign. {1,0,0} means b1 is heavier. {-1,0,0} means b1 is lighter. If we matched one ball to each of those, you wouldn't be able to tell if the first was heavier or the second was lighter. Since we have a triple to choose from based on the signs, this gives us heavy/light information on balls 1-12.
Harder example: You do the weighings and get {-1,1,-1}. This maps to b11. Looking at it, b12 must be lighter. How do we know it's b12? Well, the ball has to be represented in each weighing, otherwise one weighing would be equal, so we ruled out balls 1-9. Out of 10-12, 11 is the only one where the first and last weighing should be the same, so it must be that one.
You've probably figured out by now that if all weighings are equal, it has to be 13, because he's the odd man out. Unfortunately, we can't figure out whether he's heavier or lighter, because we only get one bit of information about him.
So you're probably asking, what about {1,1,1} and {-1,-1,-1}? To do that you'd have to add one more ball that's always on either the left or right side, but try getting that to balance. Not happening.
This is Rob here
the solutions is similar to the first.
take out one ball and leave it to the side.
Then weigh 6 vs 6
if they are equal, the the 13th ball is the odd ball.
if not
then take the 6 heavier balls and remove 2.
then weigh 2v2.
if they are even weight then weight the last two balls to find the odd one.
otherwise take the heavier set and weigh them to find the odd one.
Here's my explanation of the solution:
I divide the balls into 4 groups as such:
AAAA
BBBB
CCCCC
First weigh As against Bs. If they are equal we call that scenario 2, if they differ that is scenario 1.
Scenario 1:
We now know that As are heavy and B are ligther, or the opposite - I'm going for the former for this example.
Now I'll take A1,A2,A3,B1 and B2 and weigh them against the Cs which are all normal.
If the weight is heavy, we know it is one of the three As and as such use our last attempt by weighing A1 against A2. If they are equal, the odd one is A3 (and we know it is heavy as a bonus). If it is lighter, it is one of the Bs and we can compare them - the ligther is the odd one (or compare to a normal one).
If the weight is neutral however, we know the odd ball must be among the A4, B3 or B4. Weigh A4 and B3 against two neutrals. If it is heavy, the odd ball is A4. If it is light the odd is B3. If it is neutral the odd ball is B4.
Scenario 2:
We now have 5 balls with no information about them. In our second attempt we weigh C1 and C2 against C3 and A1 (a known normal ball).
If the weight is equal, we use our last attempt to weigh C4, if that doesn't differ we know C5 is the odd one.
If the weight differs, we know that C1 and C2 is heavy and C3 is light - or the opposite. I'm going for the first one for this example. So for our last attempt we compare C1 and C2. If they are equal the odd ball was C3, but if either one is heavy - that was the odd ball.
Humm... I of course meant I had 3 groups. I can solve a complex puzzle in an hour, but counting is too hard...
Here's my method. I think Mike is correct, but I thought I would post the way I thought about the problem. Perhaps this wordier solution is easier to follow.
The basic approach:
(1a) If you have 3 balls and know that the odd ball is either heavier or lighter, you can solve in one move by comparing 1-1.
(1b) If you have 2 balls, AB, and know that one is odd, in combination with a neutral ball, o, you can solve. You may not know if the odd ball is, in fact, lighter or heavier, but you know which ball is odd. Test A - o. equal -> B, not equal -> A.
On to the method. Do a test of 4 v4. If equal, goto (2a). else (2b)
(2a)
If they are equal you have 5 balls.
Test ABC - ooo. If odd, you know weight of the odd ball and can employ (1a). Otherwise employ (1b) to solve remaining 2 balls.
(2b)
Otherwise, label A1,A2,A3,A4 - B1,B2,B3,B4
Assume that it tilted left since the cases are symmetric.
Test: B1,A2,A3,A4 - A1,ooo.
Three possibilities:
Equal (3a), Left heavier (3b), Right heavier (3c).
(3a) Equal:
This means that the three balls you took out B2,B3,B4 contain the odd ball. Since it tilted left earlier, we know that B must be lighter. Use (1a).
(3b) Left tilt.
Since there was no change in the tilt, it can't be B1 or A1. This means that the odd ball is in A2,A3,A4. Furthermore, A must be a heavier ball because it tilted left with only neutral balls. Use (1a).
(3c) Right tilt.
Since there was a change in the movement, it can't be A2,A3, or A4, since they remained the same. If it was B2,B3, or B4 it would have remained equal (see (3a)). Therefore, it must be either A1 or B1. We don't know which is heavier, but since we only have two candidates, use (1b).
I think Ben has it the simplest.
Here is the solution I came up with before reading the other posts. It assumes that the problem is only asking to determine the odd ball, not whether that ball is lighter or heavier than the others (although there is only one case in which it would remain unknown).
The thirteen balls are labeled:
A1, A2, A3, A4
B1, B2, B3, B4
C1, C2, C3, C4, C5
1st weighing: A1 A2 A3 A4 v. B1 B2 B3 B4
If A1 A2 A3 A4 are heavier, all C's are normal:
.....2nd weighing: A1 A2 B2 B3 v. B1 C1 C2 C3
..........If A1 A2 B2 B3 is heavier, then either A1 or A2 is heavy, or B1 is light
...............3rd weighing: A1 B1 v. C1 C2
....................If A1 B1 is heavier, then A1 is the odd ball (heavy)
....................If A1 B1 is lighter, then B1 is the odd ball (light)
....................If both are equal, A2 is the odd ball (heavy)
..........If A1 A2 B2 B3 is lighter, then either B2 or B3 is light
...............3rd weighing: B2 v. B3
....................If B2 is lighter, then B2 is the odd ball (light)
....................If B2 is heavier, then B3 is the odd ball (light)
..........If A1 A2 B2 B3 and B1 C1 C2 C3 are equal, then A3 or A4 is heavy, or B4 is light
...............3rd weighing: A3 B4 v. C1 C2
....................If A3 B4 is lighter, then B4 is the odd ball (light)
....................If A3 B4 is heavier, then A3 is the odd ball (heavy)
....................If both are equal, A4 is the odd ball (heavy)
If B1 B2 B3 B4 are heavier, then repeat the above steps with A's replacing B's and vice versa
If A1 A2 A3 A4 and B1 B2 B3 B4 are equal, then the odd ball is one of the C's
.....2nd weighing: C1 C2 C3 v. A1 A2 A3
..........If C1 C2 C3 is heavier, then C1, C2, or C3 is heavy
...............3rd weighing: C1 v. C2
....................If C1 is heavier, C1 is the odd ball (heavy)
....................If C1 is lighter, C2 is the odd ball (heavy)
....................If both are equal, C3 is the odd ball (heavy)
..........If C1 C2 C3 is lighter, then follow the same steps to determine the odd ball
..........If C1 C2 C3 and A1 A2 A3 are equal, then either C4 or C5 is the odd ball
...............3rd weighing: C4 v. A1
....................If C4 is heavier, C4 is the odd ball (heavy)
....................If C4 is lighter, C4 is the odd ball (light)
....................If both are equal, C5 is the odd ball (unknown)
OK, how about this:
prev: means this compare is same as previous compare
eq: means scale is level
ne: means scale is not level
opposite: means this compare is opposite the last compare
OK, how about this:
prev: means this compare is same as previous compare
eq: means scale is level
ne: means scale is not level
opposite: means this compare is opposite the last compare
A=A1,A2,A3,A4
B=B1,B2,B3,B4
C=C1,C2,C3,C4
D=D1
compare A1,A2,A3,A4 vs B1,B2,B3,B4
---eq:
------compare C1,C2 vs C3,A1
---------eq:
------------compare C4 vs A1
---------------eq:
------------------ret D1
---------------ne:
------------------ret C4
---------ne:
------------compare C1 vs C2
---------------prev:
------------------ret C1
---------------opposite:
------------------ret C2
---------------eq:
------------------ret C3
---ne:
------compare A1,A2,B1,C1 vs A3,A4,B2,C2
---------eq:
------------compare B3 vs C1
---------------eq:
------------------return B4
---------------ne:
------------------return B3
---------prev:
------------compare A1,B2 vs C1,C2
---------------prev:
------------------ret A1
---------------opposite:
------------------ret B2
---------------eq:
------------------ret A2
---------opposite:
------------compare C1,C2 vs B1,A3
---------------prev:
------------------ret A3
---------------opposite:
------------------ret B1
---------------eq:
------------------return A4
Man I wish I would've seen this a couple hours ago, or I would generalize this a bit further. But brain needs sleep for work tomorrow.
that was fun, thanks
i used the 4,4,5 method. i believe mike said it first
i did think it would take me longer to figure out, i'll admit.
by the way, it's not error prone. just for the hell of it, i used the 4,4,5 method for each of the 13 balls being the odd one out, once for heavier, once for lighter. yeah, all 26 solved correctly
I heard of this riddle back in high school in 1999. Took me a whole night to figure it out, but I solved it.
13 Coins Solution
We called it coins instead of balls.
My original blog post is at: my old site, but I ported it over to my new site today.
//krunk (^_^x)
Mine is most definitely not error prone. In fact I proved it for the entire problem space in my head very quickly. Just run each one through. Its not hard. In fact you might say mine (and possibly others that have similar answers [I haven't read through them all]) is the most optimized solution. The original problem did not call for a generic implementation for n-balls it specifically called for an implementation for 13-balls and 3 weightings exactly.
13 balls: abcdefghiklmn
1. abcd vs efgh
a. if different: abe vs cdf
i. if same: h vs m
ii. if abcd and abe are same: af vs lm
iii. if abcd and abe are diff: ce vs lm
b. if same: ik vs la
i. if same: a vs m
ii. if diff: i vs k
Solutions:
1ai, h != m: h
1ai, h = m: g
1aii, af = lm: b
1aii, af = abe: a
1aii, af != abe: f
1aiii, ce = lm: d
1aiii, ce = abe: e
1aiii, ce != abe: c
1bi, a = m: n
1bi, a != m: m
1bii, i = k: l
ibii, i = ik: i
ibii, i != ik: k
Here is a program that computes the optimal choice tree for any number of balls. Sorry about the crappy spacing, but this blog is limited:
#include <stdio.h>
#include <memory.h>
#define NUM_BALLS 13
#define HEAVIER_BIT 1
#define LIGHTER_BIT 2
enum Side { Off, Left, Right };
// Split the vector of possible states into 3 vectors, using a
// specific weighing. The 3 output vectors correspond to the three
// results of the weighing.
static void weigh(int state[], Side weighing[], int leftheavy[], int equal[], int rightheavy[]) {
memset(&leftheavy[0], 0, sizeof(int)*NUM_BALLS);
memset(&equal[0], 0, sizeof(int)*NUM_BALLS);
memset(&rightheavy[0], 0, sizeof(int)*NUM_BALLS);
for (int i = 0; i < NUM_BALLS; ++i) {
if (state[i] & HEAVIER_BIT) {
switch (weighing[i]) {
case Left: leftheavy[i] |= HEAVIER_BIT; break;
case Right: rightheavy[i] |= HEAVIER_BIT; break;
case Off: equal[i] |= HEAVIER_BIT; break;
}
}
if (state[i] & LIGHTER_BIT) {
switch (weighing[i]) {
case Right: leftheavy[i] |= LIGHTER_BIT; break;
case Left: rightheavy[i] |= LIGHTER_BIT; break;
case Off: equal[i] |= LIGHTER_BIT; break;
}
}
}
}
// Count the number of possible states in a state vector
static int count(int state[]) {
int c = 0;
for (int i = 0; i < NUM_BALLS; ++i)
switch (state[i]) {
case HEAVIER_BIT: c++; break;
case LIGHTER_BIT: c++; break;
case (HEAVIER_BIT | LIGHTER_BIT): c+=2; break;
}
return c;
}
// Print the outcome to the user
static void outcome(int depth, int state[]) {
for (int i = 0; i < depth-1; ++i)
printf("| ");
for (int i = 0; i < NUM_BALLS; ++i) {
if (state[i] & HEAVIER_BIT) {
printf(" ball %d is heavier\n", i+1);
break;
}
if (state[i] & LIGHTER_BIT) {
printf(" ball %d is lighter\n", i+1);
break;
}
}
}
// Recurse descent. Explore all possible weighings to determine the
// optimal one for a particular state.
static void recurse(int depth, int state[]) {
for (int i = 0; i < depth; ++i)
printf("| ");
for (int i = 0; i < NUM_BALLS; ++i)
printf("%d:%s%s ", i+1, (state[i] & HEAVIER_BIT) ? "H" : "",
(state[i] & LIGHTER_BIT) ? "L" : "");
printf("\n");
// Find the best weighing
int bestcount = NUM_BALLS*2;
Side bestweighing[NUM_BALLS];
// Consider all weighings
Side weighing[NUM_BALLS];
for (int i = 0; i < NUM_BALLS; ++i)
weighing[i] = Off;
int numweighing = 0;
do {
// Compute the possible next weighing
{
int i;
for (i = 0; i < NUM_BALLS; ++i) {
Side& s = weighing[i];
switch (s) {
case Off: s = Left; goto stop_outer;
case Left: s = Right; goto stop_outer;
case Right: s = Off;
}
// Keep iterating
}
if (i == NUM_BALLS)
break;
stop_outer:
// Evaluate the quality of the weighing
int numleft = 0;
int numright = 0;
for (int i = 0; i < NUM_BALLS; ++i) {
switch (weighing[i]) {
case Left: numleft++; break;
case Right: numright++; break;
}
}
// Only consider non-trivial weighings where both sides have an
// equal number of balls
if (numleft == 0 || numleft != numright)
continue;
numweighing++;
// Determine the outcome of the weighing
int leftheavy[NUM_BALLS];
int equal[NUM_BALLS];
int rightheavy[NUM_BALLS];
weigh(state, weighing, leftheavy, equal, rightheavy);
// Determine the quality of the result by counting the number of
// states in the worst case outcome
int c = count(leftheavy);
int t = count(equal);
if (t > c) c = t;
t = count(rightheavy);
if (t > c) c = t;
// Keep the best result
if (c < bestcount) {
bestcount = c;
memcpy(&bestweighing[0], &weighing[0], sizeof(weighing));
}
}
} while (1);
// Describe the best weighing
for (int i = 0; i < depth; ++i)
printf("| ");
printf("Weigh:");
for (int i = 0; i < NUM_BALLS; ++i)
if (bestweighing[i] == Left)
printf(" %d", i+1);
printf(" against");
for (int i = 0; i < NUM_BALLS; ++i)
if (bestweighing[i] == Right)
printf(" %d", i+1);
printf("\n");
{
// Recurse using the best weighing
int leftheavy[NUM_BALLS];
int equal[NUM_BALLS];
int rightheavy[NUM_BALLS];
weigh(state, bestweighing, leftheavy, equal, rightheavy);
int c = count(leftheavy);
if (c > 0) {
for (int i = 0; i < depth; ++i)
printf("| ");
printf(" Left is heavier:\n");
if (c == 1)
outcome(depth+1, leftheavy);
else
recurse(depth+1, leftheavy);
}
c = count(rightheavy);
if (c > 0) {
for (int i = 0; i < depth; ++i)
printf("| ");
printf(" Right is heavier:\n");
if (c == 1)
outcome(depth+1, rightheavy);
else
recurse(depth+1, rightheavy);
}
c = count(equal);
if (c > 0) {
for (int i = 0; i < depth; ++i)
printf("| ");
printf(" Equal weight:\n");
if (c == 1)
outcome(depth+1, equal);
else
recurse(depth+1, equal);
}
}
}
int main(int argc, char** argv) {
int state[NUM_BALLS];
for (int i = 0; i < NUM_BALLS; ++i)
state[i] = (HEAVIER_BIT | LIGHTER_BIT);
recurse(0, state);
}
Here is the optimal result for 13 balls:
1:HL 2:HL 3:HL 4:HL 5:HL 6:HL 7:HL 8:HL 9:HL 10:HL 11:HL 12:HL 13:HL
Weigh: 5 6 7 8 against 1 2 3 4
Left is heavier:
| 1:L 2:L 3:L 4:L 5:H 6:H 7:H 8:H 9: 10: 11: 12: 13:
| Weigh: 3 4 6 against 1 2 5
| Left is heavier:
| | 1:L 2:L 3: 4: 5: 6:H 7: 8: 9: 10: 11: 12: 13:
| | Weigh: 2 against 1
| | Left is heavier:
| | ball 1 is lighter
| | Right is heavier:
| | ball 2 is lighter
| | Equal weight:
| | ball 6 is heavier
| Right is heavier:
| | 1: 2: 3:L 4:L 5:H 6: 7: 8: 9: 10: 11: 12: 13:
| | Weigh: 4 against 3
| | Left is heavier:
| | ball 3 is lighter
| | Right is heavier:
| | ball 4 is lighter
| | Equal weight:
| | ball 5 is heavier
| Equal weight:
| | 1: 2: 3: 4: 5: 6: 7:H 8:H 9: 10: 11: 12: 13:
| | Weigh: 7 against 1
| | Left is heavier:
| | ball 7 is heavier
| | Equal weight:
| | ball 8 is heavier
Right is heavier:
| 1:H 2:H 3:H 4:H 5:L 6:L 7:L 8:L 9: 10: 11: 12: 13:
| Weigh: 3 4 6 against 1 2 5
| Left is heavier:
| | 1: 2: 3:H 4:H 5:L 6: 7: 8: 9: 10: 11: 12: 13:
| | Weigh: 4 against 3
| | Left is heavier:
| | ball 4 is heavier
| | Right is heavier:
| | ball 3 is heavier
| | Equal weight:
| | ball 5 is lighter
| Right is heavier:
| | 1:H 2:H 3: 4: 5: 6:L 7: 8: 9: 10: 11: 12: 13:
| | Weigh: 2 against 1
| | Left is heavier:
| | ball 2 is heavier
| | Right is heavier:
| | ball 1 is heavier
| | Equal weight:
| | ball 6 is lighter
| Equal weight:
| | 1: 2: 3: 4: 5: 6: 7:L 8:L 9: 10: 11: 12: 13:
| | Weigh: 7 against 1
| | Right is heavier:
| | ball 7 is lighter
| | Equal weight:
| | ball 8 is lighter
Equal weight:
| 1: 2: 3: 4: 5: 6: 7: 8: 9:HL 10:HL 11:HL 12:HL 13:HL
| Weigh: 9 10 11 against 1 2 3
| Left is heavier:
| | 1: 2: 3: 4: 5: 6: 7: 8: 9:H 10:H 11:H 12: 13:
| | Weigh: 10 against 9
| | Left is heavier:
| | ball 10 is heavier
| | Right is heavier:
| | ball 9 is heavier
| | Equal weight:
| | ball 11 is heavier
| Right is heavier:
| | 1: 2: 3: 4: 5: 6: 7: 8: 9:L 10:L 11:L 12: 13:
| | Weigh: 10 against 9
| | Left is heavier:
| | ball 9 is lighter
| | Right is heavier:
| | ball 10 is lighter
| | Equal weight:
| | ball 11 is lighter
| Equal weight:
| | 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:HL 13:HL
| | Weigh: 12 against 1
| | Left is heavier:
| | ball 12 is heavier
| | Right is heavier:
| | ball 12 is lighter
| | Equal weight:
| | | 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:HL
| | | Weigh: 13 against 1
| | | Left is heavier:
| | | ball 13 is heavier
| | | Right is heavier:
| | | ball 13 is lighter
ignoranceisstr is definitely the most elegant one on here though. I do have to agree. And its easily generalizable to more balls/compares.
Oh, MY GOD.
Can u guys read:
"Find out the odd ball in 3 weightings !!!"
Why I saw some solution with more than 10 if-else or switch-case. ?
DO I missed something..?
My Solution :
only 3 if-else.
Assume 13 balls are b1, b2, b3, b5 .... b13
seta = {b1, b2, b3, b4, b5 ,b6}
setb = {b6, b8, b9, b10, b10, b12}
if seta is equal weight with setb
then ball is b13
else if seta is heavier than setb
problemSet is seta
else
problemSet is setb
Now it become find out 1 odd ball in 6 balls within 2 weight problem.
Since "find 1 odd ball in 8 balls" can be solved within 2 weights. so "find 1 odd ball in 6 balls"can also be solved in the same method.
Hence, the odd ball can be find.
This is an attempt to generalize the problem. I loved ignoranceisstr's solution, but perhaps this may give more insight into how the picking strategies relate.
There are 4 general conditions that seem to be relevant:
a. You know nothing and have no neutral balls.
b. You know nothing, but have some extra neutral balls. I think you're going to need (n+1)/2 neutral balls, but I'm not sure about this.
c. You know the weight of the ball you're searching for.
d. You've weighed half of the balls against half of the balls previously.
This is a chart of the maximum number of balls that we can solve with a certain number of turns and information.
__1 2 3_ 4_ 5__ t turns
a. 0 4 13 40 121 (t^3 -1)/2 (no info)
b. 2 5 14 41 122 (t^3+1)/2 (neutral balls)
c. 3 9 27 81 243 t^3 (know if heavy or light)
d. 0 8 26 80 242 t^3 - 1 (weighed 50/50 before)
Imagine these are pairs, (4,c) (2,d) etc.
The relationship are:
(t,a) = (t-1, d) + (t-1,b)
(t,b) = (t-1,c) + (t-1,b)
(t,c) = 3*(t-1,c)
(t,d) = (t-1,d) + 2*(t-1,c)
This suggests (and was based on) the method for solving each level. The tricky one is d, where you flip some of the A set and the B set (by amounts (t-1,d)/2), replace the rest of B with neutral balls, which should be (t-1,c) ). For c you just split in 3. For b you test (t-1,c) balls against neutral balls, and set aside (t-1,b) balls. For a you set aside (t-1,b) balls and weigh a total of (t-1,d) balls 50-50.
I would point out that in the situations where you don't have the maximum legal amount, you should always try and get as many neutral balls as possible. So, if you started out with 11 balls, you should set aside 5, and test 3v3.
(This is a different Adam)
Group 1 4 balls a1-4
Group 2 4 balls b1-4
Group 3 5 balls c1-5
weighing 1: a1a2a3a4 vs. b1b2b3b4
case 1: a1a2a3a4 == b1b2b3b4. odd ball is in c1-5
weighing 2: c1c2c3 vs. a1a2a3
case 1a: equal, the odd ball is c4 or c5. Weigh one of these against any other 'normal' ball to determine odd ball.
case 1b: c1c2c3 > a1a2a3. Since we know a's are normal, the odd ball must be heavier and in c1-c3. Weigh c1 vs. c2. If equal, c3 is the odd ball. Otherwise, the heavier ball is the odd ball.
case 1c: c1c2c3 < a1a2a3. This is the inverse of case 1b and is solvable in the same number of steps.
case 2: a1-4 > b1-4 This means c1-5 are normal.
Weighing 2: a1b1b2 vs. a2b3c1.
case 2a:equal, odd ball is between a3, a4, b4. Since we know a's are heavier than b's, we can weigh a3 vs. a4. If one is heavier, it is the odd ball. If they are the same, the odd ball is b4.
case 2b: a1b1b2 > a2b3c1. a1 or b3 is odd ball. Weigh either against any other ball.
case 2c: a1b1b2 < a2b3c1. odd ball is between a2, b1, b2. Since we know a's are heavier than b's, we can weigh b1 vs. b2. If one is lighter, it's the odd ball. If they are the same, the odd ball is a2.
case 3: a1-4 < b1-4. This is inverse of case 2 and is solvable in the same number of steps.
The key to solving this is to use the information you obtain from each weighing. If one set of balls is heavier than another set, and it contains the odd ball, the odd ball must be "heavy". Conversely, if one set of balls is lighter than another set, and it contains the odd ball, the odd ball must be "light".
Correct Answer for interview:
13 balls weight all 13 what the problem. It's not like we're time-sharing the %^3$ing scale.
What's the deal anyway? Why can't I use the scale as much as I want? Do you also limit bathroom breaks?"
@Francis:
Evidently, you cannot read. The problems states you don't know whether the odd ball is lighter or heavier so even your simple initial partitioning scheme does not work. With my solution, and probably most of the solutions on here, you only traverse 3 compares. More compares are listed but you only do 3 compares. It is expected that you understand branching and how it works.
The next question is how many balls can you solve this problem for if you are allowed 4 weighings instead iof 3.
Your example 1:8 is flawed:
You state:
"The question is to find out the minimum number of weighings required to spot the odd heavier ball among 8 identically looking balls using a common balance.Answer is 2 and the solution is given in the next paragraph."
Let's suppose that the A's are heavier than the B's. Then we have the following possibilities:
1] A1 + (C1+C2) ? A2 + A3
2] A1 + A2 ? (C1 or C2) + A3
3] A1 + A3 ? (C1 or C2) + A2
Suppose that in 1] above A2 + A3 > A1+(C1 or C2), then you would have to measure A2 against A3 - one more measurement, so you have 3 measurements, not 2! Similarly, if you had A1+A2>(C1 or C2), you would have one extra measurement. Same goes for A1+A3>(C1 or C2).
Thus it is impossible to find the heavier ball in every case. The puzzle is ill-formed and ambiguous.
asa
Really nice puzzle...Congrats to all who solved this (Including me!!!)
----------------
My blog:
http://onepuzzleaday.blogspot.com
http://justriddles.blogspot.com
http://justfungames.blogspot.com
----------------
For the second one, a similar approach
A1 A2 B1 B2 C1 C2 D1 D2
If A1 A2 <> B1 B2 (#1), then compare any of its pairs, for example A1 <> B2 (#2), finally compare (#3) any of the two with one of the other balls.
Mike,dude....excellent solution!!!
most of the other solutions give by others are incorrect.
More of such questions are available
at
http://placementsindia.blogspot.com/2007/12/solutions-to-few-google-top-interview.html
Of course the more interesting type of problem is where you have to find out the odd ball *AND* whether it's lighter or heavier. And this definitely can't be done in 3 measures. Reason: 13 odd balls, those are 26 possibilities (1 lighter, ..., 13 heavier). Each measure can partition the still number of possibility into 3 "buckets". Measures 2 and 3 together can at most differ 9 possibilities (the balance can be <, = or > in each measure, and 3*3 = 9), so no "bucket" of the first measure must be larger than 9. So the first measure should partition the 26 possibilities into "buckets" 9, 9 and 8. For symmetry reasons, the two 9-"buckets" should correspond to left and right, while "8" should correspond to "equilibrium" (left and right can't return different still open possibilities at the very first measure). In the case of quilibrium, the not measured n calls represent precisely 2n possibilities, so the 8 open possibilities requires after the first measure represent 4 not measured balls. As there are 13 balls all together, 9 balls should have involved in the first measure. But as 9 is an odd number, that's impossible. qed (I hope :-)
An interesting extension of the problem though is extending the number of measures. It can be shown that the *complete* problem (determining the odd ball, and whether it's lighter or heavier) with n measures can be solved with (3^n-3)/2 balls. For 3 measures, that's of course (27-3)/2=12 balls, for 4 measures (wouldn't that be interesting), it's (81-3)/39 balls Furthermore, there exists an algorithmic solution for all these problems where the measures done don't depend on their result (example for 3 measures). The balls are tagged with "codes" in the following way:
- write down all combinations of letters abc with the given length (aaa,aab,aac,aba,...,ccc). Those are 3^n.
- cancel the three codes where all letters are equal (aaa,bbb,ccc). 3^n-3 remain.
- for each code, fine the first letter that differes from its predecessor (example: in aaabcac, that would be ab). Cancel the code unless this is ab, ba or ca. This step will cancel half of the remaining codes, so (3^n-3)/2 balls remain.
- now write these codes for all balls in rows of a table, for 12 balls it looks like:
01 a a b
02 a b b
03 a b a
04 a b c
05 b b c
06 b c c
07 b c b
08 b c a
09 c c a
10 c a a
11 c a c
12 c a b
- First measure: balls with 'a' in first column agains balls with 'b' in first column (above: 1,2,3,4 vs 5,6,7,8)
- Second measure: same with second column (1,10,11,12 vs 2,3,4,5)
- Third measure: same with third column (3,8,9,10 vs 1,2,7,12)
- For each measure we write down 'a' if left, 'b' if right, and 'c' if equilibirum. This gives a 3-character string (example: abc for left-right-equi)
- If this code is found in above table (abc is ball 4), then this ball was the heavier one
- Otherwise, swap all 'a' and 'b', then you'll surely find its code, and its ball was the lighter one (example: baa for right-left-left is not in above table, so modify it to abb = ball 2, so ball 2 was lighter).
I hope I didn't make mistakes with all that typing :-)
I forgot to mention that I found this algorithmic approach here (in German though, hence I translated it): http://www.wer-weiss-was.de/theme113/article567234.html
Also, the strings tagged to the coins in the example above are not in the same order as produced by the algorithm, but the order doesn't matter as long as you use the same table for the finallookup.
Have anyone try out to find the odd ball among the 13 balls using 3 weightings, AND also figure out whether it is heavier or lighter than the normal ball?
I have a solution to this, and it definitely need you to think out of the box. Give it a try.
I think 13 should be break into 6 ,6,1
wieghing frst time::::
if(6 = 6 )then on only one check other one(13 one) is odd one.
else(6 =! 6)dat means defective is on either of these pair of 6.
so break 6 into 3 + 3
by wieghing 2nd time:::::
one of these 3 will be defective
by wieghing 3rd time:::::
again measure 1 and 1 if it is equal then 3rd one one will be defective or else among them one is defective.
The problem can be solved as follows:
Divide 12 balls in 2 sets of 6 each with one ball being odd one out. For simplicity, lets call the 2 groups Set A and Set B. Name the odd ball C.
First weigh Sets A & B.
Scenario 1:
If A=B,
Pick one ball from either A or B and weigh against C. This will tell you which ball is lighter or heavier.
Senario 2:
a) If A is not equal to B, then we know C is of standard weight.
b) Now compare 1 ball of A with C. If equal, A is of standard weight.
c)compare 1 ball of B with C. You will definitely now know amongst B or C which is heavier and which is lighter as C is always standard weight.
Ramesh.. your solution is incorrect....
I have solved this. it is a much elaborate solution..
A1A2A3,B1B2B3,C1C2C3,D1D2D3,E1.
1. we weight A1A2A3,B1B2B3 vs C1C2C3,D1D2D3.
if equal than is E1
2.else if either one is heavier we take that side and weight ex. A1A2A3 vs B1B2B3.
3.we take the heavier ex A and weight A1 vs A2 if equal than is A3 or else is the heavier of them.
hey solution is very simple :
jst divide the balls in to group of 5,5,3 and weigh the group of 5 balls if they weigh same then the odd balls in group of 3 and we can easily accomplished this by using 2 weigh chance and if group of 5 balls have unbalance weigh then take that group of 5 balls divide it in to group of 2,2,1 and now we have still left 2 chance and we can easily find out the odd one balls ..
I am working with an
Internet marketing company
and this really worth reading for me Many things i did not know before. I would be your frequent visitor.
Find Hospitals in your Area
need answer for this puzzle....
There are four teams A, B, C, D playing game. If any one team loses, it will play twice the money to all other teams. They play 3 games. B, C, D loses one game each in the order. Finally A & B has Rs. 40 each & C has Rs. 80 & D has Rs. 16.
Which team has started with minimum money? i) A ii) B iii) C iv) D
Which team has started with max money? i) A ii) B iii) C iv) D
need answer for this puzzle....
There are four teams A, B, C, D playing game. If any one team loses, it will play twice the money to all other teams. They play 3 games. B, C, D loses one game each in the order. Finally A & B has Rs. 40 each & C has Rs. 80 & D has Rs. 16.
Which team has started with minimum money? i) A ii) B iii) C iv) D
Which team has started with max money? i) A ii) B iii) C iv) D
You dumb bro .... The odd ball can be light or heave
You dumb bro .... The odd ball can be light or heave
if the same process repeats for N number of balls... is there any formaula bu which we can know ,how many time we have to weigh the minimum to figure out which ball is the heavier one ???
The solution works for if the odd ball is heavier.
We need at most 3 comparison.
Step 1: divide balls in two parts each contains 6 balls. If their weight are equal then done.
If not
Step 2: Divide heavier part into two part each contains 3 and weight them.
Step 3: From the heavier part take two balls and compare them. If equal then done, else the heavier is odd.
easier way is to group balls into 4 groups of 3 and 1 left. weigh 1st 2 groups. if odd ball is der, u could get in 2nd step. if not weigh next 2 groups. if odd id not in dat the single one is odd. other wise u could get in next step.
We are from e-Commerce company "healthgenie.in" if you're looking to purchase weighing scale at affordable price then order at http://www.healthgenie.in/home-care/weight-management/weighing-scale
Each use of the scale provides 3 outcomes:
1. even
2. heavy right
3. heavy left
So can reduce your possibilities by 3 each time you use the scale.
You use the scale 3 times.
So the scale can have: 3 x 3 x 3 = 27 different possibilities.
That means you can use it to solve a problem set with up to 27 possibilities.
You have 13 balls.
Each ball is either:
1. heavy
2. light.
So each ball has 2 possibilities.
13 balls x 2 possibilities = 26 possibilities.
Therefore: it IS possible to solve this problem using a scale 3 times.
I am not providing a solution here. I am just showing that if the outcomes of the scale are used to their potential then 27 bits of information can be obtained.
Based on this, I am speculating that 3 uses of the scale could actually be used on 14 balls. Where most of the time (27 out of 28) you will know the odd ball and the weight (heavy or light).. and 1 in 28 times, you will only know which ball is odd, but not the relative weight.
Split the balls in 4 sets:
Set A: {A1 A2 A3 A4}
Set B: {B1 B2 B3 B4}
Set C: {C1 C2 C3 C4}
Set D: {D1}
Weigh A against B:
Case 1: A goes up and B goes down
________Weigh Set Odd: {A1 A2 A3 B1 B2} against C + D : {C1 C2 C3 C4 D1}
________Case 1: Odd goes up
________________Weigh A1 against A2
________________Case 1: A1 goes up
________________________A1 is odd
________________Case 2: A2 goes up
________________________A2 is odd
________________Case 3: balanced
________________________A3 is odd
________Case 2: Odd goes down
________________Weigh B1 against B2
________________Case 1: B1 goes down
________________________B1 is odd
________________Case 2: B2 goes down
________________________B2 is odd
________Case 3: balanced
________________Weigh B3 and B4
________________Case 1: B3 goes down
________________________B3 is odd
________________Case 2: B4 goes down
________________________B4 is odd
________________Case 3: balanced
________________________A4 is odd
Case 2: A goes up and B goes down
________Solution will mirror Case 1
Case 3: balanced
________Trivial (hint: weigh {C1 C2 C3} against {A1 A2 A3})
Guys. ignoranceisstr was looking at the root of the problem, but still could not see it. The task is about trinary code and how many numbers you can encode with it. This task allows for up to 27 ball sets. It's rather easy if you know where to start. ignoranceisstr posted one of the answers, but didn't understand the problem. Math graduate my ass. Check out this solution:
1 9 8 - 4 b c
2 7 9 - 5 a c
3 7 8 - 6 a b
12 balls 1 through c, and one not participating in measurements (code 000).
4433114411
Professional Touch Digital Kitchen Scale is a highly advanced kitchen scales. The unit has not one but four precision GFX latest generation sensors which deliver high accuracy and the response time is very quick for coping up with the fast pace kitchens. Buy Now at Santamedical.com
https://santamedical.com/product/gurin-professional-touch-digital-kitchen-scale/
Quiz on Measures and Weights is for students and other who are looking for preparation material of job tests.
thank you for sharing this amezing blog for weighing related information feel free and visit us elweigh
According to Shannon information theory, there are 26 possibilities, or total information needed is log2(26) bits. Each weighing has three possible outcomes, or log2(3) bits. Three weighing provides 3xlog2(3) = log2(27) which is greater than needed information log2(27). So there is a solution.
since one ball carries two possibilities, you need a standard ball (0) to resolve the puzzle:
Lets name the balls as a1~5, b1~4, c1~4, and 0.
====1st try: a1~5 ----v---- b1~4 +0
if balanced, we know how to resolve c1~4 with additional 2 tries.
If not balanced and left tray is heavy, we divide the 9 balls to three group, take 3 (a1~3) off the tray, keep 3 unchanged (a4, a5, b1), and more 3 from one try to another (b2,b3,b4):
Take a1~3 down and
===2nd try:
a4,5,b2~4, ----v---- b1, 0000 ( now c1~4 can be used as 0 after 1st try).
Case A): if the scale doe not change, the odd ball is in (a4, a5, b1) because the do not move;
Case B): if the scale is balanced, one of a1~3 is heavy because they are off the scale
Case C): if the right side becomes heavy, the odd ball is light and in (b2,b3,b4) because they moved from right to left.
===3rd try:
Case B) and C) is easy. For case A): take b1 down, and more a5 to right tray, and keep a4 not moved. We will have three new out come, use same logic as in 2nd try to judge. You then find which ball is light or heavy.
My quiz is: With 4 tries, and one standard ball is provided, what is maximum number of ball we can resolve? Of cause, you have to tell what ball, heavy or light). The answer is ?????
Wow is good to be back with my ex again, thank you Dr Ekpen for the help, I just want to let you know that is reading this post in case you are having issues with your lover and is leading to divorce and you don’t want the divorce, Dr Ekpen is the answer to your problem. Or you are already divorce and you still want him/her contact Dr Ekpen the spell caster now on (ekpentemple@gmail.com) and you will be clad you did
Post a Comment