Solving a Puzzle: An Internal Monologue

The first step towards solving any problem, puzzles as well as more realistic and open-ended problems, is to understand it (although some might say the first step towards solving a problem is to recognize that there is one, but that usually refers to a different class of problems). In the case of a puzzle, this usually means reading it properly and trying to clearly state any assumptions made.

What do we want to do? We want to split 1 kg of flour into two mounds, one of 200g and one of 800g. Equivalently, we want to weigh out 200g or 800g of from 1 kg of flour and we want to do in the minimum number of weighings.

Normally it might be pertinent to ask question why we doing what we are doing as well. Why do we only have a balance weight? Why is it important to use it as little as possible? And why do we need to split 1 kg into 200g and 800g in the first place? Thinking outside the the box is always useful, but for now we will assume the box is well-defined and that the rationale behind the sides of this particular box are reasonable.

Let's explore the setting a bit. In the first weighing we can weigh 10, 40 or 50g of flour. With slightly more thinking we realize that we can also weight out 30g by putting 10g one one side and 40g on the other. This gives a first brute-force solution by weighing out 200g of flour by balancing the scale 4 times with the 40g and 10g weight one side.

Here we are really just exploring the space and we immediately discover two ways of using the weights: using them one one side or on both sides, in order to measure their difference. We also found an initial, trivial solution. This phase can sometimes be referred to as specialization. The puzzle are solving can be thought of as a special case of dividing some quantity into two (or arbitrarily many parts) given a set of weights in the minimum number of weighings possible. A bit of meta-reasoning also makes it clear that the trivial solution cannot be the best as this would be a lousy puzzle.

We can surely do better. Which tools do we have? Have we used everything we are given? Maybe we have made some unfounded assumptions? We have the scale, the weights and the flour. Aha, we can of course use the flour as a weight as well! We can for example measure out 500g by balancing the scales once. Or we can measure out 50g of flour and then use that 50g as a weight and measure out 100g by putting it together with the weights. 50g of flour together with the 50g of weights. Then we can measure out 50g again. We now have a solution where we only need to balance the scales three times, instead of four. Can we still do better?

By continuing to explore the solution a space we realized that we can use the flour. I had artificially restricted myself by making an unfounded assumption by not considering using the flour. By using the flour we immediately found a better solution, at least with respect to the number of weighings. However, it is also more complicated. The engineer in my head would now usually ask whether this trade-off is worth it.

Aha! The granularity with which can measure is the smallest weight or the smallest difference. In this case 10g. So we can drop 0 zero to make things slightly simpler. This is just a cosmetic change, but I find the smaller numbers easier to play with.

Any thing that makes the problem easier to handle is useful to do. In this case it is a trivial transformation (dividing the numbers by 10), but it somehow makes things more familiar. I often find myself moving between discrete versions to continuous variants of problems as well.

Hmm, we have to make sure that we keep the different mounds of flour separate. If we use flour as weights we can only use one mound at the time or create a new weight through an irreducible operation (mixing a 30g and a 40g of flour into a mound of 70g cannot be split again).

We just discovered a constraint that needs to be taken into account for any solution. However, both solutions we identified still holds. The question now is: can we do even better? If not, can we convince ourselves that this is impossible? If it isn't, could we make it possible by introducing more tools, e.g. measuring by eye which can be modeled by some distribution, where we allow for some error margin on the mounds (flour is rarely used for chemistry or other things were one needs to be precise, but I'm no baker). Maybe it is okay to have +/- 25g in the mounds 90% of the time? Balancing a scale is itself improbable

What if we were measuring discrete objects? Maybe the flour is made up of "balls of flour" whose weight we don't know, but then we could easily label and keep track of them.

We found a couple of algorithms now that solves the specific measuring problem we started with. However, we still don't know whether three weighings are the minimum number needed. Respice Finem, i.e. to start with the solution is a good way to continue here. What would an answer to this look like? There are several ways we can proceed:

• A better algorithm, meaning that we can do better bringing us again back to the need to show that two weighings is the minimum
• A proof to the contrary
• Come up with a general algorithm or method that is easier to work with formally
• Find an abstract model that captures this problem from where analogies can be drawn to other problems
• Brute force enumeration
• Modeling it as a CSP and plug it in somewhere, which is similar to above, but it is not obvious how to capture this into a model.

Brute force can often be useful in order to build some more intution about the space we are operating in, but it is not a satisfying solution. It was said that John Conway spend a significant effort on producing examples¹.

We now have a couple of possible solutions and some idea of the space we are operating in. We have weights which we can put on both sides of the scale, we can also create weights by measuring out flour. Can we model this in some way? We want to find the way to measure out 200g and 800g in as few weighings as possible. More generally, we want to a procedure to split an amount of flour into two predefined parts or possibly into an arbitrary number of parts. Can an arbitrary split be reduced to splitting in two? My gut says no, but maybe? In any case, let's focus on the trying to model this problem in a more general way.

Actually, doing the brute force enumeration is not that hard since we only need to check two steps. With the ways of measuring we have identified the first weighing can give us two mounds of 500g or mounds of 10, 30, 40 or 50g and the corresponding leftovers. Enumerating is just a one-page decision tree which quickly shows that we cannot measure neither 200g or 800g in two weighings. In other words, in the current setting three weighings is the best we can do. Puzzle solved!

Two solutions are better than one. In this case, the easy one can give us confidence and certainty that efforts towards finding a more formal solution won't be wasted. We found two ways to measure out the desired quantities of flour, but it was just through a bit of luck and playing around, which doesn't scale. In the real world it is sometimes fine to stop here, but if we want a fast and scalable solution this does not suffice. We want to understand better what is going on and understand it. What if the quantities change or if we want to split into an arbitrary number quantities? We would then have some tricks up our sleeves, but we would not have a general method that we could immediately apply.

How would the method change if we had a different set of weights or wanted another partitioning of the flour? Possibly into different parts and more than two parts? Can we create a method that works for any amount of weights and an arbitrary partioning? Is there any useless work that is being done in the current solution?

Now we are trying to understand what is going on so we play with different variations of the problem to try and see where to go next.

What are the scale and the weights? They are, in some sense, just embodiments of something more abstract: a way to check a property, a comparison operator and the weights are just operands or objects that has a mass property. Can we perhaps model this as an arithmetic problem?

Aha! Maybe can think of all the things we can measure in one step as numbers and the balance weight as a way to create new numbers? In the same way the decimal number 123 is just shorthand for \(1*10^2 + 2*10^1 + 3*10^0\) or binary with base 2 we can make a system without a base in the traditional sense, but where the bases are the weights we have. In the first round we have 40g and 10g. We can then create numbers \(a*40 + b*10\). We also realize that \(a, b \notin \{0, ..., 9\}\), but that \(a, b \in {-1, 0, 1}\) where the minus models the left side of the scale and the 1 the right hand of the scale, without loss of generality.

Suddenly we are dealing with numbers instead of weights, mounds of flour and a balance weight.

Hmm.. I still don't see a good way to move on from here. I'm a bit stuck. Maybe it makes sense to change things up about. What are the mininum number of weights needed to be able to measure out a given quantity? If I want to be able to measure out any amount between 1 and \(n\) grams with a balance weight?

Now we are mixing things up in order to understand the new, more abstract setting better. This new puzzle is equivalent to figuring out how many bases we need in order to represent all the numbers from 1 to \(n\).

The first thought that pops into mind is that we can just use the bases in the binary system. Then we know that with bases \(1, 2, 4, ... 2^{n-1}, 2^n\) we can represent all numbers between 0 and \(2^n+1 - 1\). But this does not account for weighing on both sides; only one of them. We see that to weight that \(3 = 2^2 - 2^0\) and \(3 = 2^1 + 2^0\). It is redundant in other words so we can probably do better. Actually, we should think of ternary numbers since \(d_i \in \{-1, 0, 1\}\); not \(\{0, 1\}\)! Is the radix related to the base in terms of expressiveness for a number system?

With weights \(1, 3, 9 ... 3^{n-1}, 3^{n}\) we can measure out all numbers between 0 and \(3^{n+1}\) and \(3^n\) is obviously larger than \(2^n\). This means that the same number of weights, \(n\), can be used to measure out a much wider range of numbers.

A lot happened here. The train of thought kept coming after moving on to the puzzle we derived. Another interesting question popped out with respect to the bases of a number system and its radix.

Aha! We have to keep in mind we can only measure absolute numbers. In other words, flipping around two sets of weights will measure out the same quantity of flour.

There is a lot to unpack here. We are now operating with pure numbers as opposed to mounds of flour, weights and scales. We delved into a different problem in order to understand the new setting better.

However, we still haven't found another solution or a general method, but the puzzle has fulfilled its job: I had plenty of small eureka moments, I made some new connections and found interesting-looking rabbit holes, but they will have to be explored another day. Now the sun is shining, my coffee mug is empty and this post is already too long, and to paraphrase another wise man: when there is no will, there is no way and my will to think is spent for now.

• How To Solve It, Polya
• Thinking Mathematically,
• Can You Solve My Problems?, Alex Bellos