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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Followup: do the same with $13$ coins. After that, try $40$. $\endgroup$
    – Mike Earnest
    May 27, 2015 at 9:50

3 Answers 3

Reset to default
15
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm afraid this is not the best result you can reach! ;) $\endgroup$
    – Hunter
    May 27, 2015 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, 2015 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, 2015 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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