The Broken Weight Problem

Some elderly academics were sitting next to me at the cafe today and they were discussing some mathematical puzzle, "The Broken Weight Problem." I'm not the best eavesdropper so I gathered a few search terms and popped them into Google, and viola.

Basically the idea is this. A merchant accepts goods in 40 pound increments. He uses a simple balance scale and a 40 pound weight to weigh the goods. One day, he accidentally dropped the weight and it broke into four pieces. After a bit of consideration, the merchant realized that, quite amazingly, each piece was an integer number of pounds in weight and, using his broken pieces of the weight and his balance scale, he was able to measure out any integer value from 1 to 40. The question is, what are the weights of the pieces? Hints and solutions after the break

---

Okay, a hint in case you are really stuck. You do realize that with a balance scale, the merchant is able to place some pieces on the other side of the scale which will act as a counter balance? This means that a five pound and a three pound piece can also measure two pounds, for example.

---

Now for solutions. Since we probably have a Common Lisp REPL close by, the easiest thing to do in this day and age is to just plug it in and have a computer solve it. But how do we do this? Well, it is simple enough using Screamer.

I start by grabbing a few libraries I will use, Iterate and, as mentioned, Screamer.

(ql:quickload '(:screamer :iterate))
(use-package :iterate)

First we define a test to see if a given set of piece weights can build an integer:

(defun check-integer (i w x y z)
  (iter (for s1 from (- w) to w by w)
    (finding
     s1 such-that
     (iter (for s2 from (- x) to x by x)
       (finding
        s2 such-that 
        (iter (for s3 from (- y) to y by y)
          (finding
           s3 such-that 
           (iter (for s4 from (- z) to z by z)
             (finding s4 such-that (= i (+ s1 s2 s3 s4)))))))))))

This function is pretty self explanatory. Given a set of weights, each weight can be in one of three places, on the right side of the scale, on the left side of the scale, or not on the scale at all. When applied to the balance of the scale (where zero means we have a balance) these states correspond to a negative value of the weight, a positive value of the weight, and a zero value for the weight. This is exactly what we are doing with these loops. Since there are only three states for each, it is simple to see that this will only require checking $3^{4}$ different possibilities at worst case.

Then we delve into the magic world of nondeterminism.

(screamer::defun stone-split (total-weight)
  (let* ((w (screamer:an-integer-between 1 (1+ total-weight)))
         (x (screamer:an-integer-between w (1+ total-weight)))
         (y (screamer:an-integer-between x (1+ total-weight)))
         (z (- total-weight w x y)))
    (if (and (> z 0)
             (iter (for i from 1 to total-weight)
               (let ((works (check-integer i w x y z)))
                 (always works))))
        (list w x y z)
        (screamer:fail))))

Here we are defining our function that will find zero, one, or several solutions to this problem depending on how we call it and if solutions exist. I left a free parameter total-weight so we can play with it, though it proves a bit boring to play with only that value. Things to note:

1. We need to use the defun from within the screamer package. This version of defun is special as it allows for simulated nondeterministic computation (via CPS I believe, but I'm not the guy to ask about that). The library suggests that you use screamer:define-screamer-package to make a package with the proper defun interned, but I am lazy.
2. The forms using screamer:an-integer-between tell Screamer that the solutions to this problem are some integer in that range. Screamer will handle figuring out which.
3. The screamer:fail form informs Screamer that it has chosen the wrong value. This will force Screamer to backtrack to the last integer range with values left and pick a new one.

We need to execute this function from within a "Nondeterministic Environment," which is commonly either inside a screamer:one-value or screamer:all-values form. So we invoke it like this ( fixed package namespace thanks to Derrell):

(screamer:one-value (stone-split 40))

…and it finds the correct result. Admittedly, this could be solved very simply without the use of Screamer, but I would argue that it requires less mental overhead when and produces much more flexible code using the Screamer route. What is the correct result?

---

I looked at it this way. You have three values a piece of weight $w$ can take, $-w$, 0, or $+w$. Therefore it seems to me that we have a set of equations:

\[ \alpha_i w + \beta_i x + \gamma_i y + \delta_i z = i ~~~~~\forall i \in {\mathbb N}_{1}^{40} \]

Where I use ${\mathbb N}_{1}^{40}$ to denote the natural numbers (starting from 1) less than or equal to 40. We know from the problem description that $w,x,y,z, \in {\mathbb N}_{1}^{40}$ and that $(\alpha, \beta, \gamma, \delta)+1 \in {\mathbb N}_{0}^{2}$. You could go about trying to solve these very over determined equations (edit: Actually it's underdetermined, hence we get multiple solutions. Limiting the values to integers is what makes it hard), however, this all might start looking familiar. This looks very much how you would calculate the value of a number in some (possibly irregular) base where the Latin symbols denote the value of each digit and the Greek symbols denote the value in that digit place. In this case, we are limited to three different values in our digit places, so it seems prudent to use base three. Thus the values of each digit place should be powers of three. Thus the answer should be 1, 3, 9, and 27.

How do we know we will have a solution? We need our trinary representation at least reach 40. Since half of our numbers are negative, we actually need to reach 80 in the positive only encoding. The largest value for four digits of trinary is (+ (* 2 27) (* 2 9) (* 2 3) (* 2 1)) or exactly 80. Also, it is a happy coincidence that our numbers also add up to 40, everything works just fine. If we look at how many unique solutions exist for other total weights we see that it seems that 40 is the largest weight we can get to with four pieces. This is a direct consequence of 80 being the largest 4 digit trinary number.

Total Weight	Number of unique solutions
4	1
5	1
6	2
7	3
8	4
9	5
10	7
11	7
12	9
13	10
14	10
15	11
16	12
17	11
18	12
19	12
20	11
21	11
22	12
23	9
24	9
25	9
26	7
27	7
28	7
29	5
30	5
31	5
32	3
33	3
34	3
35	2
36	2
37	2
38	1
39	1
40	1
41	0
42	0
43	0
44	0
45	0