83 replies to this topic

[achia]

"Parik" posted on 18 March 2009 - 04:46 PM the clearest description I have seen to solving the case comprehensively.

That is by dividing into groups of 9, then 3 and finally singly.
In each Division we can identify the defective group or item in 1 or 2 steps, depending on luck.

Using this method, the best outcome is 3 weighings and the worst outcome is 6 weighings. I think this is the best strategy to adopt as the arithmetic average of the number of attempts is 4.5.

Other strategies like balancing 13-13 and leaving one aside may solve the problem in 1 step (very lucky) or end up with 26 steps (if by 26 attempts the odd coin has not been identified, we can infer that the last coin is the odd one without further weighing). The arithmetic average of all possible outcomes is 13.5.

[aniketgoel]

For finding the different one out of three u will always require just 2 attempts..

suppose u try with 1 and 2 bunch they are not equal.

try with 1 and 3 and now if they are also not equal then its sure that the bunch 1 contains fault else if 1 and 3 are equal then bunch 2 will have fault in it.

So just 2 try for a lot of 3.

Thus in just 6 attempts you could find the solution.

So 6 is the answer..

[hareesh]

In min 3 weighings and max 5 weighings we can definitely find the odd coin

All possibilities :-
ivide 27 into piles of 7, 7, 13
1) compare 7 vs 7 coins, keeping 13 coins aside
If both of them don't weigh same, then it means that the odd coin is inside these 14 coins
If both of the sets weigh same, then we need to find the odd coin from 13 coins.

2) compare 4 vs 4 coins, keeping 5 or 6 coins aside(this depends on the previous result)
Applying the same logic as explained in step 1, we will be left with 5 or 6 or 8 coins to find the odd coin from

3) Depending on the result from previous step we need to split coins to weigh
case 1) 5 - 2vs2, 1 kept aside
case 2) 6 - 2vs2, 2 kept aside
case 3) 8 - 3vs3, 2 kept aside
If its case one, then we are done, else we will be left with either 2 or 3 coins to determine the odd coin from

4) If two coins are left, then we can find the odd one by comparing with normal coins(other coins)
If three coins are left, then we may require one more weighing

[Teddy Kesgar]

An easier-to-understand (IMHO): (sorry for my bad english)

Spoiler for Hint

27 ==> 13[A] - 13[B] - 1[C]
compare A and B (1 weighing)
if A=B then we found the answer in C

13 ==> 6[A] - 6[B] - 1[C] --
compare A and B (1 weighing)
if A=B then we found the answer in C

6 ==> 3[A] - 3[B]
compare A and B (1 weighing)
then we check either A or B is heavier

3 ==> 1[A] - 1[B] - 1[C]
compare A and B (1 weighing)
if A=B then we found the answer in C

Then, I can assure one to weigh at least 4 times before I get the correct answer.

For you who are studying Computer Science, you might notice that this solution uses
Divide-and-Conquer approach.

Edited by Teddy Kesgar, 13 July 2010 - 04:30 AM.

[scorp]

An easier-to-understand (IMHO): (sorry for my bad english)

Spoiler for Hint

27 ==> 13[A] - 13[B] - 1[C]
compare A and B (1 weighing)
if A=B then we found the answer in C

13 ==> 6[A] - 6[B] - 1[C] --
compare A and B (1 weighing)
if A=B then we found the answer in C

6 ==> 3[A] - 3[B]
compare A and B (1 weighing)
then we check either A or B is heavier

3 ==> 1[A] - 1[B] - 1[C]
compare A and B (1 weighing)
if A=B then we found the answer in C

Then, I can assure one to weigh at least 4 times before I get the correct answer.

For you who are studying Computer Science, you might notice that this solution uses
Divide-and-Conquer approach.

which one among A or B will you choose for ur next step as it says one of them is either heavy or light ... So u cannot determine the defective bunch this way ..

[jensun]

Spoiler for hint

27=1+13+13

balance 13coins nd 13 coins... if equal ... the one left is the heavy/low weight coin..

otherwise,

13=1+6+6

continue the same process......

6=1+3+3

continue...

3=1+1+1

continue....

minimum steps is < 4...

[KlueMaster]

Spoiler for Here is how to do it in

make 3 group of 9s, balance any two groups to observe: (a) it's a balance then third group has faulty coin --- 1 weighing, anomaly unknown (b) it's tilted on one side, in which case replace the heavier group with the third group to see (b.i) the balance --- 2 weighing, anomaly is 11g coin in heavier group (b.ii) similar tilt --- 2 weighing, anomaly is 9g coin in lighter group repeat the above steps by diving the identified group in 3 subgroup of 3s, and then further into 3 subgroups of 1s. In short 3 weighing to identify the coin and 1 to identify the anomaly.

overall 4 weighing...

[welshdragon]

Using your method you need only 6 weighing .. use a balance scale not a numerical one . with 3 piles you only need to weigh twice, to find the odd one out. weigh pile 1 against 2,. if equal then pile 3 is the odd one . if unequal then weigh the heavier against pile 3 .. this will be equal or lighter . if unequal and it cannot be heavier . that would mean 3 different weights, so pile 3 is the odd ball. do this with the next 2 sets . equaling 6 at most.

[Dumb And Stupid]

The answer is 4 and my solution is below.

Spoiler for Proof of Concept

if(b1:b9 == b10:b18){
if(b19:b21 == b22:b24){
if(b25 == b26)
{
***b27***
}else//if(b25 == b26)
{
if(b25 == b27)
{
***b26***
}
else
{
***b25***
}
}
}
else //if(b19:b21 == b22:b24)
{
case(b19:b21 < b22:b24){
if(b19,b22,b21 < b20,b26,b27){ //b23,b24 left out
//that means b19 b 21 is lighter
if(b19<b21)
{
***b19***
}
else
{
***b21***
}
}else if(b19,b22,b21 > b20,b26,b27)
{ // that means b20 is lighter
***b20***
}
else if(b19,b22,b21 == b20,b26,b27)
{ // that means left out balls where heavier
if(b23 < b24)
{
***b24***
}
else
{
***b23***
}
}
}
case(b19:b21 > b22:b24){
// same approach as case(b19:b21 < b22:b24)
}
}

}
else //if(b1:b9 == b10:b18)
{
case(b1:b9 < b10:b18){
if(b1,b2,b3,b10,b11,b12,b7,b8,b9 < b4,b5,b6 + 6 equal balls){ //b13:b18 left out
// this means b1,b2,b3,b7,b8,b9 might be ligther
if(b1:b3 < b7:b9){
if(b1 <b2)
{
***b1***
}
else if(b1 > b2)
{
***b2***
}
else(b1 == b2)
{
***b3***
}
}
else
{
// same solutiın as above
}
}else if (b1,b2,b3,b10,b11,b12,b7,b8,b9 > b4,b5,b6 + 6 equal balls){
// this means b10:b12 balls are heavier
if(b10 > b11){
***b10***
}
else if ( b10 < b11){
***b11***
}
else{
***b12***
}

}else if (b1,b2,b3,b10,b11,b12,b7,b8,b9 == b4,b5,b6 + 6 equal balls){
// this means left out balls b13:b18 are heavier
if(b13:b15 > b16:b18){
if(b13 > b14){
***b13***
}
if(b13 < b14){
***b14***
}
if(b13 == b14){
***b15***
}
}
else
{
// same solution as above
}
}

}
case(b1:b9 > b10:b18){
// same solution as above
}


}

[stalingino]

Spoiler for I can make it simple.. ans: 4 times, How..

we can get the answer by 4 measurements exactly.

divide them three groups.. A B C -- will have 9 coins each.

step 1:
A, B

step 2:
A, C

step 3: -- got x
xA, xB -- xA, xB, xC will have 3 coins each, x is answer group from steps 1,2.

step 4: -- got xx
xxA, xxB -- xxA, xxB, xxC will have 1 coin each, xx is answer group from step 3.


steps 1 and 2:
--------------

if (A > B & A > C) then
take group A as x -- odd coin is heavier

else if (A < B & A < C) then
take group A as x -- odd coin is lighter

else if (A < B & A = C) then
take group B as x -- odd coin is heavier

else if (A > B & A = C) then
take group B as x -- odd coin is lighter

else if (A = B & A < C) then
take group C as x -- odd coin is heavier

else if (A = B & A < C) then
take group C as x -- odd coin is lighter
end


step 3:
--------- by knowing coin is lighter/heavier continue this step
-- consider it is heavier

if (xA > xB) then
take group xA as xx

else if (xA < xB) then
take group xB as xx

else if (xA = xB) then
take group xC as xx

end

-- consider it is lighter

if (xA < xB) then
take group xA as xx

else if (xA > xB) then
take group xB as xx

else if (xA = xB) then
take group xC as xx

end

step 4:
-------
-- consider it is heavier

if (xxA > xxB) then
heavier coin is xxA

else if (xxA < xxB) then
heavier coin is xxB

else if (xxA = xxB) then
heavier coin is xxC

end

-- consider it is lighter

if (xxA < xxB) then
lighter coin is xxA

else if (xxA > xxB) then
lighter coin is xxB

else if (xxA = xxB) then
lighter coin is xxC

end