2
$\begingroup$

There are $n=18$ coins, and we know exactly $2$ of them are counterfeit. All counterfeit coins differ from normal coins in weight, but otherwise their weight is not known. They can be heavier or lighter than a normal coin, or than each other.

How many weighings are required in the worst case to differentiate the two coins from the rest of the group (and specify how their weight differs from the normal coins and, if applicable, each other)?

$\endgroup$
  • $\begingroup$ Also, hi, I'm new to this site, but I'm fairly sure that this puzzle, while similar to several other coin puzzles already posted, is both distinct from and much more difficult than most of the other puzzles due to the simple fact that the counterfeit coins weights are not constrained. I have a lower bound on the number of weighings required; however, I do not know if this value is achievable. $\endgroup$ – OmnipotentEntity Feb 13 at 19:12
  • 4
    $\begingroup$ Interesting question, but I think the answer will turn out to be very complicated and involve pages full of cases and subcases. See this question: Find two coins using a balance scale which involved 20 coins with 1 heavier and 1 lighter by the same amount. That question was much simpler than yours and the solution already required sub-sub-sub cases. It might be better to first try with a smaller n? $\endgroup$ – JS1 Feb 13 at 20:13
  • $\begingroup$ Are we using a balance scale or a scale? $\endgroup$ – Christopher Theodore Mar 17 at 0:00
  • $\begingroup$ We are using a balance scale. I apologize for not specifying. $\endgroup$ – OmnipotentEntity Mar 17 at 14:35
2
$\begingroup$

Preliminary answer. The work to get a definitive answer is more than I have time for.

As OP points out:

There are ${18 \choose 2} = 153$ combinations of coins, where 2 are fake out of 18. Furthermore, of any combination of two fake coins, there are 12 correlations of ordering of their weights. These are: first coin is heavier/lighter than genuine (2 options) times second coin is heavier/lighter than genuine (2 options) times first coin is farther from/closer to/same distance from genuine coin weight (3 options). Thus, we have $2\times 2\times 2\times 3 = 12$ weight correlations. Combined, this gives a total of 1836 possible combinations.

Also, as OP pointed out:

With all simple balance scale problems, there are 3 possible outcomes of each test, and $3^6 = 729 < 1836 < 2187 = 3^7$, so at least 7 tests are required.

As with all such problems, the goal is to try to have each test divide the remaining set of possibilities into 3 groups, as evenly as possible.

The only possible option for the first test is to weigh N coins on the left versus N coins on the right.

This table shows how many combinations tilt left, versus tilt right, versus balance, for several values of N:

\begin{array} \ N & 3 & 4 & 5 & 6\\ \text{Left} & 432 & 620 & 705 & 762 \\ \text{Right} & 432 & 620 & 705 & 762 \\ \text{Balance} & 972 & 596 & 426 & 312 \end{array}

Obviously,

If you select either 3 or 6, then there is an option remaining with more than $729 = 3^6$, and you will require at least 7 more tests. Testing either 4 or 5 would work; I recommend selecting the option that minimizes the worst case. So I recommend you select 4, where the worst cases tilt left or right, with 620 combinations each.

From there,

For the first test, you weighed coins 1,2,3,4 versus 5,6,7,8. If this test did not balance, then for the second test, you weigh 1,5,9,10 versus 2,6,11,12. This yields 194 combinations that balance, 213 that tilt left, and 213 that tilt right.

Again, working with the worst case,

If both of the first two tests tilted, then for the third test, you might weigh 9,11,13,15 versus 10,12,14,16. This yields 77 tests that balance, 68 that tilt left, and 68 that tilt right.

At this point, all possible results are still well below

81, which is the maximum number of combinations we can distinguish in 4 more tests. But 77 is close to 81, and it may be difficult to divide the tests evenly enough to distinguish all the possible combinations.

Unfortunately, finishing solving the problem would require

enumerating the 77 combinations that balanced, and each set of 68 combinations that did not, then looking through to come up with more tests that continue to divide the space evenly. And after that, one would have to go back to the sets of 194 combinations that did not balance on the second test, and also to the 596 combinations that did balance on the first.

Overall, that's a lot of work.

So, in summary, I would say:

Completing the problem with only 7 tests might be possible, but it could be that it is not possible to devise tests that divide the problem space evenly enough, and 7 tests would not be sufficient. Proving definitively whether 7 tests is sufficient would be a lot of work.

However,

I am certain we could complete the problem using 8 tests. The worst case scenario seems to be 77 combinations after 3 tests, and if those cannot be split evenly enough to fit into 81 different slots available in 4 tests, they can definitely be split into the 243 slots available in 5 more tests.

There may be a way of determining which two coins are fake without determining the weight correlations, but the problem specifically asks for those, so we can't take that shortcut.

| improve this answer | |
$\endgroup$
1
$\begingroup$

What follows establishes a lower bound on the value of weighings and is a summary of what I know about this puzzle. As well as motivations for specific values.

We can make a simple information theory argument to establish the lower bound. There are a total of $7$ cases for the relative weights of the counterfeit coins in relationship to the normal coins and themselves:

1. Both coins are heavier and they share a common weight.
2. Both coins are lighter and they share a common weight.
3. Both coins are heavier and they do not share a common weight.
4. Both coins are lighter and they do not share a common weight.
5. One coin is heavier and one coin is lighter, and they differ from the normal coin by an equal amount.
6. One coin is heavier and one coin is lighter, and the heavier coin differs from the normal coin by a greater amount.
7. One coin is heavier and one coin is lighter, and the lighter coin differs from the normal coin by a greater amount.

Within these $7$ cases, there are $12$ distinguishable ways to arrange the two counterfeit coins with respect with each other. And there are $\binom{18}{2}$ ways to position the two counterfeit coins among the $16$ standard ones. This gives a total of $1836$ possible states. Or $\approx 10.842$ bits of entropy.

Because there are three possible outcomes for each weighing, if we arrange the values very cleverly to maximin the entropy at each step we can achieve at most $\log_2(3) = 1.585\ldots$ bits of information each weighing. Dividing the two gives the absolute minimum number of steps $= 6.841\ldots$ steps. So $7$ steps is required and is a lower bound to the answer, but it might not be achievable.

A similar argument says that 19 coins should also be doable in 7 weighings, but I wanted to try 18 first because it seemed more achievable, and also the fact it's a multiple of 9 in a situation where multiples of 3 are nice is a big plus.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What would the worst-case in those 7 cases be? #5 seems to be the worst case: One coin is heavier and one coin is lighter, and they differ from the normal coin by an equal amount. $\endgroup$ – Christopher Theodore Mar 16 at 3:25
0
$\begingroup$

In the worst case, it would take exactly 18 weighings. Each coin would need to be weighed.

Presume that the coins each weigh 1 gram, and each of the counterfeits wiegh .8 grams and 1.2 grams (worst case). Even if we split them into groups of 2 and used 9 weighings, and both counterfeits ended up in the same group (worst case), that group would weigh 2 grams... just like all the others. We would have to weigh each coin.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I did actually. Because I asked how many are required in the worst case. While your answer is sufficient, it is not necessary. ;D $\endgroup$ – OmnipotentEntity Mar 15 at 17:52
  • 1
    $\begingroup$ Presume that the coins each weigh 1 gram, and each of the counterfeits wiegh .8 grams and 1.2 grams (worst case). Even if we split them into groups of 2 and used 9 weighings, and both counterfeits ended up in the same group (worst case), that group would weigh 2 grams... just like all the others. We would have to weigh each coin. $\endgroup$ – Christopher Theodore Mar 16 at 3:18
  • $\begingroup$ Consider the case where we have 8 coins, four on each scale, labeled 1-4 on the left and 5-8 on the right. If the scale balances swap 3,4 for 7,8. Worst case, if it still balances swap 1,7 for 3,5. Now the pair of counterfeit coins are guaranteed to be on different sides. Further, you know that the pair is either 1,2 or 3,4 or 5,6 or 7,8, and from the scale imbalance you know which of each pair would be heavy or light. From here you just need to two more weighings to determine the odd coin in one set (2,3,5,8 or 1,4,6,7) and you can deduce the other. This is 5 weighings, not 8. $\endgroup$ – OmnipotentEntity Mar 17 at 14:47
  • $\begingroup$ This is also not optimized. Just a proof of concept showing that the lower bound is not what you believe it to be. $\endgroup$ – OmnipotentEntity Mar 17 at 14: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.