Oyeah! Part3

Computer Science Level 2

You have 7 coins that look identical. But, one of them is different than the others. This different one is either heavier or lighter than the rest, which all have the same weight. You also have a two-pan balance that can tell which side is heavier.

What is the minimum time of scaling you have to do in order to determine the unique coin?

4 3 2 5 7 6

1 solution

André Vicente Milack
Jan 23, 2015

Let the coins be A, B, C, D, E, F and G.

if (A + B == C + D)
    if (E == F) return G;
    else
        if (E == G) return F;
        else return E;
else
    if (A == B)
        if (A == C) return D;
        else return C;
    else
        if (A == C) return B;
        else return A;

I think the answer should be 2 if we're clever

1) First pass: 7 coins ABCDEFG

ABC on one side of the scale, DEF on the other

case ABC : ABC weighs down,

2.1) place A on one side of scale, B on the other

case A: side A weighs down, A is the odd coin out, 2 weighs case B: side B weighs down, B is the odd coin out, 2 weighs case C: scale balances, C is the odd coin out, 2 weighs

case DEF: DEF weighs down,

2.2) place D on one side of the scale, E on the other

case D: side D weighs down, D is the odd coin out, 2 weighs case E: side E weighs down, E is the odd coin out, 2 weighs case F: scale balances, F is the odd coin out, 2 weighs

case G: scale balances on first pass, G is the odd coin out, 1 weigh

we must conclude then that worst case, the minimum is 2 and best case, the minimum is 1.

Matt Tough - 6 years, 3 months ago

Matt, I think your answer would be proper if we knew beforehand that the odd coin is 'heavier' than the others. But in this case, we only know that the odd coin is 'different', which might be heavier or lighter. So for example, when you put ABC on one plate and DEF on the other and ABC weighs down, we can only deduce that G is a regular coin, but we cannot tell if the odd one belongs to ABC or DEF.

André Vicente Milack - 6 years, 3 months ago

I See your logic but It is situational. If you put 3x3 and it is equal than you know the odd one is the one not weighed. You then for good measure(to determine if heavier or lighter) weigh the 7th coin vs one that has already been determined to be the equal of the rest and you'll know if it is heavier or lighter. 2 is absolutely a possibility. Your answer is assuming the odd coin makes it onto the scale 1st pass

michael bye - 6 years, 1 month ago

@Michael Bye – Michael, you don't need to determine if the odd coin is heavier or lighter, you just need to find it. You're right, two measures is a possibility, even one measure is a possibility, as you have demonstrated yourself. But my answer doesn't assume anything, it remains open for every possibility. You give me the seven coins, and before I even touch them I can guarantee that I will find the unique coin with 3 measures at most. I couldn't tell you the same with 2 measures, because there is a chance that I will need the third measure, even using the most efficient algorithm.

André Vicente Milack - 6 years ago

@André Vicente Milack – Thanks for the response. I definitely see your logic. i think the way it is worded could use some cleaning up. as you said in another response. "If you're given the seven coins, how many times will you need to use the balance so that you 'guarantee' to find the different one?". would be a bit easier to understand what you are truly looking for.

michael bye - 6 years ago

I don't get the question. The minimum amount is 1, no? If you're lucky the first time when you weigh 3 and 3 coins and they have the same weight.

stefaan vande walle - 6 years, 4 months ago

You're right, but I think the real meaning of the question is: "If you're given the seven coins, how many times will you need to use the balance so that you 'guarantee' to find the different one?".

André Vicente Milack - 6 years, 3 months ago

12 coins will also give the same result though

Clark Makmur - 6 years, 4 months ago

I see it would be possible to extend this algorithm for 8 coins keeping the number of comparisons. But I can't see how that could be possible for 12. Could you explain it?

André Vicente Milack - 6 years, 4 months ago

Oyeah! Part3

1 solution

0 pending reports