12
$\begingroup$

You have N coins, where N ≥ 5, and you know that exactly two of the coins are counterfeit and the rest are genuine. The genuine coins each weigh some amount w1 and the counterfeit coins each weigh some amount w2. You know for certain that w1 ≠ w2, but you do not know which is greater.

You have access to a balance that you are allowed to use up to four times. The balance has two trays, and one use consists of loading each of the trays with any coins of your choice, after which the balance tells you whether the contents of the left tray weigh more than, less than, or the same amount as the contents of the right tray.

Your goal is to determine which two coins are counterfeit, but you do not need to ascertain whether or not w1 > w2. What is the maximum value of N for which you can guarantee success, and what is the method of doing so?

Although these kinds of problems are common, I hunted around and have never seen this variation before. The wording of the problem is my own.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Considering the information content of each weighing, $N=13$ is an upper bound for four weighings. I haven't been able to show if this bound is sharp or not, but I suspect not. $\endgroup$ Commented Mar 19 at 4:00
  • 2
    $\begingroup$ Here is question that asks for a solution for N=7 in 4 weighings when the two counterfeits are known to be heavier. I doubt you can get N=7 when you don't know the relative weights, let alone larger N. $\endgroup$ Commented Mar 19 at 8:47
  • $\begingroup$ Do you mean maximum or minimum.? Maximum surely means you can use as many coins as you like. $\endgroup$ Commented Mar 20 at 15:26
  • 3
    $\begingroup$ @JaapScherphuis In the linked question, N is 9, not 7. $\endgroup$ Commented Mar 21 at 6:00
  • 2
    $\begingroup$ @WeijunZhou You’re right, I misread. So it’s almost a duplicate, if it weren’t for the knowledge of the relative weight $\endgroup$ Commented Mar 21 at 7:15

3 Answers 3

Reset to default
22
$\begingroup$

Here's a solution for

N = 9.

Label the coins

A through I

and use the following strategy for the first three weighings:

  1. A, B, C vs. D, E, F
  2. A, D, G vs. B, E, H
    • If Weighing 2 was =: A, B, D vs. G, H, I
    • Otherwise: A, B, F vs. G, H, I

For the final weighing and the counterfeits, consult the following table:

W1 W2 W3 W4 W4 is < W4 is = W4 is >
< < < H vs. I E, I A, C E, H
< < = G vs. I A, G F, H A, I
< < > A vs. C - E, F C, G
< = < E vs. F F, I A, B E, G
< = = A vs. B A, H D, H B, G
< = > A vs. C - D, E C, I
< > < G vs. I D, I B, C D, G
< > = H vs. I B, H F, G B, I
< > > A vs. C - D, F C, H
= < < D vs. F A, D H, I A, F
= < = A vs. C C, E - C, D
= < > E vs. F B, F G, I B, E
= = < A vs. B A, E G, H B, D
= = = - C, F C, F C, F
= = > A vs. B B, D G, H A, E
= > < E vs. F B, E G, I B, F
= > = A vs. C C, D - C, E
= > > D vs. F A, F H, I A, D
> < < A vs. C C, H D, F -
> < = H vs. I B, I F, G B, H
> < > G vs. I D, G B, C D, I
> = < A vs. C C, I D, E -
> = = A vs. B B, G D, H A, H
> = > E vs. F E, G A, B F, I
> > < A vs. C C, G E, F -
> > = G vs. I A, I F, H A, G
> > > H vs. I E, H A, C E, I
Improve this answer
$\endgroup$
8
  • $\begingroup$ That's amazing! +1 $\endgroup$ Commented Mar 19 at 12:40
  • $\begingroup$ For =>>>, you got: A,D. However, this doesn't seem to be possible:, since ABC=DEF means that the counterfeit is in GHI (per op, $w_1 \ne w_2$ ). Am I missing something? $\endgroup$ Commented Mar 19 at 13:02
  • 1
    $\begingroup$ @Brian I think you mistook $w_1$ and $w_2$ for the weights of the counterfeit coins, but they're actually the weights of the genuine and counterfeit coins, respectively. $\endgroup$ Commented Mar 19 at 13:09
  • 2
    $\begingroup$ Feel free to copy/reuse/restate the fact that this is the theoretical maximum, from my answer. $\endgroup$ Commented Mar 19 at 15:39
  • 6
    $\begingroup$ Would you share how you came up with this huge table? $\endgroup$ Commented Mar 20 at 13:55
12
$\begingroup$

The theoretical maximum is

9 coins. We have 4 weighings with 3 outcomes, or $3^4 = 81$ possible results. In all but one of these - all weighings balance - we will also have figured out whether the fake coins are lighter or heavier. Thus the total number of possible fake combinations can be no more than 41. Since 2 out of N gives $\frac {N(N-1)} 2$ possibilities, we have $\frac {N(N-1)} 2 \le 41 \implies N \le 9$

@noedne beat me to showing that this is also achievable.

Improve this answer
$\endgroup$
6
$\begingroup$

With the 4 weighings available, I can distinguish the two fakes from among

6 coins

like so:

- Label the coins A to F
- Weighing 1: A against B
- Weighing 2: C against D

If the weighings are both balanced, then we have three pairs of balanced coins (we have weighed either 0 or 2 fakes, so the unweighed coins must also be either both fakes, or both genuine), and we can use the remaining weighings to figure which pair is the odd one out.

If only one of the weighings is balanced, then the balanced coins are both genuine: (exactly) one of the fakes was involved in the unbalanced weighing. So we have two pairs of coins containing one fake each, and we can use the known-good coins to figure out the which one of each pair is the fake.

If neither weighing is balanced, then the unweighed coins are genuine. This time it only takes one more weighing to figure out the fakes, since both of them have already been on the scales against a genuine coin.

I have no proof that this is the maximum, but if someone can do more, the method has to be at least half-magical. :-)

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.