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

On LaTeX and Microsoft Word

Sorry, this is a ranty post. Adjust your desire to read appropriately.

I was busy writing my APS abstract this last week. When we got near the end I was having a heck of a time getting Bibtex to work with Latex and insert my references properly. Later on I realized that APS doesn't really allow for citation ala Latex and Bibtex, but whatever. I was struggling with this, and mentioned to my advisor, jokingly, "Man, I hate Latex." He says, also jokingly, "you could use Microsoft Word." I say sure, despite the fact that the APS website says they prefer Latex and that Latex is actually easier for the submitter, MS Word is no problem. In fact, that is kind of the point. I wrote my abstract using Org-Mode precisely because it made little to no assumptions on the end result. I can export to Latex or one of the many other formats or just grab my text and paste it into MS Word with no problems. I can also send it to any human being in the world with a computer and that person can open it and understand what they are seeing. Hell, in a handful of keystrokes I could post it to this blog.

Later, when printing, my advisor changes from his joking suggestion to insist that I use MS Word (presumably so that I can export to a Rich Text Format document that the APS accepts). This will make it easier, right… So, I copy/paste it over to a document and save it as an RTF file. Low and behold, of course, the equations are not interpreted by word. It would take at least 15 minutes and perhaps up to an hour to figure out how to get the proper symbols, fonts, and kerning into the document for submission. The last kick to the nuts is that the APS provides an RTF template, but in order to use it, you must actually type the document into it yourself, by hand. If you copy and paste it into the template something, apparently, will get screwed up. I will repeat that, the American Physical Society requires you to actually, physically, press the keys on your keyboard while their template is open in order to submit an abstract (though I imagine something like xdotool might serve me well here). This is what happens with you use things you don't understand people. You get black magic crap like this.

Point is, I miss my previous colleagues and advisor, nay entire department, nay entire institution where they held the opinion that any individual in the sciences should be using Latex as their format for correspondence. Also, bravo to the APS for encouraging people to use Latex for submitting abstracts.