Encontrar dinero real en un extraño dispositivo de pesaje

Question

Usted tiene $n$ monedas cada una pesa $20$ gramos o $10$ gramos. Cada una está marcada desde $0$ a $n-1$ así que usted puede contar las monedas aparte. Tiene un peso del dispositivo así. En la primera vuelta usted puede poner tantas monedas como te gusta en la báscula y que le dirá exactamente cuánto pesan.

Sin embargo, hay algo muy extraño acerca de la báscula. Si pones las monedas de $x_1, x_2, ..., x_j$ en el dispositivo la primera vez, entonces la próxima vez que usted tiene que poner monedas $(x_1+1), (x_2+1) , ..., (x_j+1) $ en la escala con la excepción de que usted, por supuesto, no se puede poner en una moneda numerado más alto de $n-1$. No sólo que, por cada nuevo pesaje puedes elegir si quieres poner monedas $0$ en la escala.

En otras palabras, todos los pesajes se define por la elección de monedas que usted elija para sopesar la primera vez y la decisión para cada uno de los sucesivos que pesan sobre si añadir monedas $0$ así.

Queremos separar el encendedor de monedas de la más pesada de las monedas sólo mediante la realización de un número de pesajes.

Podemos expresar nuestras opciones para cada uno pesa como una matriz. Ahora sabemos, por ejemplo, que si tenemos un total de $14$ monedas es posible separar los dos conjuntos en sólo $8$ pesajes de la siguiente manera.

$$ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0\\ \end{pmatrix} $$

La pregunta es la siguiente:

¿Cuál es el número de monedas de $n$ para que el mínimo número de pesajes necesario para separar la luz y pesadas monedas es de menos de $n/2$?

Sugerencias

Una previa de puzzle en Búsqueda de dinero real en un extraño dispositivo de pesaje provocó algunas muy ingeniosas ideas de cómo resolver este tipo de problema.

---

Aquí hay un pequeño ejemplo para comenzar con.

$$ \begin{pmatrix} 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\\ \end{pmatrix} $$

Answer 1

Esto no es realmente una respuesta, sólo los resultados de algunas investigaciones iniciales.

Deje que $f(n)$ ser el mínimo número de pesajes necesario, y $g(n)$ ser el mínimo número de pesajes bajo la restricción de que los pesajes son fijos (no depende de los pesos de los anteriores pesajes). Claramente $f(n)\leqslant g(n)$.

Aquí están algunos de los valores y de los límites para la pequeña $n$. Tenga en cuenta que para $n=6$ y $n=10$, $f(n)< g(n)$. Sería interesante saber si $\limsup_{n\to\infty}g(n)-f(n)$ y $\liminf_{n\to\infty}g(n)-f(n)$ son finitos o no. $$ \begin{array}{r|r|r|l} n y f(n) y g(n) & \text{posible primer pesaje} \\ \hline 4 & 3 & 3 & 1100 \\ 5 & 4 & 4 & 01011 \\ 6 & 4 & 5 & 011101 \\ 7 & 5 & 5 & 0101011 \\ 8 & 6 & 6 & 10010101 \\ 9 & 6 & 6 & 010101110 \\ 10 & 6 & 7 & 1011000101 \\ 11 & 7 & 7 & 01010111010 \\ 12 & 7 & 7 & 100101110100 \\ 13 & 8 & 8 & 0001010111011 \\ 14 & 8 & 8 & 10010111001100 \\ 15 & \leqslant9 & \leqslant9 & 000101011101110 \\ 16 & \leqslant9 & \leqslant9 & 1000010111011100 \\ 17 & \leqslant10 & \leqslant10 & 00010101010111011 \\ 18 & \leqslant10 & \leqslant10 & 100001110101011001 \\ 19 & \leqslant11 & \leqslant11 & 0001010111010101110 \end{array} $$

Aquí está el código de Mathematica que he usado. Es una búsqueda recursiva, la partición de la moneda posible vectores después de cada pesaje. testAll[n,k] búsquedas de soluciones a $f(n)=k$; testAllM[n,k] búsquedas de soluciones a los $g(n)=k$.

allVectors[n_]:=allVectors[n]=Tuples[{0,1},n]
lastHalf[s_]:=s[[Length[s]/2+1;;]]
weightVectors[n_]:=weightVectors[n]=SortBy[lastHalf@SortBy[allVectors[n],Total],#.(n #+Array[Mod[#,2]&,n])&]
shiftWeightVector[w_]:={Join[{0},#],Join[{1},#]}&@Most@w
vectorString[v_]:=IntegerString[FromDigits[v,2],2,Length@v]
partitionVectors[vv_,w_]:=SortBy[GatherBy[vv,Dot[#,w]&],-Length[#]&]

test[{_},_,_]:=True
test1[v_,w_,s_]:=Module[{r=v.w},If[BitGet[s,r]==1,Throw[False],BitSet[s,r]]]
test[vv_,w_,1]:=If[Length[vv]>Total[w]+1,False,Catch[Fold[test1[#2,w,#1]&,0,vv];Throw[True]]]
test[vv_,w_,k_]:=Module[{w2=shiftWeightVector[w]},AllTrue[partitionVectors[vv,w],test[#,w2[[1]],k-1]||test[#,w2[[2]],k-1]&]]
testAll[n_,k_]:=vectorString/@Select[weightVectors[n],test[allVectors[Length@#],#,k]&,1]

testM[{_},_,_]:=True
testM[vv_,w_,1]:=If[Length[vv]>Total[w]+1,False,Catch[Fold[test1[#2,w,#1]&,0,vv];Throw[True]]]
testM[vv_,w_,k_]:=Module[{w2=shiftWeightVector[w],p=partitionVectors[vv,w]},AllTrue[p,testM[#,w2[[1]],k-1]&]||AllTrue[p,testM[#,w2[[2]],k-1]&]]
testAllM[n_,k_]:=vectorString/@Select[weightVectors[n],testM[allVectors[Length@#],#,k]&,1]