El siguiente patrón funciona con $31$ pesajes:
$${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}.$$
Esto supera los $35$-solución de pesaje encontrado antes.
$${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}.$$ Vea los comentarios al final de este post.
Esto no es una respuesta completa, pero no cabe en un comentario. Definimos $f(n)$ a ser el más pequeño número de pesajes posible para $n$ monedas. Aquí está algo simple, pero no es particularmente eficiente código de Mathematica que calcula $f(n)$ para los pequeños $n$ por fuerza bruta: elija un representante de $x$ de una rotación de equivalencia de la clase de $n$largo $\{0,1\}$-vectores, construir una matriz de $k$ sucesivas rotaciones de $x$, que golpeó la matriz en contra de todo $\{0,1\}$-vectores, y ver si todos los $2^n$ resultados son distintos. Hay aproximadamente $2^n/n$ la rotación de clases, por lo que la complejidad de este es de alrededor de $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{Ejemplo} & \text{$\#$ de ejemplos} \\
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}$$
Este rápidamente se convierte en inviable. Sin embargo, la comprobación de un determinado vector de costos "sólo" $2^n$ matriz se multiplica, por lo que podemos conseguir algunos límites superior por $f(n)$ adivinando buena vectores de $x$. Una razonable heurística es que el $k\times n$ matriz $A$ estamos construyendo debe tener $\det a A^T$ grande; el uso de que, encontramos por ejemplo que $f(15)\le 9$, ya que
$$(0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1)$$
resulta trabajar con $9$ rotaciones.
(Añadido 7/3/2015:)
Para la construcción de las soluciones para $k=31$ y $k=35$ pesajes de $n=50$ monedas, empecé mediante la ejecución de una subida de alrededor de $3$ veces, y recogió el patrón de dar la mayor $\det AA^T$. Como un primer cheque, miré a una reducción de la base para $\ker$ para comprobar que no tenía nada distinto de cero los vectores cuyas coordenadas fueron en más de $1$ en valor absoluto, y, a continuación, de forma exhaustiva facturado $\ker$ por ponerla en Hermite formulario por primera vez. Esto requiere la comprobación de alrededor de $(2/3)3^{n-k}$ vectores, que es fácil en un ordenador portátil. La ejecución por $k=31$ tomó cerca de $7 a$ horas $81$ veces tan largo como la ejecución por $k=35$.
Por cierto, sólo a partir de un examen visual de la reducción de las bases para los más pequeños valores de $k$, sospecho que $f(50)$ es de alrededor de $28$.
