Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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)?
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:
| N | 3 | 4 | 5 | 6 |
|---|---|---|---|---|
| Left | 432 | 620 | 705 | 762 |
| Right | 432 | 620 | 705 | 762 |
| Balance | 972 | 596 | 426 | 312 |
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.
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.
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.
