Another coins weighing puzzle

Question

In a bank safe deposit box 80 identical coins can be found, of which 2 or 3 are fake.

Jason knows that there are 3 fake coins and has also identified them.

He is challenged to prove it to his friends Christian and Mary, who both know that the fake coins are 2 or 3 and, in addition, know that each fake coins weigh 1 gram less than the genuine ones.

Jason can use a balance scale to perform as many weighings as he likes, but without giving away the identity (fake/genuine) of any coin, at any stage in the process.

Which are the optimum number of weighings that Jason must do so as to prove to his friends that the fake coins are exactly 3? No tricks are allowed :)

To clarify, there is no limitation in the number of weighings; Jason can do as many as he wants (we are not necessarily looking for the minimum number).

Below are my thoughts: Jason randomly picks 64 coins and weighs 32 against the other 32.

We have the following cases:

1. The scale balances, so we have either 0+0 (all are genuine) or 1+1. In this case, we again split them into two groups 16+16 and weight one against the other. If they balance, we are in the case of 0+0. Otherwise we have 1+1. So we know we have at least 2 fake coins. Then we need to prove that in the remaining 16 coins there is 1 more fake.
2. The scale does not balance. We either have 0+1, or 0+2 or 0+3 or 1+2 (in any order). We take the lighter group and split them into 16+16. If the scale balances, we are in one of the first 3 cases. We then know that the second group contains from 1 to 3 fake. Then we take the 2nd group and split it into 16+16. Again we have the following cases: 1-0, 1+1, 2+0, 3+0, 1+2. If the scale balances, we know we have 1+1. Then we need to prove that in the remaining 16 coins there is 1 more fake.
3. If it does not, we take the heavier and split it into 8+8. If the scale balances, we know we have 0+0 fake so we are in one of the cases 1+0, 2+0 or 3+0. We then take the lighter (for which we know it contains 1 or 2 or 3 fake) and split it into 8+8. We again have 5 cases: 1-0, 1+1, 2+0, 3+0, 1+2.

If the scale does not balance, we have 1+2 (so we know for sure we have >2 fake).

We continue with the remaining cases and then do the same with the 16 coins.

Will this work? Can anyone provide a complete solution?

Answer 1

Here is a simple solution that works. There are many combinations that you can use. The idea is to make sure you are always making 3 such groups and weighing them against each another so that all of them balance. Also any transfer should be done in a way that you cannot tell whether you transferred a fake or a real.

Jason makes 6 groups as below (there are many more possible solutions as you can understand after reading through my solution) -

G1 = 20 coins, G2 = 20 coins, G3 = 20 coins

G4 = 7 coins (1 fake coin), G5 = 7 coins (1 fake coin), G6 = 6 coins (1 fake coin)

He weighs G1 against G2 and G2 against G3. This shows to Mary and Christian that either G1, G2 and G3 all have 1 fake each or none of them have any fake.

Now Jason transfers 1 coin from G1 to G4, 1 from G2 to G5 and 2 from G3 to G6 (he can also take 2,2,3 or 3,3,4 or other counts as well making sure G4, G5 and G6 have equal number of coins after transfer).

So G4, G5 and G6 all have 8 coins each now after the transfer. Now he weighs G4 against G5 and G5 against G6. They all balance. This shows Mary and Christian that there are 3 fake coins as they know there are either 2 or 3 (they know zero or another multiple of 3 is not an option).

But what they cannot tell whether the fake coins were there in G4, G5 and G6 from before or the transferred coins were fake or fake one's are still in G1, G2 and G3.

I hope it is clear. Let me know if any questions.

Answer 2

Assumption: the scales do not make any measurements; they can only be used to show one given pile is heavier than another.

Assumption 2: all of the coins are identifiable (numbered, say) throughout the whole process (so "random" doesn't make sense).

Assumption 3: Based on a below comment by Harry, I take "can't reveal the identity of any coin" to mean he loses if C&M can figure out if some coin is genuine or fake.

First, I'll write a quick proof of the easy case, which contrasts with the difficulty that comes into it in the complementary case.

---

Easy case: The total number of coins, $N$, satisfies $N \in 3\mathbb N + 3 = \{6,9,12,\ldots\}$.

Here, Jason makes three piles of $N/3$ coins with one fake in each. In two weighings, Jason establishes that each pile has the same weight. The number of fakes must be a multiple of three!

---

The complementary case: impossible?

As for the question in hand, I conjecture that this case is impossible: that is, Jason cannot prove that there are three fake coins, without compromising the location of some of the genuine coins.

Here, I'll present a semi-proof. Let me apologise on many accounts:

• That there are many holes.
• It's long and hard to follow.

Nevertheless, I hope this can be a stepping stone in the right direction. Counterexamples welcome!

---

Heuristic proof (with gaps)

Case 1. Jason starts by splitting all the coins into two stacks (A and B) and comparing them.

There must be an imbalance of fakes: stack A must contain more than stack B, say.

Case 1a. There are 2 fakes in stack A, and one in B.

(Key: A-fake: a fake coin in the lighter stack A, B-fake: a fake coin in the heavier stack B)

In this case, since there is the expected number of A-fakes, 2, Jason needs to demonstrate that there is a fake in B. Showing the B-fake exists must involve (at some point) another weighing with the fake from B on one side. To give any new information, not all of the coins from B will be used (or it will be the same weighing as the first!). Two of these examples use hindsight: the only way J can prove there are three coins is to reveal the 2-1 split, and in 2 out of 3 instances, C&M can deduce backwards from that:

• If you try and balance the B-fake with one A-fake: This doesn't add anything to the proof that the B-fake exists. Also, in hindsight, you can probably figure out that this is a 1-1 split, and so all the coins from stack B that you don't use must all be genuine, in hindsight.
• If the B-side of the scales has more fakes: then all of the coins from the B stack are all genuine (figured out in hindsight).
• If you use no A-fake to balance against B, then all of the coins being weighed against B must be genuine (this is immediate to C&M).
• If you put both of the fakes from A on the other side, all of the unweighed coins in stack A must be genuine (knowing in hindsight, there is one fake in B and hence 2 fakes in A).

Case 1b. All three of the fakes are in A.

Jason must show that the number of coins in A is not two — but this reveals the 3-0 split, i.e. that all the coins in stack B are genuine. Jason loses.

---

Case 2. Jason does not weigh all the coins together the first time.

This is the inductive part. Suppose that Jason leaves some coins out from the first weighing. Suppose that stack A is weighed against stack B, and stack C comprises all the remaining, unweighed coins.

Case 2a. Piles A–C each have 1 fake; or A has 2 fakes and C has 1.

• Jason must demonstrate that there is a fake in stack C: then, like in case 1a., this reveals genuine coins in stack C.

Case 2b. There are 2 fakes in A and 1 in B.

• Refer to case 1a.: if Jason reveals the existence of the fake in B, this allows C&M to deduce in hindsight that some of the coins from stack B are genuine.

Case 2c. There is one fake in A, and two in C.

• Here, Jason must somehow show that there is more than one fake in C (as a 1-0-1 split needs to be ruled out) — but as soon as he does, all of the coins in B are revealed to be genuine.

Case 2d. All three 3 fakes are in A.

• Assuming that Jason must show that there are more than 2 fakes in A, or no fakes in either of the other two piles (to rule out a 2-0-0 split or 1-0-1 split), this reveals that all the coins in stacks B and C are all genuine!

---

Answer 3

Jason numbers the $80$ coins and shows that coins $1$-$25$ weigh the same as coins $26$-$50$ and coins $51$-$75$. So either (a) there's one fake in each of these sets, or (b) the first $75$ coins are all genuine. He then shows that coins $\{1,2,76,77\}$ weigh the same as coins $\{26,27,78,79\}$ and coins $\{51,52,53,80\}$. Again, either (c) there's one fake in each of these sets, or (d) these coins are all genuine.

Since (c) and (d) can't both be true (we know there are some fakes, and all coins have now been weighed), then either (a) or (b) is true, and so there must be exactly three fakes. But no particular coin can be identified as genuine or fake: case (a) allows each of the first $75$ coins to be either genuine or fake, and case (b) allows each of the remaining five coins to be either genuine or fake.

Answer 4

Why random weighings? I thought Jason already knows which $3$ coins are fake. Also, I assume Mary & Christian (why do you need two of them anyway?) must come to know partial info about where the fake coins are, since any unbalanced weighing will give such info. If so, the easiest thing I can think of is three weighings.

Jason divides the coins into four groups of $20$ each, with a fake coin in groups $1,2,3$. Then weigh $1$ vs $4$, $2$ vs $4$, and $3$ vs $4$. This proves there are fake coin(s) in groups $1,2,3$ and M&C already know there cannot be more than $3$ fake coins.

Does the above work, or did I misunderstand your question?

Answer 5

Let's take the point of view of Christian (or Mary) and we suppose absurdily that the fake coins are only 2. We will get a contraddiction:

We ask Jason to divide the 80 coins in 2 sets of 40 coins both, we will call set A and set B.

Under the assumpion of two fake coins, we have to distinguish two cases:

• All the 2 fake coins are in A

• 1 fake coin is in A and the other is in B.

Only in the latter case the balance will show us the same weight.

As pointed out by @Harry Gartner we ask Jason to number all the coins from 1 to 80 and we ask him to try all the $\binom{80}{40}$ possibilities. If the fake coins are only two, soon or later the balance will compare the same weights.

But the weight will never be balanced: we got a contraddiction.

Answer 6

He makes two groups, A and B, with two coins each, of which one in A is fake. He weights them against each other. Then he takes one genuine coin of A and exchanges it with a genuine coin of B and weights again.

In both cases, Mary sees that B is heavier, so she knows that (i) either A contains one fake coin and B none and we exchanged genuine ones, or (ii) A contains 2 fake coins and B 1 fake coin, and we exchanged fake ones. Importantly, she knows that A+B contains an odd number of fake coins (i.e. 1 or 3).

Now, we simply have to split the remaining coins in pairs which are either both genuine or both fake, and weight them against each other. Mary will always see a tie, so she knows that the remaining set must contain an even number of fake coins (i.e. 0 or 2).

Finally, an odd plus an even number must be an odd number, and since Mary already knows that the total number of fake coins is either 2 or 3, it must be 3.