Update: I've now found two solutions that require only $25$ weighings:
$$
01011011100010111101000001100111110011010100011010\;,\\
00101110001101001010111110001000110010011111011101\;.
$$
These are the only solutions known (in the context of this post) with $k=n\,/\,2$, for any $n$. I found them using Tad's recipe of repeatedly maximizing the determinant of $AA^\top$ by hill climbing and testing the candidate with the highest determinant among several runs. The determinants are
$$
87546852131623099566361867104\;,\\
93001686149176479553585114299\;.
$$
I only had to test half a dozen candidates to find these two solutions, which seems consistent with $f(50)\simeq 22.4$. I'll now be testing these two with $24$ weighings; that will take the better part of a day and will require a bit more than a trillion difference vectors to be checked in each case.
I believe the bounty should go to Tad, who developed the mathematical approach. I tried to improve on it but couldn't, so instead I coded it a whole lot faster :-). Here's the code. It uses a special bit encoding for efficient arithmetic with vectors over $\mathbb F_3$. On my MacBook, it takes half a minute to test a candidate with $31$ weighings and two hours for a candidate with $26$ weighings.
The best solution it's found so far is $01010111100010011111110000111011000101101100100001$, with $26$ weighings required. I'm now looking for solutions with $25$ weighings, but that requires up to six hours of testing per candidate. I expect the minimum to be near $23$ (see below). I haven't implemented Tad's determinant maximization approach yet; the above solution was just the third candidate I tried with uniform sampling among the vectors (uniform sampling among the rotational equivalence classes would be worse since it gives higher weight to periodic sequences).
Here's a short summary of the mathematical basis of the code, mostly following Tad's ideas and notation; $n$ is the number of coins, and $k$ is the number of weighings. We can treat the two weights of the coins as $0$ and $1$. Then every possible weight configuration is characterized by a binary weight vector, and the differences between weight vectors are ternary vectors with entries $-1$, $0$ and $+1$. A solution is admissible if the $k\times n$ matrix $A$, with entries $A_{ij}\in\{0,1\}$ according as coin $j$ is weighed in weighing $i$, has different products with all possible weight vectors, or equivalently, if its product with all possible difference vectors is non-zero.
We can regard the difference vectors as vectors over $\mathbb F_3$. Only the difference vectors in the kernel of $A$ over $\mathbb F_3$ can be in the kernel of $A$ over $\mathbb Z$. The kernel over $\mathbb F_3$ will generally contain $3^{n-k}$ difference vectors, and these we have to check over $\mathbb Z$ (actually only half of them, due to invariance under negation). The key to doing this efficiently is to bit-encode $\mathbb F_3$ such that the time-limiting steps (addition, componentwise multiplication and summation of vectors) can be performed compactly using integer operations and table lookups instead of iterating over $n$ vector components.
Here are some results that expand on Tad's results for values well below $50$. $n_\text{c}$ is the number of equivalence classes under rotation; the numbers in the header row are $n-k$, and the numbers in the bodies of the two tables are the numbers and fractions, respectively, of rotational equivalence classes that yield a solution.
\begin{array}{c|c|cc}
n_\text{c}&n&0&1&2&3&4&5&6&7&8&9\\\hline
2&1&1\\
3&2&1\\
4&3&2\\
6&4&2&1\\
8&5&6&3\\
14&6&6&4\\
20&7&18&12\\
36&8&20&17&8\\
60&9&50&45&25&6\\
108&10&74&71&56&17\\
188&11&186&178&130&83&4\\
352&12&216&214&200&135&42\\
632&13&630&614&520&469&261&6\\
1182&14&916&910&878&787&535&101\\
2192&15&2002&1988&1924&1831&1427&648&22\\
4116&16&3040&3037&3000&2926&2605&1686&330&2\\
7712&17&7710&7699&7464&7330&6915&5361&2131&34\\
14602&18&10806&10801&10760&10649&10310&9014&5547&875\\
27596&19&27594&27582&27270&27110&26565&24773&18964&7307&152\\
52488&20&40642&40639&40592&40474&40024&38487&33414&20254&3102&2\\
99880&21&94658&94640&94440&94281&93518&91759&85546&65010&24368&508\\
\end{array}
\begin{array}{c|c|cc}
n_\text{c}&n&0&1&2&3&4&5&6&7&8&9\\\hline
2&1&.5000\\
3&2&.3333\\
4&3&.5000\\
6&4&.3333&.1667\\
8&5&.7500&.3750\\
14&6&.4286&.2857\\
20&7&.9000&.6000\\
36&8&.5556&.4722&.2222\\
60&9&.8333&.7500&.4167&.1000\\
108&10&.6852&.6574&.5185&.1574\\
188&11&.9894&.9468&.6915&.4415&.0213\\
352&12&.6136&.6080&.5682&.3835&.1193\\
632&13&.9968&.9715&.8228&.7421&.4130&.0095\\
1182&14&.7750&.7699&.7428&.6658&.4526&.0854\\
2192&15&.9133&.9069&.8777&.8353&.6510&.2956&.0100\\
4116&16&.7386&.7379&.7289&.7109&.6329&.4096&.0802&.0005\\
7712&17&.9997&.9983&.9678&.9505&.8967&.6952&.2763&.0044\\
14602&18&.7400&.7397&.7369&.7293&.7061&.6173&.3799&.0599\\
27596&19&.9999&.9995&.9882&.9824&.9626&.8977&.6872&.2648&.0055\\
52488&20&.7743&.7743&.7734&.7711&.7625&.7333&.6366&.3859&.0591&.0000\\
99880&21&.9477&.9475&.9455&.9439&.9363&.9187&.8565&.6509&.2440&.0051\\
\end{array}
Here are the minimal $k$ values up to $n=26$ (denoted by $f(n)$ as in Tad's table), together with the numbers and fractions of solution classes at minimal $k$:
\begin{array}{c|c|c|c}
n&f(n)&\#&\#\,/\,n_\text{c}\\\hline
1&1&1&.5000\\
2&2&1&.3333\\
3&3&2&.5000\\
4&3&1&.1667\\
5&4&3&.3750\\
6&5&4&.2857\\
7&6&12&.6000\\
8&6&8&.2222\\
9&6&6&.1000\\
10&7&17&.1574\\
11&7&4&.0213\\
12&8&42&.1193\\
13&8&6&.0095\\
14&9&101&.0854\\
15&9&22&.0100\\
16&9&2&.0005\\
17&10&34&.0044\\
18&11&875&.0599\\
19&11&152&.0055\\
20&11&2&.0000\\
21&12&508&.0051\\
22&12&8&.0000\\
23&13&2340&.0064\\
24&13&36&.0001\\
25&14&10688&.0080\\
26&14&216&.0001
\end{array}
The solution class counts of $2$ for $n=16$ and $n=20$ that both come at the end of an unusual triple of identical values of $f(n)$ are salient; here are the solution vectors:
$$
0000101110111011\;,\\
0000110111011101\;,\\
00000101111011110111\;,\\
00000111011110111101\;.\\
$$
Note that in both cases the two solutions are related by inversion, they contain slightly longer runs of $0$s than of $1$s, and the runs of $1$s are separate by single zeros.
It's tempting to speculate that the bound $f(n)\gt n/2$ that holds up to $n=26$ will continue to hold for higher $n$. However, I don't believe that this is the case. There's already a slight indication of this in the data; the solutions are gradually encroaching on the bound. (The trends in the absolute numbers are relevant here, not in the fractions, since we only need a single solution.) The fact that the third uniformly randomly guessed candidate turned out to be a solution for $k=26$, $n=50$ also points in this direction, since it suggests that the density of solutions at that point is much higher than it is for $k=n/2-1$ at lower $n$ values (where it's almost negligible).
Moreover, statistical considerations suggest that the asymptotic behaviour of $k$ might be $n\,/\log n$. There are various handwaving arguments that could be used to support this, based on entropy or collision probabilities; the details may be hard to get right, but the bigger picture is the same in each case: The $k$ measurements each have an effective space of order some power $n^\alpha$ to spread across ($\sqrt n$ if we consider them to be binomially distributed), so our discerning ability grows with $n^{\alpha k}$, while the number of possibilities we need to be able to discern grows with $2^n$; equating the logarithms yields $\alpha k\log n=n\log2$ and thus $k\propto n\,/\log n$.
Such $n\,/\log n$ behaviour seems consistent with the data up to $n=26$, so we can get a rough estimate e.g. from $f(26)=14$:
$$f(50)\simeq\frac{50\log26}{26\log50}\,f(26)\simeq1.6\,f(26)\simeq22.4\;.$$
That leaves ample space for improvement. :-)
Let $P_k$ (for $k \geq 2$) be the property: “there exists a strategy that works in $2k$ weightings, whose first move is comparing two groups of $3^{k-1}$ coins”.
We will show that $P_k \Rightarrow P_{k+1}$. We’ll see afterwards how $P_2$ is true.
Assume that $P_k$ holds, and let $c_1,\ldots,c_{3^{k+1}}$ be the coins. Our first weighting must be $c_1,\ldots,c_{3^k}$ against $c_{3^k+1},\ldots,c_{2\cdot 3^k}$.
- If the two are unequal, put, for each $1 \leq i \leq 3^k$, the coins $c_{3i-1},c_{3i-2},c_{3i}$ in a little bag $B_i$. Then $B_i$ satisfies the same properties as the coins (there’s a little trick here but it does work), but there are $3^k$ of them and we know the result of comparing $B_1,\ldots,B_{3^{k-1}}$ to $B_{3^{k-1}+1},\ldots,B_{2\cdot 3^k}$.
So, by $P_k$, we know that with $2k-1$ further weightings, we can find distinct indices $1\leq i,j \leq 3^k$ such that $B_i$ is the bad light bag (hence contains the lighter coin) and $B_j$ contains the heavier coin. With one weighting, you can find the lighter coin in $B_i$ (resp. the heavier coin in $B_j$) and that makes $2k+2$ weightings total.
- Now we assume that at the first weighting, the scales are balanced. We then construct $3^k$ bags of three coins, but with a different trick to ensure that there still is one lighter bag and one heavier bag: for $1 \leq i\leq 3^k$, $B_i$ is made with $c_{i+l\cdot 3^k}$, $0 \leq l \leq 2$. In $2k$ weightings, we can (by $P_k$) find distinct indices $1 \leq i, j\leq 3^k$ such that $B_i$ is the lighter bag while $B_j$ is the heavier one.
But using the results from the first weighting, it follows that the ordered pair $(\text{lighter coin, heavier coin})$ must be one of the $(c_{i+l\cdot 3^k},c_{j+l\cdot 3^k})$, with $0 \leq l \leq 2$ (ie the good and bad coins had to “compensate one another”). We only have one weighting left to determine which is the true possibility. To do that, we compare $c_i,c_{j+3^k}$ to $c_j,c_{i+3^k}$, and $Left$ is lighter (resp. heavier) than $Right$ iff the pair is $(c_i,c_j)$ (resp. $(c_{i+3^k},c_{j+3^k})$).
This ends our induction.
We still need to check $P_2$. Let use digits to denote our coins: $1,2,3,4,5,6,7,8,9$.
First we weigh $123$ against $456$. By symmetry we only need to consider the cases $123=456$ and $123<456$ ($<$ means “is lighter”).
If $123=456$, then both the heavier and lighter coins are in the same of the subsets $123,456,789$. Then weigh $1258$ against $3469$. If there is equality again, then the bad coins are either $12$ or $34$. Weigh $1$ against $2$, then $3$ against $4$ to know. If, on the other hand, (by symmetry again) $1258 < 3469$, then the possible $(\text{lighter, heavier})$ pairs are $13,23,54,56,89$. Then weigh $59$ against $84$: if it’s equal, then the possible pairs can only be $13,23$ and you can determine the right one with the last weighting. If $59<84$, then the right pair is $54$ or $56$ and you can again determine the right one with one last weighting. If $59>84$ then it’s $89$.
If $123<456$, this is much, much tighter (there are exactly $27$ possible cases and three weightings). Weigh $1245$ against $3678$. If there is equality, then the possible pairs (same order as ever) are $14,15,24,25,36,37,38,76,86$; then weigh $1463$ against $2578$. If there is equality, the possible pairs become $14,25,36$ and one weighting is enough to find the good one. If $1463<2578$, the possible pairs are $15,37,38$ and weighting $7$ against $5$ decides which is the good one. If $1463>2578$, the possible pairs are $24,76,86$ and weighing $7$ against $2$ decides the good one.
If $1245<3678$, the possible pairs are $16,17,18,26,27,28,19,29,96$. Weigh $178$ against $642$: if $178=642$, the possibilities are $17,18,26$ (decidable in one go), if $178<642$, the possibilities are $96,16,19$ (decidable by $61$ against $34$), if $178>642$, the possibilities are $27,28,29$, decidable in one go.
If $1245>3678$, the possibilities are $34,35,39,84,85,74,75,94,95$. Weigh $478$ against $253$. If there is equality, the possibilities are $47,84,35$ (decidable by $78$ against $35$), if $478<253$, the possibilities are $75,85,95$ (decidable in one go), if $478>253$, the possibilities are $34,94,95$ (decidable by $94$ against $12$).
And thus we’re done.
Best Answer
Here is a simple solution that works. There are many combinations that you can use. The idea is to make sure you are always making 3 such groups and weighing them against each another so that all of them balance. Also any transfer should be done in a way that you cannot tell whether you transferred a fake or a real.
Jason makes 6 groups as below (there are many more possible solutions as you can understand after reading through my solution) -
G1 = 20 coins, G2 = 20 coins, G3 = 20 coins
G4 = 7 coins (1 fake coin), G5 = 7 coins (1 fake coin), G6 = 6 coins (1 fake coin)
He weighs G1 against G2 and G2 against G3. This shows to Mary and Christian that either G1, G2 and G3 all have 1 fake each or none of them have any fake.
Now Jason transfers 1 coin from G1 to G4, 1 from G2 to G5 and 2 from G3 to G6 (he can also take 2,2,3 or 3,3,4 or other counts as well making sure G4, G5 and G6 have equal number of coins after transfer).
So G4, G5 and G6 all have 8 coins each now after the transfer. Now he weighs G4 against G5 and G5 against G6. They all balance. This shows Mary and Christian that there are 3 fake coins as they know there are either 2 or 3 (they know zero or another multiple of 3 is not an option).
But what they cannot tell whether the fake coins were there in G4, G5 and G6 from before or the transferred coins were fake or fake one's are still in G1, G2 and G3.
I hope it is clear. Let me know if any questions.