8
$\begingroup$

Follow up question to my other question, but totally different methodology required.

You are given 99 coins which consists of 30 fake ones. You also have a digital balance scale with perfect precision that shows how much difference between weighs you put on. For example, if you put 10 g on the left side and 20 g on the other side, it will show -10, otherwise +10.

  • You know that all genuine coins have the same weight but you do not know their weights.
  • You also know that every fake coin could be heavier or lighter by 1 gram than a genuine coin. So Some fake coins could be 1 gram lighter and some other fake coins could be 1 gram heavier than genuine coins
  • The weight of genuine coin is integer valued.

So,

What is the minimum amount of weighing which guarantees to tell whether if any coin you choose is a fake or not?

In other words, you will choose a coin you want; after weighings you are going to tell that if that coin is a fake or not for sure. That's the aim of the question. The coin you choose could be a fake or genuine, it doesnt matter.

$\endgroup$
  • 1
    $\begingroup$ I see a contradiction in the definition. One one hand, you state if any coin you *choose* is fake or not, on the other choose any coin *after weighings*. So what is the goal: to determine if a chosen coin is fake (coin choice before weighing procedure) or to determine which coin is fake (coin choice after procedure/determine every coin)? $\endgroup$ – George Menoutis Nov 1 at 10:03
13
$\begingroup$

You only need

One weighing.

Assume the genuine coins weigh $x$ grammes.

Weigh all the coins besides the one you picked. If you picked a fake coin, your result will be one of $\{ 98x - 29$, $98 x - 27, \ldots, 98x + 29 \}$. If you picked a genuine coin, your result will be one of $\{ 98x - 30, 98x - 28, \ldots, 98x + 30 \}$. The remainder modulo $2$ of your weighing determines whether your coin was fake (odd remainder) or genuine (even remainder).

Credit to Hexomino and Jaap for the corrections!

$\endgroup$
  • 3
    $\begingroup$ Do you mean 98 instead of 99 since we are removing one? $\endgroup$ – hexomino Nov 1 at 12:58
  • $\begingroup$ @hexomino That's a good point! $\endgroup$ – Alexander Geldhof Nov 1 at 13:00
  • 5
    $\begingroup$ And since $98$ is even, you now don't even need to do the mod 98 operation. $\endgroup$ – Jaap Scherphuis Nov 1 at 13:02
2
$\begingroup$

The number of weighings will be:

Simply $2$ weighings.

What will you do is to:

Put all coins on one side and you will know not only the total weights...
But also the weight of a single genuine coin!

Mathematically speaking:

Let's say the weight of a genuine coin is $x$ grams, which means the fake one will be either $x-1$ or $x+1$ grams. The total weights of all $99$ coins will be between $99x - 30$ and $99x + 30$ grams.

If you divide this number by $99$, you will get between $x - 0.303$ and $x + 0.303$ grams, which means if you round this to the nearest integer, you will always get the $x$ i.e. $x = round(\frac{sum}{99})$.

So the next step is:

Simply weight a coin. If it's $x$ grams then it's genuine; otherwise, it's fake. We can claim the status of this coin.

$\endgroup$
  • $\begingroup$ I think you are supposed to do all the weighings before deciding which coin to ask about. In other words, the question is asking how many weighings it takes to determine which coins are fake. $\endgroup$ – Gareth McCaughan Nov 1 at 10:59
  • 4
    $\begingroup$ Also, note that unless I understood the question incorrectly, the fake coins need not be the same weight - you may have 15 coins which are lighter and 15 which are heavier which will just give you 99x $\endgroup$ – Lolgast Nov 1 at 11:41
  • $\begingroup$ If I wasn't mistakenly understand the question, this strategy will work. Yes I'll do all the weighings, and then simply pick the coin on my last step to be announced whether it's genuine or not. (It's not determining every fake coins, but determine a single chosen coin, whether it's fake or not.) And no issue at all for how many lighter and heavier. The $\pm$ sign actually denotes any values between the two, not just either two values. $\endgroup$ – athin Nov 1 at 12:34
  • $\begingroup$ The question has been edited to say that the genuine coins have integer weight. $\endgroup$ – Jaap Scherphuis Nov 1 at 12:56
  • $\begingroup$ @JaapScherphuis Yes, just saw that, this strategy seems fine now. $\endgroup$ – hexomino Nov 1 at 12:57
0
$\begingroup$

30 weighings. Minimum (if you somehow luckily weigh all 30 fake coins first you can determine them to all to be fake) The minimum weight of a fake coin is always 1gram lighter, the maximum weight of a fake coin is always 1gram heavier. Hence a comparison of 2 fake coins will always be 2 grams. Once the fake minimum, and fake maximum are determined the solution can possibly be 30 weighings.

64.5 weighings. Average

99 weighings. Maximum (if you are unlucky and weigh the 30th fake coin last)

$\endgroup$
  • 3
    $\begingroup$ Your answer disagrees with the two answers posted before yours, but you don't comment on why you think those answers are incorrect. Also, I think you are misunderstanding the question - the goal is to be able to identify a single coin as fake or real, and your answer appears to be trying to do more than that. $\endgroup$ – Rob Watts Nov 1 at 19:41

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.