22

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

Community
  • 1
  • 3
    It looks like you are not adding (or not) coin $x_1$ from the previous weighing, but rather coin $0$? – Hagen von Eitzen Jul 08 '15 at 20:32
  • 1
    @HagenvonEitzen Thank you that was a mistake. Fixed. –  Jul 08 '15 at 20:48
  • @HagenvonEitzen Now it really is fixed :) –  Jul 08 '15 at 21:31
  • 2
    The battle of the monies. For how long hasn't humanity played this game? – mathreadler Jul 08 '15 at 21:36
  • 1
    The techniques described re the previous related puzzle all carry over essentially without modification. You now have a little more freedom in constructing the matrix, but none of the techniques in the other solution actually relied on the circulant structure, and the heuristic asymptotics provided by @joriki apply equally well here. – Tad Jul 09 '15 at 03:12
  • @Tad Yes. The main differences as I see them are a) I suspect you can find a solution with number of weighings $k< n/2$ for much smaller $n$ in this problem which might make things a lot easier b) if you want to find a constructive solution it is going to be completely different c) for a fixed $n$ and $k$ there are many more possibilities which might make things a lot harder. –  Jul 09 '15 at 05:41
  • @Tad I plotted a histogram of the determinant of $AA^T$ for all $A$ that could be a solution to this problem when $n=7$ and $k=5$. The two colours are whether the matrix is in fact a solution or not. It partly justifies your heuristic but I wonder if we can do better still http://i.imgur.com/DbfuS4B.png . –  Jul 09 '15 at 13:41
  • @Tad The $n=9$, $k=6$ case is more interesting... See http://i.imgur.com/zTlOCDJ.png . The maximal determinant of 1620 is reached only by matrices which are solutions. –  Jul 09 '15 at 16:01
  • @Lembik: Are you using my code for this? :-) – joriki Jul 09 '15 at 20:47
  • @joriki No sorry! I wrote my own which isn't anywhere near fast enough. –  Jul 09 '15 at 20:56
  • Well, you're welcome to, and let me know if you need help getting it to run. I'll be applying it to this new question but I don't have the time right now. – joriki Jul 09 '15 at 21:22
  • 1
    Using the given matrix, can a solution be found for any weighing numbers? – Grigory Ilizirov Aug 03 '15 at 14:42
  • As the matrix is not full rank I am puzzled how the 14 weight variables could be obtained from the summation (total weights) vector. I am looking for a smaller problem where one could distinguish the n weights from less than n measurements. – Abu Bakar Aug 04 '15 at 13:53
  • 1
    @Galaxy Try $ M= \begin{pmatrix} 1 & 0 & 1 & 1\ 1 & 1 & 0 & 1\ 1 & 1 & 1 & 0\ \end{pmatrix} $ –  Aug 05 '15 at 09:19
  • At each step there is the choice of including coin 0 or not. This decision can be made based on the weights of previous weighings. As far as I can see, none of the discussion takes this possibility (which makes the analysis considerably harder) into account. Perhaps there's some good reason to believe that this extra freedom makes no difference to the answer to the question. – David Bevan Aug 06 '15 at 17:42
  • @DavidBevan Any progress on either formulation would be really great! –  Aug 06 '15 at 17:52

1 Answers1

5

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]
David Bevan
  • 5,862