7
$\begingroup$

Someone gives you 4 apparently identical golden coins.

You know that among them there could be exactly one fake coin, and that a fake coin hasn't the same weight of a golden one.

In your pocket you have a fifth - surely genuine - golden coin, and in front of you a balance with two pans.

What is the minimum number of weighings to determine if there is a fake coin between the four you've been given, and if it's heavier or lighter than a golden one?

$\endgroup$
  • $\begingroup$ Followup: do the same with $13$ coins. After that, try $40$. $\endgroup$ – Mike Earnest May 27 '15 at 9:50
14
$\begingroup$

How many weighings you need:

2

Call the four coins A,B,C and D, and the true gold coin G. You start by weighing

AB | CG

  1. If this balances, then it is only possible that D is defective. Weigh D against G to find out for sure.

  2. If it tips towards AB, there are three possibilities: either A or B is heavy, or C is light. To figure out which one, weigh A against B. If they don't balance, you learned which of them was heavier. If they do balance, you learn C was light.

  3. If it tips toward CG, this is very similar to the previous case. Just switch the words "heavy" and "light" in that paragraph.

Furthermore, it can't be done in just one weighing. There are nine possible situations (each coin could be heavy or light, or all could be same), and a weighing has only three outcomes. By the pigeonhole principle, there will be some outcome which would result from from two different situations, so a weighing could not distinguish between those situations.

$\endgroup$
  • $\begingroup$ if A and B dont balance we can conclude which one is heavier but how would you conclude which one is fake ? fake coin could be either heavy or light than original. $\endgroup$ – Karan Thakkar May 27 '15 at 9:31
  • 1
    $\begingroup$ @karanthakkar Using what we had learned before. For example, if the first weighing tipped toward AB, then we knew it was impossible that either A or B was light, so if A and B don't balance, we know one was heavier. $\endgroup$ – Mike Earnest May 27 '15 at 9:33
1
$\begingroup$

For four coins, you only need one weighing to detect the presence of a fake. Two in each pan, simple.

To identify the coin, and determine if heavier, two more weighings are required. A directed state graph is not necessary.

  1. arbitrarily empty a pan, divide the remaining coins and weigh.

Are they of equal weight ? If yes:

  1. select one of the other two coins and test it against the pocket coin.

If no:

  1. select the heavy coin and test it against the pocket coin.

If they are the same weight then the lighter coin was fake.

Three in total to determine the fake, and tell if it is lighter.

$\endgroup$
  • $\begingroup$ I'm afraid this is not the best result you can reach! ;) $\endgroup$ – Hunter May 27 '15 at 12:15
  • $\begingroup$ This would work only if you knew the fake coin is heavy or light. But because you don't know, you will only learn that the scales are uneven, which you already knew. $\endgroup$ – Zikato May 27 '15 at 12:30
  • $\begingroup$ No, we don't know that there is a fake. Consider having to do this for hundreds of packets of for coins, day in, day out. Consider too that maybe only 10% of coin packs have a fake. Perhaps it costs $100 for each use of the scale ? In any case OP asks for detection first, and then identification and classification after that. Minimum weighing as asked in the OP to "detect" is one. The question should otherwise lose a comma and embolden the follwing "and". ...been given and if it's heavier or lighter $\endgroup$ – mckenzm May 30 '15 at 1:38
0
$\begingroup$

Straight answer would be

1 to 4 times


1)You put the fifth coin on one end, and then put each coin in turn on the other pan. The one that's different in weight is the fake coin.


2)If you are lucky, the first one you put on would be the fake. If not, you'll need to weight each one in turn.


The question didn't ask for the minimum number of time to use the balance. :p

$\endgroup$
  • $\begingroup$ Correct, I'll edit my question! ;) $\endgroup$ – Hunter May 27 '15 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.