22
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ It looks like you are not adding (or not) coin $x_1$ from the previous weighing, but rather coin $0$? $\endgroup$ – Hagen von Eitzen Jul 8 '15 at 20:32
  • 1
    $\begingroup$ @HagenvonEitzen Thank you that was a mistake. Fixed. $\endgroup$ – user66307 Jul 8 '15 at 20:48
  • 2
    $\begingroup$ The battle of the monies. For how long hasn't humanity played this game? $\endgroup$ – mathreadler Jul 8 '15 at 21:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Tad Jul 9 '15 at 3:12
  • 1
    $\begingroup$ Using the given matrix, can a solution be found for any weighing numbers? $\endgroup$ – Grigory Ilizirov Aug 3 '15 at 14:42
5
$\begingroup$

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]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy