Finding real money on an even stranger weighing device

You have $n$ coins which each weigh either $20$ grams or $10$ grams. Each is labelled from $0$ to $n-1$ so you can tell the coins apart. You have one weighing device as well. At the first turn you can put as many coins as you like on the weighing device and it will tell you exactly how much they weigh.

However, there is something really strange about the weighing device. If you put coins $x_1, x_2, ..., x_j$ on the device the first time, then the next time you have to put coins $(x_1+1), (x_2+1) , ..., (x_j+1) $ on the scale with the except that you of course can't put on a coin numbered higher than $n-1$. Not only that, for every new weighing you get to choose if you want to put coin $0$ on the scale.

In other words, all the weighings are defined by the choice of coins you choose to weigh the first time and the decision for every successive weighing about whether to add coin $0$ as well.

We want to separate the lighter coins from the heavier coins just by performing a number of weighings.

We can express our choices for each weighing as a matrix. Now we know, for example, that if we have $14$ coins it is possible to separate the two sets in only $8$ weighings as follows.

$$ \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} $$

The question is as follows:

What is the number of coins $n$ for which the minimum number of weighings needed to separate the light and heavy coins is less than $n/2$?

Hints

A previous related puzzle at Finding real money on a strange weighing device elicited some very clever ideas for how to solve this type of problem.

Here is a smaller example to get started with.

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

Solution 1:

This isn't really an answer, just the results of some initial investigations.

Let $f(n)$ be the minimum number of weighings required, and $g(n)$ be the minimum number of weighings under the further restriction that the weighings are fixed (not dependent on the weights of previous weighings). Clearly $f(n)\leqslant g(n)$.

Here are some values and bounds for small $n$. Note that for $n=6$ and $n=10$, $f(n)< g(n)$. It would be interesting to know whether $\limsup_{n\to\infty}g(n)-f(n)$ and $\liminf_{n\to\infty}g(n)-f(n)$ are finite or not. $$ \begin{array}{r|r|r|l} n & f(n) & g(n) & \text{possible first weighing} \\ \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} $$

Here's the Mathematica code I used. It's a recursive search, partitioning the possible coin vectors after each weighing. testAll[n,k] searches for solutions to $f(n)=k$; testAllM[n,k] searches for solutions to $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]