12
$\begingroup$

A puzzle I enjoyed, from the November 1983 issue of the American Mathematical Monthly:

Problem E3023: Proposed by J. G. Mauldon (a well-known retrograde analysis chess problem composer too!)

You are given an accurate indicating spring scale (not a balance) and seven coins, each of which weighs either x or y, where x and y are unknown. In five weighings, determine the weight of each coin.

I've had a peek at the two published solutions now. The first, case-based one is to me not very inspiring, but even the second solution by Mauldon himself (who unfortunately passed some years ago) is in my humble opinion not as cool and generalizable as the solution I will try to lead towards here.

Let's say to simplify things that we must specify the full set of 5 weighings right at the beginning. Letting the 7 weights be $a,b,c,d,e,f,g$, an example attempt of 5 weighings could be:

$c+d$
$d+e$
$a+b+c$
$e+f+g$
$b+f$

However this doesn't work because, supposing that the two coins weigh $1$ & $2$ then the following 2 assignments for the individual coin weights:

$1,2,1,2,2,1,1$
$1,1,2,1,1,2,1$

will both generate the results for the 5 weighings to be:

$3,3,4,4,3$

Often it's good idea to attack a problem by going for a simpler case first. Up to symmetry, there are exactly two solutions to identify 5 coins in 4 weighings. Here's one:

b+c+d+e
a+b+d
a+b+e
a+c

$\endgroup$
  • $\begingroup$ Maybe it's worth mentioning that the solution involves a very large tree of possibilities and a lot of patience. I didn't have so much patience and looked into the solutions published more than 5 years later. $\endgroup$ – A. P. Oct 14 '17 at 14:39
  • $\begingroup$ @A. P. Well, looking up the answers is one way to solve a published problem. The solution we ourselves found didn't involve any "tree of possibilties", and was much more compact. Thanks for the link to the published solutions, but I won't look at them yet. There's also the question of different numbers of coins and weighings. $\endgroup$ – Laska Oct 14 '17 at 15:51
  • 1
    $\begingroup$ Starting from smaller numbers of coins already shows how interesting this puzzle is. Even 4 coins seem to require a full 4 weighings. $\endgroup$ – humn Oct 14 '17 at 16:50
  • 1
    $\begingroup$ Do you happen to know an example solution for five coins that would take only 4 weighings, and has it been verified? $\endgroup$ – micsthepick Oct 17 '17 at 22:42
  • 1
    $\begingroup$ If it helps to know, @Laska, some of us haven't given up trying to crack this tasty nut of a puzzle and still have leads to follow before looking for more hints. Just your saying that in-print solutions are more complex than necessary is a big hint even without knowing anything more about those solutions. $\endgroup$ – humn Oct 21 '17 at 10:32
4
$\begingroup$

I wrote a computer program simply trying to:

1- Create all possible matrices which represents our $a$, $b$, $c$ values in a summation by $1$ or $0$ if they exist in the sum, such as below:

$\begin{bmatrix} 0 &0 &0 &1 &1 &0 &1 \\ 0 &0 &0 &0 &0 &0 &1 \\ 1 &0 &0 &1 &0 &0 &1 \\ 0 &0 &0 &0 &0 &1 &1 \\ 0 &1 &1 &0 &1 &1 &0 \\ 1 &0 &0 &1 &1 &0 &0 \\ 1 &0 &0 &1 &1 &0 &0 \end{bmatrix}\begin{bmatrix} a\\ b\\ c\\ d\\ e\\ f\\ g \end{bmatrix}= \begin{bmatrix} S_1\\ S_2\\ S_3\\ S_4\\ S_5\\ S_6\\ S_7 \end{bmatrix}$

So I represent everything as a matrix. In my program, It tries to create all possible combinations by using $1$ and $0$ and the program makes sure that every column has at least one $1$ and none of the rows are the same.

2- Secondly, I choose two values for our values ($a$,$b$,$c$,... etc.) and find our $S$ values for each possible two values. so there are $2^7$ possible values you can choose for your chosen matrix above. and every values I find $S$ sums. Let's say I choose $2$,$2$,$4$,$2$... etc

3- By using these $S$ values and the original matrix, I choose another two values which are different than our $a$, $b$, $c$,... (let say $3$,$1$,$1$,$3$...), and find other $S_t$ values.

4- Lastly, In part 3 if I encounter $S_t$ values which are the same $S$ values for each sum in part 2, I conclude that that matrix is not the matrix I need to use to find $a$,$b$,$c$, ... values since there could be other possible values satisfies the same conditions/equations.

If you are looking for 7 value and 5 equations, one of the possible answer becomes:

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

Here is the code, you can change ks and d values to find for different results, such as if you input ks as 5, and d as 4. You will get instant answers, but it takes about an hour to find a 7 and 5. The program can be optimized better, but it works without any problem at the moment.

Here is another solution:

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

Previous Solution

First weigh the first three:

$ w_1=a+b+c$

Then the other three:

$ w_2=d+e+f$

Then the some mix:

$w_3=a+e+f$

then the last mix:

$w_4=b+d+e$

we also have differences as an extra information among these $w$s. but what can we do with these differences, what kind of information can be gained?

Let's do the math:

There are a few possibilities for the $w$s: $3x$, $2x+y$, $x+2y$ and $3y$ and the differences could be $0$, $x-y$, $2x-2y$ and $3x-3y$. If you notice, the differences have some relation, the ratio between them is constant. So by using those $w$'s, we have the lots of relation we can find among $a,b,c,d,e,f$ except $g$ since we did not weigh it at all. Lastly we weigh our $g$ and find one of the weights! Then the rest becomes easily and quickly, for example let say:

$ w_1=7$

Then the other three:

$ w_2=15$

Then the some mix:

$w_3=11$

then the last mix:

$w_4=11$

and last weight:

$g=5$

from the difference between $w_2$ and $w_3$, it can be concluded that $a=1$ and $d=5$ since $g=5$. Moreover, from $g=5$, so you can easily say that $e=5$ and $f=5$. The only problem becomes $b$ and $c$. But since we have seperate results, $w_1$ and $w_4$, $b$ becomes $1$ and as a result $c=5$.

This is applicable to most kind of combinations.

$\endgroup$
  • $\begingroup$ Certainly will give you +1 for a brave effort. But I don't think the combinations you have chosen work out. If a...g are respectively 3,3,1,3,1,3,3 or 2,2,3,2,3,2,3 then you will still get the same results for your weighings: 7,7,7,7,3. (For verification, I am taking your weighings to be a+b+c, d+e+f, a+e+f, b+d+e, g). For those who were a bit baffled about the problem, this non-solution is probably a very good indication what we are trying to achieve. $\endgroup$ – Laska Oct 14 '17 at 16:36
  • 1
    $\begingroup$ @Laska you are right, i need to edit the methodology after getting 2 or 3 equal ws, i believe it is possible to overcome this situation. $\endgroup$ – Oray Oct 14 '17 at 16:47
  • 1
    $\begingroup$ @Laska seems my program has a little bug :) i will update the answer... $\endgroup$ – Oray Oct 30 '17 at 7:52
  • 1
    $\begingroup$ @Laska I believe that I have fixed the bug in my program, could you recheck again? If there is no bug left, I will share my code. $\endgroup$ – Oray Oct 30 '17 at 14:42
  • 1
    $\begingroup$ Hi I think your latest solution works :D $\endgroup$ – Laska Oct 30 '17 at 16:14
2
$\begingroup$

weigh all 7. ax+by=c ; a+b=7 weigh 5. ax+by+d=c ; a+b=5 Determine the total wight of the two coins off the scale (i.e. d). weigh 3 ax+by+d+e=c ; a+b=3 Determine the total weight of the new two coins off the scale (i.e. e) weigh 1 coin. ax+d+e+f=c ; a=1 Determine the total weight of the new two coins off the scale (i.e. f) detemine x as the value of this last coin.

Subtract x from each d, e, f.

if d=2x or e=2x or f=2x, we know for certain both coins weigh x.

where d!=2x or e!=2x or f!=2x, we know for certain at least one corresponsing coin weighs y.

given d!=2x, if e!=d and e!=2x, d=2y or d=y+x and e=2y iff d!=2y.

Therefore for the fifth and final weighing, weigh 1 coin from d along with the final coin, which is x. We can now deterimine all the weights of the coins by knowing if d=2y, or d=y+x

$\endgroup$
  • $\begingroup$ If I’ve understood you properly, then I don’t think your solution can work. For example there is no weighing in which only one of the two coins that make up e appears. So if one is x and one is y, we can’t tell which is which. By the way in my own thinking, I have always been assuming that one weighing is never a strict subset of another so e.g. I would never weigh 7 and then 5 but instead 2 and then 5. It’s equivalent but simpler. $\endgroup$ – Laska Oct 18 '17 at 20:13
  • $\begingroup$ >For example there is no weighing in which only one of the two coins that make up e appears. // I see what you mean! $\endgroup$ – J Mark Inman Oct 18 '17 at 21:31
2
$\begingroup$

(This initial write-up is half rushed, late in the day. More write-up is half ready.)

A nearly complete solution, with an incomplete (for now) explanation

This refreshingly juicy puzzle would be a lot easier with unlimited copies of each coin but, alas, only one of each is available.   What to do?   Simulate multiple copies (in stage 3)!   Here’s how.
  Stage 1. Weigh 5 specific combinations of the 7 coins.
  Stage 2. Determine the mystery weights, x and y.
  Stage 3. Determine which coins weigh x and which weigh y.

Assume that x < y and that each of these weights is represented by at least one coin. (A future edit is planned to justify this assumption.)

Stage 1. Weigh 5 specific combinations of the 7 coins.


             P  =                       f + g
             Q  =           c   +   e   +   g
             R  =       b   +   d + e   +   g
             S  =   a     +     d + e   +   g
             T  =   a + b + c + d + e + f    


 Example:    x  =  1.1  =  a, b, c, d, f
             y  =  3.3  =  e, g

             P  =                                 1.1 + 3.3   =    4.4
             Q  =               1.1    +    3.3    +    3.3   =    7.7
             R  =         1.1    +    1.1 + 3.3    +    3.3   =    8.8
             S  =   1.1       +       1.1 + 3.3    +    3.3   =    8.8
             T  =   1.1 + 1.1 + 1.1 + 1.1 + 3.3 + 1.1         =    8.8
 


Stage 2. Determine the mystery weights, x and y.

This stage is admittedly sketchy, but go ahead and scale the weighings’ results as specified, then stretch and translate those scaled weighings to fit on the displayed grid.   The grid will indicate what coefficients to use in a set of linear equations that solve for x and y.

     Scaled weighings to align         Fit them onto the vertical bars in this grid

                                     0      1/6 1/4 1/3     1/2     2/3 3/4 5/6      1
                                     .       .   .   .       .       .   .   .       .
               6P                   2|0      .   .          1|1          .   .      0|2
               4Q                   3|0      .      2|1      .      1|2      .      0|3
               3R                   4|0         3|1  .      2|2      .  1|3         0|4
               3S                   4|0         3|1  .      2|2      .  1|3         0|4
               2T                   6|0     5|1  .  4|2     3|3     2|4  .  1|4     0|6
                                     .       .   .   .       .       .   .   .       .
                                     .       .   .   .       .       .   .   .       .
  Example:                           .       .   .   .       .       .   .   .       .
                                     .       .   .                       .   .       .
     6P  =  6(4.4)  =  26.4          |       .             26.4              .       |
     4Q  =  4(7.7)  =  30.8          |               |       .     30.8              |
     3R  =  3(8.8)  =  26.4          |           |   .     26.4      .   |           |
     3S  =  3(8.8)  =  26.4          |           |   .     26.4      .   |           |
     2T  =  2(8.8)  =  17.6          |     17.6  .   |       |       |   .   |       |


     Equations     /   P  =  4.4  =  1x + 1y    (because  6P = 26.4  aligns with "1|1")
     indicated    /    Q  =  7.7  =  1x + 2y    (   "     4Q = 30.8       "      "1|2")
     by numbers  <     R  =  8.8  =  2x + 2y    (   "     3R = 26.4       "      "2|2")
     at vertical  \    S  =  8.8  =  2x + 2y    (   "     3S = 26.4       "      "2|2")
     bars above    \   T  =  8.8  =  5x + 1y    (   "     2T = 17.6       "      "5|1")

     This solves to    x = 1.1  and  y = 3.3
 


Stage 3. Determine which coins weigh x and which weigh y.

This determined how to select coins for the weighings and was especially fun to work out.   Calculate N by combining all five weighings.


           N  =  (62P + 15Q + 13R + 12S - 11T - 203x) / (y-x)


Example:   N  =  (62(4.4) + 15(7.7) + 13(8.8) + 12(8.8) - 11(8.8) - 203(1.1)) / 2.2
              =  131

Now decompose N into...


           N  =   1A  +  2B  +  4C  +  14D  +  29E  +  51F  +  102G

           ...where A, B, C, D, E, F and G are each either 0 or 1.

           This interprets N as a mixed-base binary-digit number, each
           digit of which tells whether its corresponding coin weighs x or y.


Example:  131 =  1(0) + 2(0) + 4(0) + 14(0) + 29(1) + 51(0) + 102(1)

   Thus     A = B = C = D = F = 0         and   E = G = 1

     so     a = b = c = d = f = x = 1.1   and   e = g = y = 2.2

It’ll be fun to explain this better in a future edit but, for now, the approach can be summarized by saying that it simulates a single weighing that includes multiple copies of each coin.

                      f g  -.
                      f g   |
                      f g   |
                      f g   |  J = 62 copies of weighing P
                      f g   |
                      f g   |
                      f g   |
                       :   -'
                c . e . g  -.
                c . e . g   |
                c . e . g   |  K = 15 copies of Q
                c . e . g   |
                c . e . g   |
                     :     -'
              b . d e . g  -.
              b . d e . g   |
              b . d e . g   |  L = 13 copies of R
              b . d e . g   |
                    :      -'
            a . . d e . g  -.
            a . . d e . g   |  M = 12 copies of S
            a . . d e . g   |
                   :       -'
         -  a b c d e f .  -.
         -  a b c d e f .   |  N = 11 copies of T, which are subtracted
         -  a b c d e f .   |
                  :        -'
       --------------------------
        (M-N)a + (L-N)b + (K-N)c + (L+M-N)d + (K+L+M-N)e + (J-N)f + (J+K+L+M)g

    This simulates a weighing with the following numbers of coins:

    1 x a,  2 x b,  4 x c,  14 x d,  29 x e,  51 x f,  102 x g
 

The goal was to have more copies of each successive coin than the combined number of all (alphabetically) previous coins.   Material is being written up to demonstrate how the 5-coins-and-4-weighings version of this puzzle was solved and how that led to this solution.

$\endgroup$
  • $\begingroup$ Typo up there: After decomposing N, 𝑒 = 𝑔 = 𝑦 = 2.2 should be 𝑒 = 𝑔 = 𝑦 = 3.3 $\endgroup$ – humn Oct 28 '17 at 23:02
  • $\begingroup$ thanks for your continuing energy. The solution you propose for 7 weighings and 5 coins is incorrect. For example 3,3,3,3,1,1,3 & 2,2,2,3,3,2,2 both yield weighings 4,7,10,10,14. Please publish your 5 by 4 solution. $\endgroup$ – Laska Oct 30 '17 at 8:09
  • 1
    $\begingroup$ Wow, @Laska, good counter-example, it reveals how important the identification of X and y are. I keep finding more and more interesting ways to identify which coin is which after knowing x and y, though, and am still having too much fun to ask for hints. Thank you for such an intriguing twist on coin-weighing puzzles. $\endgroup$ – humn Nov 2 '17 at 4:25
1
$\begingroup$

I've been playing with this all day, and I'm afraid I do not have the math to back this answer up. I've done enough guess-and-check, but feel free to explain to me how this works (if it does):

I chose to start from the "center". The first task is to figure out what the difference between x and y is, and from there, weigh the coins such that they are intertwined:

Given coins $a, b, c, d, e, f,$ and $g$

  1. $c + d$
  2. $d + e$

If 1 and 2 weigh differently, then this is the difference in weight between $c$ and $e$. There is still an issue with various factorizations, but knowing the sum really cuts things down.

  1. $a + b + c$
  2. $e + f + g$

If 1 and 2 did not produce $x$ and $y$, then these will (I think).

Finally, step 5 figures out the correct placement of $x$ and $y$ within $a, b, f,$ and $g$

  1. $b + f$

I think this pattern hold with more coins. For example, if $g$ is known, and we add $h$ and $i$, then one weighing is $g + h + i$, and the other is $a + h$ to get the correct order. As more letters are added, the original pivot point would need to be moved to the center (adding $j$ and $k$ would require the first two weighings to include $d, e,$ and $f$.

$\endgroup$
  • $\begingroup$ +1 for a solid attempt, but I know already it's not going to work out. It will take more space than I have here, so I will put it in the base post. $\endgroup$ – Laska Oct 16 '17 at 8:08
  • 1
    $\begingroup$ If {a=d=g=x, b=c=e=f=y} then your weighings give the results (x+y,x+y,x+2y,x+2y,2y). However you get the same results with {a=b=d=g=f=y, c=e=x}, so it does not distinguish between these two cases. $\endgroup$ – Jaap Scherphuis Oct 16 '17 at 8:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.