CareerCup

Let marbles be 123..9, L = light, H = heavy , G = good
weigh 123-456
then if L-H
weigh 124-389, L-H again => weigh 1-3(G) => 1 or 2 for light, H-L => weigh 4-1(G) => 3 or 4 for heavy, equal => weigh 5-1(G) => 5 or 6
else
weigh 71-82, L-H => weigh 7-1(G) => 7 or 8, equal => 9

max 3 weighs

I don't agree with 2 passes answer.
Consider: Given 3 balls. two balls are the same, one is different than the other two. How can you find out the abnormal one in 1 weigh? It's not possible.

if 9 marbles, put them in 3 groups, so each group has 3 marbles so only one group would have different weight than the other two group since there's only 1 marble is different than the others. So take the two groups aside and you left with 3 marbles and weigh them again and you find the result!!
anonym's answer was correct. It doesn't matter if weighs more or less, no matter what it will make the group's weight different than the others.

2 Passes are good enough

anonym and pinG are correct

I think 3 comparison is requires. Divide into 3 parts . Compare 1 & 2 part . If they are balanced defect is in 3rd part. If 1 & 2 imbalanced than take the lighter version from 1 & 2 comparison and compare it with 3rd part. If its equal than defect piece is another part from 1 & 2 comparison and its heavy else it will be lighter one. Now we know that ball is heavy or light . So now compare 2 balls in this part. if they are equal than 3rd one had defect and if not than heavy one has defect.
So in total 3 weighing would be required.

best case: two weighing, worst case: three weighing

divided into three triples. if equal, then look at the third triple, weigh two of the third triple, if equal, then the third one in the third triple is the one., else, then weigh the first triple and the second triple, then will know if the abnormal one is overweighted or not.
ok, if the two triples are not equal. then test the first triple and the third triple to know if overwieghted or light, also will know it is in side which triple, then test two of the abnormal triple, (cuz you know if the abnormal one is overweighted or light),then you know the answer

well tAlking about best cases and worst cases for this problem:-

we can have best case as 1 weighing
and worst case more than three weighing for sure

if we choose to make two sets of quadruplets and if they equal each other then the left over single marble is the defective one, hence best case of 1 weighing.

same for worst case..it can be gotten in other ways too I guess. I don't want to worry about the worst case anyway.

Thanks.

This takes 3 passes since at the start you don't know whether the marble is too heavy or too light.

that's not the best case, since, you have 1/9 possibility to get the right ball, therefore, the expect number of operation is not the most optimal

what I argued about the worst case, and best case, which are both based on the same operations strategy. Otherwise, if you change the strategy, that's not the best or worst case, since every time, you have to do the same thing, whatever the result turns out

it will take atleast 3 passes(three groups). best case is 2 when u split into three groups and 1 when u split it into 2 groups.

Yes, splitting into 3 vs 3 in first weighing will not give the answer in 2 weighings: If they turn out equal in first weighing, how will you determine in 1 weighing, of the last three, which is different?

In fact 2 weighings is not possible, it will take at least three if we don't know if the ball is heavy or light.

If I remember correctly, For k weighings, max you can do is (3^k - 3)/2. If you don't believe me, lookup the web!

2 passes is correct yar kyo kachra kar rahe ho

2 passes is correct yar kyo kachra kar rahe ho

2 passes is correct

here is the answer...in max 3 and min 2 weighs
divide the 9 coins into two parts say(l1,l2,l2,l4)and(h1,h2,h3,h4) and say the remaining coin is x.
step1.now weigh first part with the second one..
two possibilities are there.if both are equql,then go to step 3.otherwise go to step 2.
step2.divide the coins as(h1,h2,l1) and (h3,h4,x).weigh two parts.3 possibilities are there.
1.if both are equal,then 1 of l2,l3,l4 is lighter.so weigh l2 with l3.if both are equal,then l4 is odd and is lighter ow the lighter one is odd and is lighter.
2.if(h1,h2,l1) is heavier,then either of h1 or h2 is heavier.weigh h1 with h2.heavier one is odd and is heavier.if both are equal,then there is something wrong.
3.if(h3,h4,x) is heavier,then either h3 or h4 is heavier or l1 is lighter.so weigh h3 with h4.if both are equal,then l1 is odd and is lighter ow the coin on heavier side is odd and is heavy.
step3.weigh coin x with any of the remaining 8 coins.if x is on lighter side,then x is odd and is lighter ow x is odd and is heavier.

1234-5678

case 1234=5678
9 is the answer

Case 1234<5678
Learnt : 1234 is the lighter side
564-789

Case 564 = 789
Learnt : 123 contains ur answer
1-2
Case 1=2
3 is the answer
Case 1<2
1 is the answer
Case 1>2
2 is the answer
Case 789 < 564
5-6
Case 5=6
Not possible
Case 5<6
6 is the answer
Case 5>6
5 is the answer
Case 789 > 564
7-8
Case 7=8
4 is the answer
Case 7>8
7 is the answer
Case 7<8
8 is the answer

Case 1234>5678
W.L.O.G Answer can be determined in 2 more comparison.

1234-5678

case 1234=5678
9 is the answer

Case 1234<5678
   Learnt : 1234 is the lighter side
   564-789
   
   Case 564 = 789
     Learnt :  123 contains ur answer
      1-2
     Case 1=2
        3 is the answer
     Case 1<2
         1 is the answer        
     Case 1>2
         2 is the answer
   Case 789 < 564
      5-6
      Case 5=6
        Not possible
      Case 5<6
        6 is the answer
      Case 5>6
        5 is the answer
   Case 789 > 564
      7-8
      Case 7=8
        4 is the answer
      Case 7>8
         7 is the answer
      Case 7<8
        8 is the answer

Case 1234>5678
W.L.O.G Answer can be determined in 2 more comparison.

2attempts --best case.
first split into a,b,c(Each 3 balls)
then find out the group which has diff weight..(lets say a )
Second take 2 balls out of these 3 balls from group a.
if both the balls have same weight then the one u dint choose was faulty ball.

if balls have diff weight then exchange the ball and do another comparison..3 attempts.worst case

2 tries. first two groups of 3. if one is heavier you narrowed it down to that group of 3. if they are equal you narrowed it down to the remaining group of 3. then pick 2 and weigh those. if they are equal you know the 3rd is the one. if not you are down to 1 and are done.

2 weighings and some elimination.

2 passes .. weigh two triplets at a time, if they are balanced the overweight marble is in the third triplet and weigh two of the third triples..you will find one.. done!! Else if there is imbalance in the first two triplets then take the imbalanced triplet and weigh two of the marbles in it !! voila...

In the best case, everything takes exactly 1 operation.