13
$\begingroup$

We are given ten stacks of three coins. All the three coins in one of the stacks are counterfeit. A true coin weights a whole number of grams. A false coin differs in weight from a true coin by less than 3.6 grams.

We have a digital scale. How can you identify the counterfeit stack with two weighings?

Link source: https://books.google.com/books?id=qwwEZmt6upUC&printsec=frontcover&hl=ru&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false

$\endgroup$
  • $\begingroup$ Do all false coins have the same weight? Could this weight (in grams) still be an integer? $\endgroup$ – Arnaud Mortier Jun 18 at 20:42
  • $\begingroup$ All false coins have the same weight. It can be an integer. $\endgroup$ – student28 Jun 18 at 20:47
  • $\begingroup$ Do we know the weight of the real coins at the beginning? $\endgroup$ – hexomino Jun 18 at 20:49
  • $\begingroup$ No, we don't know it. $\endgroup$ – student28 Jun 18 at 20:56
  • 1
    $\begingroup$ Wow, this seems almost impossible (or, more likely, I'm not very smart). With a single weigh, even if we know the weight of a real coin, we can find the fake stack from at most two stacks (put a coin from one of the stacks and see if it weighs as much as a real coin). Obviously the answer has something to do with weighing different amount of coins from different stacks, but I still feel like I'm missing something. $\endgroup$ – shoopi Jun 18 at 21:11
9
$\begingroup$

Ok, found something that seems to work.

First, weigh this many coins from each stack:

 Stack    A B C D E F G H I J
 Round 1: 3 3 3 3 2 2 1 1 0 0

There are two possible outcomes. I we're lucky,

the result is a multiple of 18 grams, all the weighed coins are genuine, and the fakes are in one of the remaining two stacks. Since we now know the weight of a genuine coin (result divided by 18), we can weigh one coin from stack I to identify which one is the fake stack.

If we weren't so lucky, we know that I and J stacks are genuine, and we'll next weigh these coins:

 Stack    A B C D E F G H I J
 Round 1: 3 3 3 3 2 2 1 1 0 0
 Round 2: 0 1 2 3 1 3 2 3 3 0

This should uniquely identify the fake stack:

Calculate the distance from the multiple of 18 that is nearest both cases.
Then compare the cases, and see what happened to the error:

* Vanished: A is fake
* went to one third: B is fake
* went to two thirds: C is fake
* no change: D is fake
* was halved: E is fake
* increased by 50%: F is fake
* doubled: G is fake
* tripled: H is fake

Finally, we need to rule out overlap, because we weighed fewer than 22 coins. (The maximum possible error is 10.8g, so the nearest multiple of 22 would have been uniquely defined.) So we need to figure out if there are any particular numerical combinations that would allow misinterpretation.

The cases that would be easiest to confuse with each other are "went to two thirds" and "increased by 50%". (Sorry for pulling this out of a hat, don't have the time for a rigorous argument now.) If the F coins were exactly 3.6 grams too light, we'd get a "10.8 grams to 7.2 grams below a multiple of 18", which could also be interpreted as the "7.2 grams to 10.8 grams above a multiple of 18" which would mean that C coins were exactly 3.6 grams too heavy.

Since the fakes are guaranteed to be less than 3.6 grams off the regular weight, this is not a problem. (TODO: rigorously check that the rest of the cases would require an even bigger weight difference for the fakes. EDIT: maybe tossing in the J coins for the second weighing would help, too.)

$\endgroup$
  • $\begingroup$ @hexomino oh yes, you are correct, had to run, so didn't have the time to proofread anything. $\endgroup$ – Bass Jun 19 at 8:53
  • $\begingroup$ Yes, I understand that feeling. This is a very elegant solution, I was wracking my brain last night trying to figure out which combination of coins could work and why 3.6 was important but this explains it very nicely. $\endgroup$ – hexomino Jun 19 at 8:57
2
$\begingroup$

There are multiple variations that can be done because we can exclude a lot from any of the 2 weightings.

My logical approach:

We put 3 coins from 3 lots, 2 from next 3, 1 from next 3 and none from the last.

Round 1 Stacking: A:3 B:3 C:3 D:2 E:2 F:2 G:1 H:1 I:1 J:0

By the weight difference we can determine if the cheating is on ABC, DEF, GHI or J (happy case, 1st try)

Round 2 Stacking: We put 3 coins from the 1st remaining lot (A, D or G), 2 from the second (B, E or H) and one from the last lot (C, F or I).

Now we again have a weight difference that determines the number of cheated coins, therefore the stack it belongs to.

$\endgroup$
  • $\begingroup$ This method seems to rely on knowing the exact weight difference, but we don't, we only know that the weight difference is less than 3.6 grams. $\endgroup$ – Bass Jun 23 at 5:48

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.