37
$\begingroup$

In the country Curgonia, there are many types of fake coins and only a single type of genuine coins. The weights of these coins satisfy the following conditions:

  • All genuine coins have the same weight
  • Every fake coin is heavier than any genuine coin
  • No two fake coins have the same weight

Cosmo puts 100 coins on the table and tells Fredo: "Thirty of these coins are genuine and seventy of them are fake." Then Cosmo leaves the room. On the table, there is a balance with two pans (but there are no weights).

Question: What is the smallest possible number of weighings that guarantee Fredo to identify at least one genuine coin?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ I'm probably reading into this too much. When you say "all fake coins have different weights" - does that mean no two fake coins have the same weight or just that generally some are higher, some are lower, some are the same. $\endgroup$
    – DoubleDouble
    Commented Sep 18, 2015 at 15:12
  • 5
    $\begingroup$ @DoubleDouble: The coins on the table have 71 pairwise distinct weights. The smallest of these weights belongs to the genuine coins, and the 70 larger weights belong to the 70 fake coins. $\endgroup$
    – Gamow
    Commented Sep 18, 2015 at 15:15
  • 1
    $\begingroup$ Does the weight of fake coins follow the distribution $$Y = aX + b$$, b being the weight of a genuine coin and a being the sequence number of the fake coin when being ordered from lightest to heaviest? In other words: do fake coins gain weight linearly or randomly? $\endgroup$
    – Nzall
    Commented Sep 18, 2015 at 16:24
  • 6
    $\begingroup$ @Nate Kerkhofs: nothing is known about the weight distribution, except what is written in the problem statement $\endgroup$
    – Gamow
    Commented Sep 18, 2015 at 16:27
  • $\begingroup$ What if Cosmo handed Fredo one genuine coin before he walked out? $\endgroup$
    – Justin
    Commented Sep 18, 2015 at 17:28

9 Answers 9

Reset to default
23
$\begingroup$

As many have already stated, the best you can do is

seventy weighings.

Suppose the genuine coins have weight 0, and the other coins have weights of distinct powers of two. Then any try on the old balance will always just tip the scale to the side of the heaviest fake coin, since it weighs more than all the other coins on the scale put together.

Now suppose the scale somehow magically marked the heaviest coin on the scale with a big red X everytime you weighed some coins. Now, there is no use using the coin with an X again. Also, you've learned absolutely nothing about the other coins. Hence, even with this extra magic, the only information you can gain each time is to eliminate one coin as being fake. Thus, it takes in the worst case seventy weighings to eliminate all the fake coins and find at least one genuine one.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ This is the clearest explanation of why you can't succeed with fewer weighings. $\endgroup$
    – user3294068
    Commented Sep 18, 2015 at 17:39
  • 2
    $\begingroup$ But worst case also finds all good coins. So you've got that going for you, which is nice. $\endgroup$
    – Kevin
    Commented Sep 18, 2015 at 18:51
  • $\begingroup$ Does the problem statement allow for genuine coins of weight zero, or were you just trying to avoid having an extra "+30" term everywhere? $\endgroup$
    – Kevin
    Commented Sep 20, 2015 at 1:47
  • 3
    $\begingroup$ Your argument is physically impossible; "coins" with weights that are 70 distinct powers of 2 cannot exist, and most certainly cannot fit on a scale without the smallest ones (not "coins") being just a few atoms in size. $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Commented Sep 21, 2015 at 4:40
  • 2
    $\begingroup$ $2^{70} \approx 10^{21}$, so if the lightest fake coin weighed 1 gram, the heaviest would weigh about $10^{18}$ kg, which is about 1/millionth of the weight of the Earth. All the real coins could weigh 30 mg, and they'd still add up to less than the lightest fake. Awkward, yes, utterly impractical, yes, but not completely impossible. $\endgroup$
    – user3294068
    Commented Apr 4, 2016 at 17:57
9
$\begingroup$

Hm...

The obvious strategy is

every time, weighing the lightest coin you get against an unused coin

for a worst case of

70 weighings.

I'm not sure if there's way to improve that by weighing multiple coins against each other at once instead of just having one on each pan - it doesn't seem likely to me because one fake coin and one real can weigh more than two fakes, but it's still possible that you could improve this.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ How do you get 60? 50 weighings first + 25 weighings second and you're maybe still not there? $\endgroup$
    – Dr Xorile
    Commented Sep 18, 2015 at 16:38
  • 1
    $\begingroup$ I don't think the average case is improved in your second strategy. Weighing any two coins in the not-proved-fake pile is exactly equivalent to weighing any other two coins, regardless of whether you've weighed them before. Also, your first strategy only requires 70 weighings. $\endgroup$
    – Zandar
    Commented Sep 18, 2015 at 17:14
  • $\begingroup$ @Zandar: Oh, duh. I'll fix it. $\endgroup$
    – Deusovi ♦
    Commented Sep 18, 2015 at 17:16
  • $\begingroup$ Also $100/4<30$. $\endgroup$
    – Dr Xorile
    Commented Sep 18, 2015 at 17:54
5
$\begingroup$

The smallest possible number of weighings that guarantee a genuine coin is

70

Let's consider the information we get from each type of weighing.

If we weigh one coin against another, an even weighing tells us that both coins are good, whereas an uneven weighing tells us only that the heavier coin is fake.

If we weigh multiple coins against each other, an even result tells us nothing unless we know that we have a group with only two fake coins; if we have three, we have the possibility of two fake coins on one side weighing the same as a fake and a genuine coin on the other. An uneven result tells us only that the heavier side has at least one fake coin.

It should be obvious that weighing multiple coins gives less information in all cases unless we already have a group with only two fake coins (at which point an uneven weighing would still not identify a genuine coin). The best strategy is then to weigh single coins against each other. If the weights are even, we have found a good coin; if not, we eliminate a fake coin. In the worst case, all weighings will be uneven, in which case we will need 70 weighings to identify a genuine coin.

Note that it makes no difference which coins we weigh, as long as we set the heavier coin aside each time; we could continue to weigh the lighter coin against a new coin each time, or weigh 71 coins in a "tournament", or just take random coins for each weighing. This is because an uneven weighing provides absolutely no information about the lighter coin, so the only thing that changes about our situation after the first weighing is that we effectively have 99 coins, of which 69 are fake. The only point at which a genuine coin will be identified in the worst case is after all the fake ones have been eliminated, at which point all the remaining ones will be genuine by default.

Improve this answer
$\endgroup$
0
2
$\begingroup$

The minimum possible number of weighings is:

71

If we have 70 fake coins and 30 real coins, and we want to pair them one by one, then we need to guarantee a case where the scale is balanced in order to win. If we make 50 comparisons among the 100 coins AND THEN discard the heavy coins, we'll be left with 50 of the lighter coins. Note that among these 50 light coins, 30 are guaranteed to be the genuine coins. If we perform 21 comparisons, we guarantee that all of the fake coins have been paired up with a real coins, and been discarded for being too heavy, so the last pair MUST contain a real coin. This means we have the initial 50 comparisons, then an extra 21, yielding 71.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ The final weighing is not necessary if you keep discarding the fakes up to 70 times, the remaining coins are known to be genuine. $\endgroup$
    – Arkku
    Commented Sep 18, 2015 at 20:12
  • $\begingroup$ You're right, it's not a necessary weighing. Thanks $\endgroup$
    – nietsnegttiw
    Commented Sep 18, 2015 at 20:26
  • $\begingroup$ @RossMillikan I don't understand what you mean when you say "there are eight coins that have not been on the balance a second time." If all fakes are of a unique weight, I don't understand how the number of cases where things balance could exceed one. $\endgroup$
    – nietsnegttiw
    Commented Sep 21, 2015 at 13:51
  • $\begingroup$ I had misread the problem and thought we had to find all the good ones. You are right. $\endgroup$
    – Ross Millikan
    Commented Sep 21, 2015 at 13:53
2
$\begingroup$

Weighing multiple coins gives us no real information because there are no bounds on how much more the fake coins weigh. Weighing one pair tells us only that (1) both are the same and both are real, or (2) the heavier coin is fake and can be eliminated from the pool of candidates.

Worst case, 70 weighings will eliminate 70 fakes and all the rest are real (tho most likely a pair of reals would be found earlier).

Note than any solution must access (weigh at least once) a minimum of 71 coins, to be sure that at least one real coin has been considered. 70 weighings can do this (for example, just compare the lighter of each weighing with the next coin from the pool of unweighed ones; after 70 compares you have tested 71 coins).

I have not yet found any way to make use of the number of real coins. This answer is the same whether there are 70 fake + 1 real, or 70 fake + 1000 real - just do 70 compares of any type and each time eliminate the heavier one from the pool (or both are real if equal). If there is any way to beat 70 compares, it's going to have to infer some information from the number of real coins, but I'm not finding any way to do that.

edit: oops, I had a bad answer which somebody commented on while I was (immediately) revising it - ignore that first comment if it makes no sense, it was my blunder.

Improve this answer
$\endgroup$
1
  • $\begingroup$ What if it turns out you have compared a real and a fake 30 times, and two fakes 5 times? Then the remaining coins are all fake. $\endgroup$
    – 2012rcampion
    Commented Sep 18, 2015 at 16:56
1
$\begingroup$

I'll do a baseline of

10 weighings

My strategy is to essentially find the lightest coin. Split the coins into a group of 64, a group of 8, and a group of 28 ignored. This guarantees at least 1 legit coin is part of the group.
Do a binary comparison for each group to find the lightest coin. Then compare the coins. The lightest(s) are genuine.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ Binary comparison might not work. From the group of eight, assuming the lightest coin has weight $1$, you end up with a first weighing of $1+4+6+8$ vs. $2+3+5+9$. $\endgroup$
    – Marconius
    Commented Sep 18, 2015 at 14:42
  • 1
    $\begingroup$ This doesn't necessarily work - say real coins weigh 1 unit. If you're weighing 4v4, it could be 2 3 4 5 vs 1 1 1 20, and you'd mistakenly think the real coin is in the 2345 group. $\endgroup$
    – Deusovi ♦
    Commented Sep 18, 2015 at 14:43
  • $\begingroup$ Bah, that did occur to me right after I posted. I'll try to see how to work around that (fakes < real+fake) $\endgroup$
    – JonTheMon
    Commented Sep 18, 2015 at 14:56
  • $\begingroup$ You should edit the answer to explain when it does and does not work. As it stands, it is incorrect. $\endgroup$
    – tucuxi
    Commented Sep 21, 2015 at 0:09
0
$\begingroup$

Here's my two cents.

Step 1

Split the coins into two groups. One group should be 71 coins, and in the other, 29 coins.

Step 2

Since we know that the group containing 71 coins has at least one genuine coin. And we know that the genuine coin is the lightermost of them all. So we begin by placing one two coins randomly on the scale and place away the heavier one for each weigh. This way we will have to make a total of 70 weighs to make sure all coins have been weighed and we have the lightermost of them all. This is the genuine coin. If we ever get two coins of the same mass any time in the weighing process we stop there. Both of these coins are genuine.

Improve this answer
$\endgroup$
0
$\begingroup$

The only information that any given weighing (of equal number of coins) reveals to us:

  • If pans are equal, either both or none of the pans have fake coins.
  • If pans are unequal, either one or both of the pans have fake coins.

We also notice that finding actual weights of coins in terms of other coins is pointless, since we might end up with equations like $Fake\ coin\ 1 \geq 200 \times Fake\ coin\ 2$. The only that seems of practical importance is sorting the coins relatively (in ascending/descending order).

Let's make the assumption that equal pans always means no fake coins in the given scenario. (There exist no two sets of fake coins with equal weights.) However, we will not know this. So even if we stumble upon two equal pans, we will repeatedly use different weighings till we conclude that there is no fake coin. This can take a long time. This also means that the fact as to which pan is greater is of no importance, once we know we have unequal pans.

According to worst case, we will never get equal pans unless this is logically implied from previous facts (in which case, weighing them is pointless).

Hence we can conclude that we will never get equal pans in our perfect strategy under the worst case.

If pans are unequal, we gain no new information.

Hence, we conclude that it most be possible to achieve a state where it is logically implied that a particular coin is genuine, without us ever getting equal pans in our weighings.

This only seems possible by doing $70$ weighings, as others have said.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think you need to reread the question. If pans are equal, they are both real. $\endgroup$
    – Kevin
    Commented Sep 18, 2015 at 18:40
  • $\begingroup$ Guess I needed to reread your answer, you were talking about weighing multiple coins on each pan. $\endgroup$
    – Kevin
    Commented Sep 18, 2015 at 18:41
  • $\begingroup$ Why 71? If it is known that there are only 70 fake coins, once all have been identified (in the worst case), there is no need to weigh anymore since it was given that the rest are all genuine (the goal was to identify a genuine coin, not to weigh it). $\endgroup$
    – Arkku
    Commented Sep 18, 2015 at 20:06
  • $\begingroup$ @Arkku You're right. I meant 70. $\endgroup$
    – ghosts_in_the_code
    Commented Sep 20, 2015 at 15:00
0
$\begingroup$

Minimum 1 weight (best case) when you find two coins with the same weight.

Worst case 70 comparisons (worst case) if you have to weight all the wrong ones.

Edit: If you're lucky enough to weight two coins that weights the same (good ones are all equal and fake ones are all different) then you resolved the problem. Each time you weight you just have to make sure to grab the lighter one. If you're unlucky enough to get 70 times the balance unbalanced, you will remain with the 29 other genuine coins.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Please explain why. $\endgroup$
    – Bob
    Commented Sep 20, 2015 at 16:08
  • $\begingroup$ I edited the comment to clarify. Sorry for not explaining earlier Bob. $\endgroup$
    – Jesus Arias Ávila
    Commented Sep 20, 2015 at 22:24

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