26
$\begingroup$

You have 50 coins which each weigh either 20 grams or 10 grams. Each is labelled from 0 to 49 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 strange about the weighing device. If you put coins $x_1, x_2, ..., x_j$ on the device the first time, then you have to put coins $(x_1+1) \bmod 50, (x_2+1) \bmod 50, ..., (x_j+1) \bmod 50$ on the scale the next time, and coins $(x_1+2) \bmod 50, (x_2+2) \bmod 50, ..., (x_j+2) \bmod 50$ the next time and so on. In other words, all the weighings are defined by the choice of coins you choose to weigh the first time.

Under this rule, what is the smallest number of weighings that will always tell you exactly which coins weigh 10 grams and which weigh 20?

Clearly you could just put one coin on the device in the first turn and then it would take exactly $50$ weighings to solve the problem.


Here is an example when you have only $4$ coins that takes only $3$ weighings. First put coins $1$,$2$ and $3$ on the scale. For the next weighing you will have coins $0$, $2$ and $3$. For the last weighing you will have coins $0$, $1$ and $3$ and you will then know exactly which coins are real and which are fake.


Here is another example when you have $9$ coins that takes only $6$ weighings. First put coins $2,5,7,8$ on the scale (indexing from $0$ again).

Answers so far (smaller is better)

  • 38 by san
  • 35 by Tad
  • 31 by Tad
  • 26 by joriki
  • 25 by joriki (A very impressive record!)
$\endgroup$
  • $\begingroup$ How is your example better than just weighing 1 coin at the time? In three weighing you know exactly which coins weigh 20 and which weigh 10. $\endgroup$ – Conrado Costa Jun 30 '15 at 12:34
  • $\begingroup$ @ConradoCosta If you put one coin on the scale you need 4 weighings as you weigh each coin individually. In my example that is reduced to 3. $\endgroup$ – user66307 Jun 30 '15 at 13:25
  • $\begingroup$ In the case of $4$ coins. do you know how many weigh $20$ and how many weigh $10$? If you do then with $3$ weighing you will have found $2$ coins of the same weight. If you are lucky you may need only $2$ weighings. Or I am missing something? $\endgroup$ – Conrado Costa Jun 30 '15 at 15:21
  • $\begingroup$ @ConradoCosta No you know nothing about how many weigh 10 or 20 in advance. All the information you get has to be obtained by weighings. $\endgroup$ – user66307 Jun 30 '15 at 15:23
  • 5
    $\begingroup$ If you let $f(n)$ denote the minimal number of weighings, for a number $n\ge1$ of coins, the sequence $\{f(n)\}$ starts like this: $1,2,3,3,4,5,6,6,6,7,7,8,\ldots$ This sequence does not appear in OEIS. $\endgroup$ – Tad Jul 1 '15 at 3:52
8
+100
$\begingroup$

Update: I've now found two solutions that require only $25$ weighings:

$$ 01011011100010111101000001100111110011010100011010\;,\\ 00101110001101001010111110001000110010011111011101\;. $$

These are the only solutions known (in the context of this post) with $k=n\,/\,2$, for any $n$. I found them using Tad's recipe of repeatedly maximizing the determinant of $AA^\top$ by hill climbing and testing the candidate with the highest determinant among several runs. The determinants are

$$ 87546852131623099566361867104\;,\\ 93001686149176479553585114299\;. $$

I only had to test half a dozen candidates to find these two solutions, which seems consistent with $f(50)\simeq 22.4$. I'll now be testing these two with $24$ weighings; that will take the better part of a day and will require a bit more than a trillion difference vectors to be checked in each case.


I believe the bounty should go to Tad, who developed the mathematical approach. I tried to improve on it but couldn't, so instead I coded it a whole lot faster :-). Here's the code. It uses a special bit encoding for efficient arithmetic with vectors over $\mathbb F_3$. On my MacBook, it takes half a minute to test a candidate with $31$ weighings and two hours for a candidate with $26$ weighings.

The best solution it's found so far is $01010111100010011111110000111011000101101100100001$, with $26$ weighings required. I'm now looking for solutions with $25$ weighings, but that requires up to six hours of testing per candidate. I expect the minimum to be near $23$ (see below). I haven't implemented Tad's determinant maximization approach yet; the above solution was just the third candidate I tried with uniform sampling among the vectors (uniform sampling among the rotational equivalence classes would be worse since it gives higher weight to periodic sequences).

Here's a short summary of the mathematical basis of the code, mostly following Tad's ideas and notation; $n$ is the number of coins, and $k$ is the number of weighings. We can treat the two weights of the coins as $0$ and $1$. Then every possible weight configuration is characterized by a binary weight vector, and the differences between weight vectors are ternary vectors with entries $-1$, $0$ and $+1$. A solution is admissible if the $k\times n$ matrix $A$, with entries $A_{ij}\in\{0,1\}$ according as coin $j$ is weighed in weighing $i$, has different products with all possible weight vectors, or equivalently, if its product with all possible difference vectors is non-zero.

We can regard the difference vectors as vectors over $\mathbb F_3$. Only the difference vectors in the kernel of $A$ over $\mathbb F_3$ can be in the kernel of $A$ over $\mathbb Z$. The kernel over $\mathbb F_3$ will generally contain $3^{n-k}$ difference vectors, and these we have to check over $\mathbb Z$ (actually only half of them, due to invariance under negation). The key to doing this efficiently is to bit-encode $\mathbb F_3$ such that the time-limiting steps (addition, componentwise multiplication and summation of vectors) can be performed compactly using integer operations and table lookups instead of iterating over $n$ vector components.

Here are some results that expand on Tad's results for values well below $50$. $n_\text{c}$ is the number of equivalence classes under rotation; the numbers in the header row are $n-k$, and the numbers in the bodies of the two tables are the numbers and fractions, respectively, of rotational equivalence classes that yield a solution.

\begin{array}{c|c|cc} n_\text{c}&n&0&1&2&3&4&5&6&7&8&9\\\hline 2&1&1\\ 3&2&1\\ 4&3&2\\ 6&4&2&1\\ 8&5&6&3\\ 14&6&6&4\\ 20&7&18&12\\ 36&8&20&17&8\\ 60&9&50&45&25&6\\ 108&10&74&71&56&17\\ 188&11&186&178&130&83&4\\ 352&12&216&214&200&135&42\\ 632&13&630&614&520&469&261&6\\ 1182&14&916&910&878&787&535&101\\ 2192&15&2002&1988&1924&1831&1427&648&22\\ 4116&16&3040&3037&3000&2926&2605&1686&330&2\\ 7712&17&7710&7699&7464&7330&6915&5361&2131&34\\ 14602&18&10806&10801&10760&10649&10310&9014&5547&875\\ 27596&19&27594&27582&27270&27110&26565&24773&18964&7307&152\\ 52488&20&40642&40639&40592&40474&40024&38487&33414&20254&3102&2\\ 99880&21&94658&94640&94440&94281&93518&91759&85546&65010&24368&508\\ \end{array}

\begin{array}{c|c|cc} n_\text{c}&n&0&1&2&3&4&5&6&7&8&9\\\hline 2&1&.5000\\ 3&2&.3333\\ 4&3&.5000\\ 6&4&.3333&.1667\\ 8&5&.7500&.3750\\ 14&6&.4286&.2857\\ 20&7&.9000&.6000\\ 36&8&.5556&.4722&.2222\\ 60&9&.8333&.7500&.4167&.1000\\ 108&10&.6852&.6574&.5185&.1574\\ 188&11&.9894&.9468&.6915&.4415&.0213\\ 352&12&.6136&.6080&.5682&.3835&.1193\\ 632&13&.9968&.9715&.8228&.7421&.4130&.0095\\ 1182&14&.7750&.7699&.7428&.6658&.4526&.0854\\ 2192&15&.9133&.9069&.8777&.8353&.6510&.2956&.0100\\ 4116&16&.7386&.7379&.7289&.7109&.6329&.4096&.0802&.0005\\ 7712&17&.9997&.9983&.9678&.9505&.8967&.6952&.2763&.0044\\ 14602&18&.7400&.7397&.7369&.7293&.7061&.6173&.3799&.0599\\ 27596&19&.9999&.9995&.9882&.9824&.9626&.8977&.6872&.2648&.0055\\ 52488&20&.7743&.7743&.7734&.7711&.7625&.7333&.6366&.3859&.0591&.0000\\ 99880&21&.9477&.9475&.9455&.9439&.9363&.9187&.8565&.6509&.2440&.0051\\ \end{array}

Here are the minimal $k$ values up to $n=26$ (denoted by $f(n)$ as in Tad's table), together with the numbers and fractions of solution classes at minimal $k$:

\begin{array}{c|c|c|c} n&f(n)&\#&\#\,/\,n_\text{c}\\\hline 1&1&1&.5000\\ 2&2&1&.3333\\ 3&3&2&.5000\\ 4&3&1&.1667\\ 5&4&3&.3750\\ 6&5&4&.2857\\ 7&6&12&.6000\\ 8&6&8&.2222\\ 9&6&6&.1000\\ 10&7&17&.1574\\ 11&7&4&.0213\\ 12&8&42&.1193\\ 13&8&6&.0095\\ 14&9&101&.0854\\ 15&9&22&.0100\\ 16&9&2&.0005\\ 17&10&34&.0044\\ 18&11&875&.0599\\ 19&11&152&.0055\\ 20&11&2&.0000\\ 21&12&508&.0051\\ 22&12&8&.0000\\ 23&13&2340&.0064\\ 24&13&36&.0001\\ 25&14&10688&.0080\\ 26&14&216&.0001 \end{array}

The solution class counts of $2$ for $n=16$ and $n=20$ that both come at the end of an unusual triple of identical values of $f(n)$ are salient; here are the solution vectors:

$$ 0000101110111011\;,\\ 0000110111011101\;,\\ 00000101111011110111\;,\\ 00000111011110111101\;.\\ $$

Note that in both cases the two solutions are related by inversion, they contain slightly longer runs of $0$s than of $1$s, and the runs of $1$s are separate by single zeros.

It's tempting to speculate that the bound $f(n)\gt n/2$ that holds up to $n=26$ will continue to hold for higher $n$. However, I don't believe that this is the case. There's already a slight indication of this in the data; the solutions are gradually encroaching on the bound. (The trends in the absolute numbers are relevant here, not in the fractions, since we only need a single solution.) The fact that the third uniformly randomly guessed candidate turned out to be a solution for $k=26$, $n=50$ also points in this direction, since it suggests that the density of solutions at that point is much higher than it is for $k=n/2-1$ at lower $n$ values (where it's almost negligible).

Moreover, statistical considerations suggest that the asymptotic behaviour of $k$ might be $n\,/\log n$. There are various handwaving arguments that could be used to support this, based on entropy or collision probabilities; the details may be hard to get right, but the bigger picture is the same in each case: The $k$ measurements each have an effective space of order some power $n^\alpha$ to spread across ($\sqrt n$ if we consider them to be binomially distributed), so our discerning ability grows with $n^{\alpha k}$, while the number of possibilities we need to be able to discern grows with $2^n$; equating the logarithms yields $\alpha k\log n=n\log2$ and thus $k\propto n\,/\log n$.

Such $n\,/\log n$ behaviour seems consistent with the data up to $n=26$, so we can get a rough estimate e.g. from $f(26)=14$:

$$f(50)\simeq\frac{50\log26}{26\log50}\,f(26)\simeq1.6\,f(26)\simeq22.4\;.$$

That leaves ample space for improvement. :-)

$\endgroup$
  • 1
    $\begingroup$ I agree completely about $k=n/2$. Let me change my acceptance criterion to that. $\endgroup$ – user66307 Jul 6 '15 at 8:34
  • 1
    $\begingroup$ @Lembik: Progress report: I implemented Tad's hill climbing for $\det AA^T$, and the four tests that I'm running with high-determinant patterns (in parallel on a quad-core processor) are all succeeding so far -- so we may well have a $k=25$ solution in six hours... $\endgroup$ – joriki Jul 6 '15 at 9:29
  • 1
    $\begingroup$ @Lembik: I put the entire code on github: github.com/joriki/algebra. It should be self-contained in that form. Please let me know if there are problems compiling or running it or if you have suggestions for improving it. $\endgroup$ – joriki Jul 6 '15 at 13:02
  • 1
    $\begingroup$ @Lembik: P.P.S.: I forgot to mention: There's a slightly different version of Question1341400.java in that repository because I had to move a class in the process. I also added a main method to show how to use the code. You'll need to use that version and ignore the first one in the gist. $\endgroup$ – joriki Jul 6 '15 at 13:17
  • 2
    $\begingroup$ @Joriki: Great exposition! +1 for you and Tad of course. I'm pretty sure there is also a strong connection with coding theory especially error detecting codes. It would be nice to also find a thread in this direction. $\endgroup$ – Markus Scheuer Jul 7 '15 at 5:55
5
+200
$\begingroup$

The following pattern works with $31$ weighings: $${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}.$$ This beats the $35$-weighing solution found earlier. $${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}.$$ See the comments at the end of this post.

This is not a complete answer, but it won't fit in a comment. We define $f(n)$ to be the smallest number of weighings possible for $n$ coins. Here is some simple but not particularly efficient Mathematica code which computes $f(n)$ for small $n$ by brute force: pick a representative $x$ of a rotational equivalence class of $n$-long $\{0,1\}$-vectors, build a matrix out of $k$ successive rotations of $x$, hit that matrix against all $\{0,1\}$-vectors, and see if all $2^n$ results are distinct. There are roughly $2^n/n$ rotation classes, so the complexity of this is about $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{Example} & \text{$\#$ of examples} \\ 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}$$

This quickly becomes infeasible. However, checking a given vector costs "only" $2^n$ matrix multiplies, so we can get some upper bounds for $f(n)$ by guessing good vectors $x$. A reasonable heuristic is that the $k\times n$ matrix $A$ we're constructing should have $\det A A^T$ large; using that, we find for example that $f(15)\le 9$, since $$(0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1)$$ turns out to work with $9$ rotations.

(Added 7/3/2015:) To construct the solutions for $k=31$ and $k=35$ weighings of $n=50$ coins, I started by running a hill-climb about $3$ times, and picked the pattern giving the largest $\det AA^T$. As a first check, I looked at a reduced basis for $\ker A$ to check that it didn't have any nonzero vectors whose coordinates were at most $1$ in absolute value, and then exhaustively checked $\ker A$ by putting it into Hermite form first. This requires checking about $(2/3)3^{n-k}$ vectors, which is easy on a laptop. The run for $k=31$ took about $7$ hours, $81$ times as long as the run for $k=35$.

Incidentally, just from a visual examination of the reduced bases for smaller values of $k$, I suspect that $f(50)$ is about $28$.

$\endgroup$
  • $\begingroup$ Your heuristic is very interesting! If you plot $AA^T$ for all the weighings you tested for $n=12$, $f(n)=8$ do you see the ones that work at the peak? $\endgroup$ – felix Jul 2 '15 at 7:20
  • $\begingroup$ I mean the determinant of $AA^T$ of course. $\endgroup$ – felix Jul 2 '15 at 7:53
  • 2
    $\begingroup$ @san I think we can regard joriki's answers as computer aided proofs. You have to check the code that finds the answers. $\endgroup$ – felix Jul 6 '15 at 16:17
  • 1
    $\begingroup$ @Tad: Very nice and instructive answer! +1 for you and Joriki $\endgroup$ – Markus Scheuer Jul 7 '15 at 6:06
  • 2
    $\begingroup$ Very nice comment with the bounty. I found a proof that $f(n) \geq 2n/\log_2{n}$ in Probabilistic methods in combinatorics. By Paul Erdös and Joel Spencer Academic Press, Inc., New York 1974 $\endgroup$ – user66307 Jul 7 '15 at 6:17
4
$\begingroup$

This is an elementary approach, but for larger numbers, it is more computable than the total approach given by Tad. So probably this is far from being optimal: If you first weigh the coins $0$, $12$ and $25$ it takes 38 weighings according to the rule, so you can tell all coins apart.

Proof: Set $w_i$ the weigh of the $i$'th coin, and $M_j$ the result of the $j$th weighing. So you know all $M_j$ for $j=1,\dots,38$ and want to know $w_i$ for $i=0,\dots,49$. We have $M_1=w_0+w_{12}+w_{25}$, $M_2=w_1+w_{13}+w_{25}$,...,$M_{38}=w_{37}+w_{49}+w_{12}$.

Now $M_1-M_{26}=w_{12}-w_{37}$, so, if $w_{12}\ne w_{37}$, we know the value of both. If they are equal, consider the weighing $M_{13}=w_{12}+w_{24}+w_{37}$. If both are equal to 10, then $M_{13}=30$ or $M_{13}=40$ and if both are 20, then $M_{13}=50$ or $M_{13}=60$. You also learn the value of $w_{24}$, even in the case that they are different.

Similarly, from $M_{2}-M_{27}$ and $M_{14}$ you determine $w_{13}$, $w_{25}$ and $w_{38}$ and from $M_{3}-M_{28}$ and $M_{15}$ you determine $w_{14}$, $w_{26}$ and $w_{39}$. Continue with this reasoning until you determine $w_{23}$, $w_{35}$ and $w_{48}$ (using $M_{12}-M_{37}$ and $M_{24}$).

So you have determined $w_{12},\dots,w_{35}$, and $w_{37},\dots,w_{48}$. Now from $M_{38}=w_{37}+w_{49}+w_{12}$ you obtain $w_{49}$ and from $M_{25}=w_{24}+w_{36}+w_{49}$ you obtain $w_{36}$.

Finally, from $M_{1},\dots,M_{12}$ you obtain $w_0,\dots,w_{11}$, since you know already two individual weights in each case. This determines all the weights.

Note that with this starting weighing, 38 is the least number you need to determine all weights, since 37 weighings cannot tell apart the coin vector $V_1$ that is 10 for all coins except the coin 36 with weight 20, and the coin vector $V_2$ with all coins weighing 10 except for the coins 11 and 49 which weigh both 20.

Note: This elementary method gives the following numbers:

If $n=4k$, starting from $(0,k,2k)$, you need $3k$ weighings.

If $n=3k$, starting from $(0,1,k,2k)$, you need $2k$ weighings if $k$ is odd, and $2k+1$ weighings, if $k$ is even.

If $n=4k+2$ you need $3k+2$ weighings, starting from $(0,k,2k+1)$.

For prime numbers the method doesn't work. Else you take a divisor $d<n/3$ of $n$ and you need $n-d$ weighings.

$\endgroup$
  • $\begingroup$ Thank you very much for being the first improvement! $\endgroup$ – user66307 Jul 2 '15 at 17:21
0
$\begingroup$

For $n\gt3$ the least number of weighings is $n-1$. All versions use the combinations of $n-1$ coins missing one, and a repeated weighing of the remaining coin.

If we analyse the original example, we can add up the total of the $3$ weighings. This gives us:

$2\times$(weight of coin $0$+weight of coin $1$+weight of coin $2$) $+3\times$weight of coin $3$. (I have used weights of $1$ and $2$ instead of $10$ and $20$.)

The sum of the first $3$ coins is from $\{3,4,5,6\}$ and so may take the values $\{6,8,10,12\}$, and the final coin provides either $3$ or $6$, giving the final set of possible weighings as $\{9,11,13,15,12,14,16,18\}$, or sorted: $\{9,11,12,13,14,15,16,18\}$.

So we take the $3$ weighings and add up the totals. Now because we have an even number of the first $3$ coins, we can determine the weight of the last coin as odd or even. This value can be removed from the original equations giving $3$ equations in $3$ unknowns, which have a solution.

For example if our three weighings give $5,5,6$, the totals weight is $16$. If the final coin weighed $1$, we would have $2\times(c_0+c_1+c_2)=13$, which is impossible. We infer the final coin must weigh $2$, so we have:

$$ c_0+c_1=3$$ $$ c_0+c_2=3$$ $$ c_1+c_2=4$$

which has the unique solution $c_0=1, c_1=2, c2=2$.

To generalize this, we can see that a solution set comes from:

$$(n-2)\{n-1,\dots,2n-2\}+(n-1)\{1,2\}$$

A possible weighing is unique modular $(n-2)$, and so we can determine the weight of the last coin by leaving a total weighing $0\mod(n-2)$, which leaves $(n-1)$ equations in $~(n-1)$ unknowns, which has a unique solution.

For example, with $5$ coins, we have the possible weights $\{4,5,6,7,8\}$ from the $4$ coins, and the total weighing is $3\times(c_0+c_1+c_2+c_3)+4\times c_4$. So the final total weighing will be either $3k+1$ or $3k+2$, telling us the value of $c_4$.

Because the range of coin wieghts is limited, a solution with more coins can often be achieved with less weighings than this. The variables are the number of coins used in weighings, the number of weighings and the possible weights of the coins.

$\endgroup$
  • 1
    $\begingroup$ For 9 coins it seems we only need 6 weighings. Include coins 2, 5, 7 and 8 in the first weighing (indexing from 0). $\endgroup$ – user66307 Jul 1 '15 at 6:32
  • $\begingroup$ @Lembik; ok i can see what you mean now!, i changed the last para, so this i suppose isn't a solution, but i think the maths is ok and on the right track.. $\endgroup$ – JonMark Perry Jul 2 '15 at 4:13
  • $\begingroup$ @JonMarkPerry If you assume $x_i=i$, then your solution is correct, although it is easier to start weighting $1,2,3$ and then make $n-1$ weighting according to the rule. $\endgroup$ – san Jul 2 '15 at 14:49

Your Answer

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