0
$\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
0
$\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.

$\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.