Finding real money on a strange weighing device

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. :-)

The following pattern works with $31$ weighings: $${0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, \ 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, \ 0, 1, 1, 1}.$$ This beats the $35$-weighing solution found earlier. $${1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, \ 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, \ 0, 0, 0, 1}.$$ See the comments at the end of this post.

This is not a complete answer, but it won't fit in a comment. We define $f(n)$ to be the smallest number of weighings possible for $n$ coins. Here is some simple but not particularly efficient Mathematica code which computes $f(n)$ for small $n$ by brute force: pick a representative $x$ of a rotational equivalence class of $n$-long $\{0,1\}$-vectors, build a matrix out of $k$ successive rotations of $x$, hit that matrix against all $\{0,1\}$-vectors, and see if all $2^n$ results are distinct. There are roughly $2^n/n$ rotation classes, so the complexity of this is about $4^n/n$.

(* check if vector x works when rotated k times *)
ok[x_, k_] := Block[{n = Length[x], m, v},
  m = RotateRight[x, #] & /@ Range[k];
  v = Tuples[{0, 1}, n];
  Unequal @@ (m.# & /@ v)];

(* compute a canonical representative for the rotation class of x *)
MinRotation[x_] := 
  First[Sort[RotateRight[x, #] & /@ Range[Length[x]]]];

f[n_] := f[n] = Block[{k, v},
  v = Select[Tuples[{0, 1}, n], # == MinRotation[#] &];
  For[k = 1, k <= n, k++,
  s = Select[v, ok[#, k] &];
  If[s != {}, Return[{k, First[s], Length[s]}]]]];

TableForm[Prepend[f[#], #] & /@ Range[12],
  TableDirections -> {Column, Row, Row},
  TableHeadings -> {None, {"n", "f(n)", "Example", "# of examples"}}]

$$ \begin{array}{cccc} \text{n} & \text{f(n)} & \text{Example} & \text{$\#$ of examples} \\ 1 & 1 & (1) & 1 \\ 2 & 2 & (0 1) & 1 \\ 3 & 3 & (0 0 1) & 2 \\ 4 & 3 & (0 1 1 1) & 1 \\ 5 & 4 & (0 0 1 1 1) & 3 \\ 6 & 5 & (0 0 1 0 1 1) & 4 \\ 7 & 6 & (0 0 0 0 1 1 1 & 12 \\ 8 & 6 & (0 0 0 1 0 1 0 1) & 8 \\ 9 & 6 & (0 0 1 0 0 1 0 1 1) & 6 \\ 10 & 7 & (0 0 0 0 1 1 0 1 1 1) & 17 \\ 11 & 7 & (0 0 0 1 0 1 0 0 1 1 1) & 4 \\ 12 & 8 & (0 0 0 0 1 0 0 0 1 0 1 1) & 42 \\ \end{array}$$

This quickly becomes infeasible. However, checking a given vector costs "only" $2^n$ matrix multiplies, so we can get some upper bounds for $f(n)$ by guessing good vectors $x$. A reasonable heuristic is that the $k\times n$ matrix $A$ we're constructing should have $\det A A^T$ large; using that, we find for example that $f(15)\le 9$, since $$(0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1)$$ turns out to work with $9$ rotations.

(Added 7/3/2015:) To construct the solutions for $k=31$ and $k=35$ weighings of $n=50$ coins, I started by running a hill-climb about $3$ times, and picked the pattern giving the largest $\det AA^T$. As a first check, I looked at a reduced basis for $\ker A$ to check that it didn't have any nonzero vectors whose coordinates were at most $1$ in absolute value, and then exhaustively checked $\ker A$ by putting it into Hermite form first. This requires checking about $(2/3)3^{n-k}$ vectors, which is easy on a laptop. The run for $k=31$ took about $7$ hours, $81$ times as long as the run for $k=35$.

Incidentally, just from a visual examination of the reduced bases for smaller values of $k$, I suspect that $f(50)$ is about $28$.