16
$\begingroup$

In the country of Dalgonia, there is only one type of fake coins and only one type of genuine coins.

  • All genuine coins have the same weight.
  • All fake coins have the same weight.
  • Fake coins and genuine coins have different weights
    (but it is not known which of these two weights is larger).

Furthermore, the genuine coins have the following outrageous property: whenever somebody can logically deduce that a certain coin is genuine, this coin evaporates into thin air (and disappears forever from Dalgonia).

Cosmo puts $N\ge3$ coins on the table and tells Fredo: "Exactly $N-1$ of these coins are genuine and exactly one of them is fake." Then Cosmo leaves the room. On the table, there is a balance with two pans (but there are no weights).

Question: For which values of $N\ge3$ is Fredo able to identify the fake coin and to determine whether it is heavier or lighter than the genuine coins of Dalgonia?

Improve this question
$\endgroup$
9
  • $\begingroup$ Are you asking which values of N guarantee being able to find/weigh the fake coin, or which ones it's possible for? $\endgroup$
    – Zandar
    Commented Sep 20, 2015 at 17:22
  • $\begingroup$ Does Fredo have any coins? $\endgroup$
    – Tom K.
    Commented Sep 20, 2015 at 17:45
  • 4
    $\begingroup$ The evaporation condition makes no sense because you're relying on information provided by another person that's not logically deduced. Sure you can "logically deduce" something assuming what Cosmo says is true, but then I could make all the genuine coins disappear simply by saying "they're all genuine", since you can "logically deduce" that my claim implies itself. $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Commented Sep 20, 2015 at 22:54
  • 2
    $\begingroup$ @R.. Don't you think that's being overly pedantic? $\endgroup$
    – George Reith
    Commented Sep 21, 2015 at 0:30
  • 4
    $\begingroup$ And if Cosmo knew which coins were fake and genuine, shouldn't they evaporate? $\endgroup$
    – Tom K.
    Commented Sep 21, 2015 at 6:55

5 Answers 5

Reset to default
13
$\begingroup$

You can guarantee finding and determining the weight of the fake coin for

any even $N$.

Any useful weighing will be of an even number of coins, with the same number on each side of the balance. If the result is balanced, all the coins must be genuine and so will immediately disappear. Therefore if you start with an odd number of coins, there will always be the possibility that all weighings are balanced, eliminating an even number of genuine coins each time, until only the fake coin is left. At this point the fake coin is identified, but its weight cannot be determined.

If you start with an even number of coins, put half on each side of the balance; the result must be unbalanced. Now take the heavier side and weigh individual coins against each other. Either a weighing will be unbalanced, in which case the heavier coin is the fake, or you will eliminate coins until one or none are left. If none are left, the fake is light and you can repeat the process for the lighter side.

If one coin is left, call it $H$ and take three coins $A,B,C$ from the lighter side. Weigh $HA$ vs $BC$.

  1. If it balances, all are genuine and disappear; now the fake coin must be light, and you can weigh the other coins individually until you find it or it's the only remaining coin.

  2. If $HA$ is lighter, $A$ must be fake and light.

  3. If $HA$ is heavier, all coins other than those just weighed must be genuine and disappear. $A$ cannot be light or heavy, so it too is genuine and disappears. Now weigh $B$ and $C$ against each other: either one of them will be lighter than the other and fake, or they will balance and $H$ is fake and heavy. (Thanks to Julian Rosen for resolving this case.)

Thus you can always find and determine the relative weight of the fake coin.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ If there's one coin left over from the heavy side, you weigh it against a coin from the light side, and it's heavier, then all the coins but those two vanish $\endgroup$
    – Julian Rosen
    Commented Sep 20, 2015 at 17:59
  • $\begingroup$ @JulianRosen Oops, wasn't even thinking about the other coins there. $\endgroup$
    – Zandar
    Commented Sep 20, 2015 at 18:03
  • $\begingroup$ This still doesn't work, going to have to rethink it. $\endgroup$
    – Zandar
    Commented Sep 20, 2015 at 18:33
  • 1
    $\begingroup$ In case 3, maybe you can instead weigh the two coins from the other side against each other. $\endgroup$
    – Julian Rosen
    Commented Sep 20, 2015 at 18:36
  • $\begingroup$ @JulianRosen Yeah, that works. Thanks, I was starting to think you'd need powers of 2. $\endgroup$
    – Zandar
    Commented Sep 20, 2015 at 18:45
4
$\begingroup$

It works for any $N \ge 4$.

If $N=3$ you cannot guarantee success. You must weigh only 2 coins. If the coin not measured is fake, then you will be successful since the scale will balance and those will disappear, leaving you with the fake. But if the fake is measured, then the coin not measured will disappear, leaving you with 2 coins and no reference to know which is fake.

For $N \ge 4$, the solution is as follows.

Divide the coins into two equal groups. If $N$ is odd, leave once coin out. Measure the groups against each other. There are 2 possible outcomes:

If the scales balance, all the measured coins disappear and the coin left out is fake. This can only occur when $N$ was odd.

Otherwise, one side will drop. The coin left out (if $N$ was odd) will disappear since it is known that the fake coin was measured. You are left with one set of coins which may contain a fake heavy coin, and one which may contain a fake light coin. Each group has $M \ge 2$ coins in it.

Take the heavy group and weigh two coins against each other until you run out of coins or find the heavy fake coin (you can be more efficient by weighing groups of coins, but this question doesn't ask us to minimize uses of the scale). If you run out of coins to weigh, and have none left over, then simply repeat with the light pile to find the fake light coin. If instead, you had one coin left, then you know that it might be fake and heavy, or genuine and the fake is in the light pile. This can only occur if $M \ge 3$ and odd.

Since $M \ge 3$, there are at least 3 coins in the light pile. So, use the technique by @Zandar to determine the result. Pick three coins from the light pile called $A, B,$ and $C$. The coin left over from the heavy pile is $H$. So weigh $HA$ vs $BC$. There are three possible results:

  1. $HA$ is lighter. Thus, $H$ was not a fake heavy coin and $A$ is the fake light coin.
  2. $HA$ is the same as $BC$. Again, $H$ was not a fake heavy coin and all the measured coins disappear. So, simply weight the remaining coins in the light group 1 vs 1 until you find the fake or are left with one left over (which must be fake).
  3. $HA$ is heavier. This means that either $H$ is heavy, or $B$ or $C$ are light. All other coins ($A$ and the rest of the coins in the light pile) disappear since they were genuine. So, weigh $B$ vs $C$ to see if either one was light (and fake). If not, then it was $H$.
Improve this answer
$\endgroup$
0
$\begingroup$

It is possible for any value equal to or greater than 3, assuming that you have the ability to chop the coins into pieces with infinite precision. You do not need to have coins which have an even weight distribution.

For even numbers, you divide into two groups and weigh. Set aside the lighter half as L, the heavier side as H. Now split H into two parts and weigh. If they are equal, then H will disappear and you know that the fake is lighter. If H1 and H2 are unequal, then L will disappear and you know that the fake is heavier. Continue splitting and weighing until you have two coins or one coin left.

If your second weighing showed that the fake was heavier, then the fake is the heavier of the remaining coin(s). If your second weighing showed that the fake was lighter, then the fake is the lighter of the remaining coin(s).

For odd numbers, it is possible, using deduction and limits.

Premises:

  • Coins can be split into pieces without losing material.
  • Coins can be weighed relative to themselves without proving anything. If I split a coin into pieces, I can continue adjusting the split until I have evenly divided the coin, and none of this causes the coin to disappear.

So, take all the coins and then weight 2v1 until you have weighed every single combination of coins. If at any point 1 is heavier than 2, then all other coins will disappear and you know which coin is fake and that it's heavier.

Okay, now what if you don't find the fake? Split every coin into two equal parts (by weight), keeping track of which coins parts belong to which coin. Now weigh two halves of one coin against three halves of other coins until you have tested all combinations. If at any point a coin is heavier than its opposition, then the fake will be revealed and known to be heavier.

So what we have now is a formula of N-1/N, where N is the number of pieces we've split each coin into. Take the limit as N approaches infinity and we have 1, which represents equality of weight, which is not possible. So, for any given threshold of measurement, we can either find the fake and know it's heavier or find nothing and prove that the fake is lighter.

The key here is that any standard of accuracy is reachable, if we have a great deal of patience. In fact, if we know the standard of accuracy in advance, we can simply chop the coins into sufficiently-small pieces and do one round of weighings.

Knowing that fake is lighter (if it were heavier we would have found it), we can solve for an odd number of coins. Weigh the coins 1v1 until you have a single coin left standing. That coin is the fake, and you know it's lighter. For higher values, you can be more efficient by weighing larger piles against each other, but the end result is that you can narrow it down to 1 coin, and then you win.

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

N=3, N-1=2. There are 2 real coins and 1 fake coin. The 2 real coins will balance against each other and the other one is fake. This process will hold true for all values of N where N is greater than or equal to 3.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is the same as Trenin's and Mateen Ulhaq's answers. It doesn't work because although you can identify the fake coin, you can't always determine whether it is light or heavy. $\endgroup$
    – f''
    Commented Nov 1, 2015 at 2:10
-1
$\begingroup$

Odd $N$

Mark all the coins with $c_1, c_2,\ldots,c_N$.

Pick one coin, $c_k$. Weigh all other coins on the balance, putting half on either side.

  • If the balance is equal, $c_k$ is fake.
  • If the balance is unbalanced, $c_k$ is genuine and we have reduced our problem to even $N\geq 2$
Improve this answer
$\endgroup$
5
  • $\begingroup$ Doesn't work. You have no reference if it's lighter or heavier - you need to know that alongside which is the fake. $\endgroup$
    – Tim Couwelier
    Commented Sep 21, 2015 at 6:29
  • $\begingroup$ @TimCouwelier As long as every genuine coin has the same weight $w_g$, it doesn't matter what the weight of the fake coin $w_f$ is so long as $w_g \neq w_f$. In the context of this problem, if the scale is perfectly balanced with an equal number of coins on either side, all coins on the scale must be genuine. Thus, they all disappear and you are left with $c_k$, your fake coin. $\endgroup$
    – Mateen Ulhaq
    Commented Sep 21, 2015 at 6:35
  • $\begingroup$ @MateenUlhaq problem is, that op wants to know which coin is heavier or lighter. (: $\endgroup$
    – Tom K.
    Commented Sep 21, 2015 at 6:41
  • $\begingroup$ Nevermind; this doesn't work anyways since our chosen $c_k$ genuine coins disappear and we are left with an even $N$. $\endgroup$
    – Mateen Ulhaq
    Commented Sep 21, 2015 at 6:43
  • 1
    $\begingroup$ -1, the question was and to determine whether it is heavier or lighter than the genuine coins which is impossible to tell in your first scenario $\endgroup$
    – Novarg
    Commented Sep 21, 2015 at 13:46

Your Answer

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

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