The coin weighing problem in question:
Suppose that one has $n$ coins, among which there may or may not be one counterfeit coin. If there is a counterfeit coin, it may be either heavier or lighter than the other coins. The coins are to be weighed by a balance.
a) Find an upper bound on the number of coins $n$ so that $k$ weighings will find the counterfeit coin (if any) and correctly declare it to be heavier or lighter.
b) What is the coin-weighing strategy for $k = 3$ weighings and $n = 12$ coins?
This problem makes me wonder: how many unique strategies (up to relabeling of the coins, swapping sides of the scale, or swapping the heavy/light coins) exist that satisfy part b?
The problem asks for "the" coin-weighing strategy, but I've seen the problem solved at least two nonequivalent ways (one involving a decision tree, and another involving a clever tabulation of the possible outcomes). Notice that we're only trying to distinguish 25 possible cases with enough entropy to distinguish 27 states, so it's not exactly surprising that we have multiple valid solutions.
I'd start by showing what I've attempted so far, but I really don't know how I'd even start here. Any suggestions?
You said you want to find the unique strategies up to relabelling of the coins, and you’ve now also added equivalence under exchanging “heavier” and “lighter” and under exchanging the two sides of the balance. I think we should also exclude unnecessarily adding coins already known not to be counterfeit on both sides; and we shouldn’t distinguish between coins already known not to be counterfeit just because they had a different history in previous weighings. If you want to make those distinctions after all, it’s straightforward to count the possibilities in each of the strategies below.
The first choice is just the number of coins to weigh in the first weighing.
If we weigh $3$ or less on each side and the balance stays level, we have $13$ or more cases left for $2$ weighings, so that doesn’t work.
If we weigh $5$ or more one each side and the balance tilts, we have $10$ or more cases left for $2$ weighings, so that doesn’t work either.
So the first weighing has to have exactly $4$ coins on each side.
If the balance stays level, there are $9$ cases left: there’s no counterfeit coin, or one of the $4$ as yet unweighed coins is counterfeit. We need to partition those $9$ cases exactly into $3$ groups of $3$. The next weighing must include at least $3$ of the unweighed coins, since leaving $2$ unweighed would leave $4$ cases if the balance stays level. Including all $4$ of them also won’t work because then if the balance tilts that leaves $4$ cases. So the next weighing must include exactly $3$ of the unweighed coins. There are two inequivalent ways of doing that: a) weigh all three on one side against three weighed coins, or b) weigh two on one side against the third and one weighed coin. In both cases, if the balance stays level, we have to weigh the remaining unweighed coin against some other coin. If the balance tilts, in case a) we have to weigh one of the previously unweighed coins against another, but in case b) we have two options: either weigh the two previously unweighed coins that were one the same side against each other, or put two that were on opposite sides on the same side and way them against two neutral coins. Thus, in total there are $3$ inequivalent substrategies if the balance stays level in the first weighing.
If the balance tilts in the first weighing, there are $8$ cases left. So the two tilt results in the second weighing must either both leave $3$ of those cases, or one must leave $3$ and the other $2$. Thus, either $3$ weighed coins must stay in place while $3$ switch sides, or $3$ must stay in place while $2$ switch sides (or equivalently vice versa). We only have $4$ neutral coins to balance them with, so the difference in the number of coins already weighed on each side can be at most $4$. That leaves the following $7$ inequivalent possibilities (with $l$, $h$ and $n$ denoting coins that are known to be potentially lighter, potentially heavier, and normal, respectively): $lllh$ vs. $lnnn$, $lllhh$ vs. $lnnnn$, $llh$ vs. $lhn$, $llh$ vs. $llh$, $llh$ vs. $lln$, $llhh$ vs. $lhnn$, and $llhh$ vs. $lnnn$.
After this weighing, one of the following three cases occurs:
a) There are $2$ potential counterfeit coins. Then we have two options – weighing those coins with/against each other, or weighing one of them against a neutral coin.
b) There are $3$ potential counterfeit coins from the same side of the first weighing. Then we have to weigh two of those against each other.
c) There are $3$ potential counterfeit coins, two from one side of the first weighing and one from the other. Then we have two options – weighing the two coins from the same side against each other, or weighing two coins from opposite sides with each other.
The three possible outcomes for each of the $7$ above possibilities are as follows:
$lllh$ vs. $lnnn$: abb
$lllhh$ vs. $lnnnn$: abc
$llh$ vs. $lhn$: acc
$llh$ vs. $llh$: acc
$llh$ vs. $lln$: abc
$llhh$ vs. $lhnn$: acc
$llhh$ vs. $lnnn$: acc
We can choose a strategy for each of the three outcomes independently, so e.g. abc allows for $2\cdot1\cdot2=4$ different strategies. The case $llh$ vs. $llh$ is symmetric, so the two outcomes of type c are equivalent and only count once. Thus, the total number of inequivalent substrategies if the balance tilts in the first weighing is $2+4+8+4+4+8+8=38$.
We can choose strategies for the two possible outcomes of the first weighing independently, so the total number of inequivalent strategies is $3\cdot38=114$.
I’m sure there must be a mistake in there somewhere :-)