8
$\begingroup$

You have a machine that lights up if counterfeit coin is placed in it. Any number of coins can be placed in the machine. It only lights up and does not indicate how many counterfeit coins are present (who designs these machines anyway?!?). You are given 15 coins and told that 2 are counterfeit. You are allowed to use the machine a maximum of 7 times and asked to find the two counterfeit coins.

go!

$\endgroup$
  • $\begingroup$ This is a deliciously evil puzzle. Well done, sir! $\endgroup$ – Bass Jan 6 '18 at 2:20
  • $\begingroup$ Welcome to Puzzling! (Take the Tour!) Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$ – Rubio Jan 11 '18 at 5:39
6
$\begingroup$

It is possible, but only if you test 5 coins the first time.

The difficulty is that, if all the tests up to a certain point have answered No, and there are $k$ coins remaining, then there are $k\choose 2$ combinations remaining. This limits how evenly we can divide the remaining combinations with each test. Specifically, for 6 coins, there are $15 < 2^4$ combinations, but there is no way to divide the combinations that will always yield an unambiguous answer in 4 tests.

Details on why we must start with 5 coins:

For $N$ coins, there are ${N \choose 2}$ combinations. For 15, that comes to 105 combinations. In 7 guesses, we can distinguish between $2^7 = 128$ combinations. That does not leave much leeway, so we need to split the number of remaining combinations as close to in half as possible at each stage.

If we have $k$ coins containing both counterfeits, and we put $i$ coins into the machine, then we have $k-i\choose 2$ combinations that get a "No", and the remainder ${k\choose 2} - {k-i\choose 2} = {i\choose 2} + k\times i$ that get a "Yes".

Some possibilities for the first test:

  1. 6 coins in: Yes implies $69 > 2^6$ combinations, No implies $36$ combinations.
  2. 5 coins in: Yes implies $60$ combinations, No implies $45$ combinations.
  3. 4 coins in: Yes implies $50$ combinations, No implies $55$ combinations.
  4. 3 coins in: Yes implies $39$ combinations, No implies $66 > 2^6$ combinations.

So only 4 or 5 could work. But, while $55 < 64$, if we test 4 coins the first time and get No, we cannot guarantee success. At this point, we would have 11 coins containing two counterfeits. For tests 2 through 4:

  1. 3 in, 8 out: Yes implies 27, No implies 28. (Bad news: it's No)
    • If we tried 4 in, Yes would imply $34 > 2^5$ combinations
  2. 2 in, 6 out: Yes implies 13, No implies 15. (Bad news: it's No)
    • If we tried 3 in, Yes would imply $18 > 2^4$ combinations
  3. 1 in, 5 out: Yes implies 5, No implies $10 > 2^3$
    • If we tried 2 in, Yes implies $9 > 2^3$, No implies 6.

Thus, if we put 4 coins in for the first test and get no, then we cannot guarnatee success. Thus, our first test must be 5 coins.

Starting with 5 coins in the first test:

If we get No on the first test, our next test is 3 coins.

  1. 3 in, 7 out: Yes implies 24, No implies 21 combinations.
  2. If No, then we test 2 in, 5 out. Yes implies 11 combinations, No implies 10.
  3. If No again, then we have 5 coins and 4 tests remaining. Test 4 of the coins individually. If two are Yes, then they are the counterfeits. If only one is Yes, then the fifth coin is the other counterfeit.

If the first test returned Yes, then we have ${5\choose 2} + 5\times 10 = 60$ combinations remaining. This is less than 64, but only barely. Label the tested coins group A, and others group B.

For our second test, we split the groups: A1 (2 coins), A2 (3 coins), B1 (1 coin), and B2 (9 coins). Test groups A1 and B1 both together. If we get Yes, then we have both coins in A1 (1 combo), one in A1, one not in A1 (26 combos), or one in A2, one in B1 (3 combos), for a total of 30. likewise a No for this test would mean either both in group A2 (3 combos) or one in A2, one in B2 (27 combos), also for a total of 30.

If first and second test results are Yes, split group B2 into B2a (3 coins) and B2b (6 coins). Test groups A2 and B2a together.

  • Yes, combinations are A1$\times$A2 (6), A2$\times$B1 (3), or A1$\times$B2a (6), total of 15.
  • No, combinations are A1$\times$A1 (1), A1$\times$B1 (2), or A1$\times$B2b (12), total of 15.

If the first result is Yes and the second test result is No, groups A1 and B1 are eliminated. Split B2 into B2a (5) and B2b (4). Test B2a.

  • Yes: must have one coin from A2a and one from B2a, 15 combinations.
  • No: cominations A2a$\times$A2a (3) or A2a$\times$B2b (12), total of 15.

Tests 4 through 7 will depend on previous results, but in all combinations, it is straightforward to choose a test that will split the remaining combinations in half. In all cases if the first test returned Yes, then after 3 tests, there are 15 combinations to test and 4 tests to make the determination, so it will work.

If the first test returned No and the second or third returned Yes:

Then we have either 24 combinations to differentiate in 5 tests or 11 combinations in 4 tests. In either case, we use a strategy like above to split the groups of combinations in half repeatedly until we have only one combination remaining.

For example: first test No, second test Yes. We have group A (3 coins) and group B (7 coins), with at least one counterfeit in group A. Split group B into B1 (4 coins) and B2 (3 coins). Test B1.

  • Yes: must have one coin in A and one in B1: 12 combinations.
  • No: Either both in A (3) or one in A and one in B2 (9), total 12 combinations.
| improve this answer | |
$\endgroup$
1
$\begingroup$

Finally managed to find the fakes. I used this method:

Label the coins with pentadecimal numbers 0-E. Write out each possible counterfeit coin pair in a "pretty" triangle. Then do a binary search, taking care that

  1. each weighing leaves a solvable number of reasonably well-identifiable coin pairs on both sides
  2. each weighing can be performed by testing some specific individual coins.

Then, try different partitioning strategies, (backtracking, if necessary,) until you find a proper partitioning scheme that allows you to pinpoint any pair. This was surprisingly non-trivial, and there was a lot of backtracking.

Here's a diagram of a successful search, when the counterfeit coins are 1 and 3 (a worst-case scenario for the full partitioning scheme shown later). Notice how you must always use the result of the previous measurement to decide what to weigh next.:

enter image description here

Notice how each weighing excludes roughly a half of the remaining possibilities: e.g. for the first weighing, if at least one of the counterfeit coins is labeled 4 or less, any pair without such numbers is automatically impossible.

In the above example search, the actual pair was always on the bigger, more difficult side, making it the likely worst case scenario. To prove that any pair can be found using this method, here's a partition map for the first 4 measurements. The weighings split the search space in the order Black - Orange - Blue - Green.

enter image description here

At this level, we still have 3 weighings left, each partition has at most 8 pairs, and each partition is individually solvable. The partition shapes for the 4D and 4E partitions may be overly complicated, but at this point, I wasn't taking any risks.

This probably duplicates a lot of info in the earlier answers, but hey: diagrams :-)

| improve this answer | |
$\endgroup$

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.