Why are all numbers from 1 to 2N covered by weights with powers of 3?

Question

This is from What's the fewest weights you need to balance any weight from 1 to 40 pounds?

Suppose you want to create a set of weights so that any object with an integer weight from 1 to N pounds can be balanced on a two-sided scale by placing a certain combination of these weights onto that scale.

What is the fewest number of weights you need?

I can't really understand the accepted answer there. Why can we be certain that all numbers from 1 to 2N shall be covered by powers of 3 so that we can go to the next one as 2N+1?

Answer 1

It helps to think about the scale not in terms of balancing two objects, but in terms of creating a weight difference between the two sides. (If you want to balance out an object, you simply put weights to make the appropriate weight difference.) For instance, you could put a 9 and a 1 on the right pan, and a 3 on the left. This makes a weight difference of $(9+1) - 3$, which is 7, and so you could weight a 7-pound object.

Now, let's look at what weight differences we can make. I'll always be calculating the difference as right minus left - so if the left side is heavier, the difference could be negative!

---

Step 1

Say we just have a 1-pound weight. What differences can we make? Well, we have only three options: we can put it on the right, leave it off, or put it on the left. So our possible differences are 1, 0, and -1.

(I've attached a digital readout to the scales - it measures the current weight difference and displays it at the base.)

Step 2

Now, what happens if we add in another weight - say, 5 pounds?No matter what we currently have on the scale, if we add the new weight on the right, the difference increases by 5. Similarly, if we add it on the left, the difference decreases by 5.

I'm going to mark all the differences we can get on a number line:

Step 3

Let's continue with this set - what if we added, say, a 20lb weight? After you try all the new combinations, you end up with this:

Huh, that's interesting... lemme just highlight some things...

Aha! And now it's clear what adding a new $k$-pound weight does - it copies your current pattern of accessible numbers, and pastes it centered at $k$ and $-k$.

You can even say this is what happened at the beginning, when we added our first weight! With no weights, your only accessible difference is 0; adding the 1-pound weight copied the ★ on the 0, and pasted it at -1 and 1.

---

And now, armed with this knowledge, we can see how the "powers of three" strategy works:

You start with a single ★ at 0. Then, you choose the next weight to be whatever will paste your copy at the appropriate offsets, so it just barely touches without overlapping. This means you're creating a "range" of accessible values that grows and grows, without ever having any missed numbers.

And what is this correct offset? Well, you want to shift your copy's left endpoint to match up with your current range's right endpoint -- so each time, you want to shift by exactly the length of your current range! And since you're tripling the size of your range each time, it's always a power of three.

---

Sidenote

This system is called "balanced ternary" - adding a new weight is just like adding a new digit in your representation of a number. In regular ternary, the place values [from right to left] are "1, 3, 9, 27...". Balanced ternary is similar, except the allowed digits are 1, 0, and -1 (often written "T").

It turns out the balanced ternary representation of a number tells us precisely how to place the weights in the pans! 1 means "right pan", 0 means "leave out", and T means "left pan" - for instance, the number 19 is written in balanced ternary as "$\underset{27}{1}\;\underset{9}{T}\;\underset{3}{0}\;\underset{1}1$". The digits tell us "place the 27-pound and 1-pound weights on the right pan, and the 9-pound weight on the left pan".

Answer 2

Why can we be certain that all numbers from 1 to 2N shall be covered by powers of 3 so that we can go to the next one as 2N+1?

This is not the claim. The argument is using induction, and the inductive hypothesis is not that numbers from $1$ to $2N$ should be covered, but that only numbers from $1$ to $N$ should be covered (or $0$ to $N$ or $-N$ to $N$ depending upon how you view the problem).

Then we choose to add a weight that weighs $2N+1$. To balance a weight $W$ from $N+1$ to $2N$, we can write $W$ as $W = (2N+1) - X$ where $X$ is a number from $1$ to $N$. Then we balance the $2N + 1$ weight against the object, and add the weights we would use to balance $X$ but on the opposite sides they would go on to balance $X$ which has the effect of essentially subtracting the $X$.

We can also similarly balance weights up to $3N+1$ just be adding instead of subtracting.

Example: To weigh an object $W$ of weight $1$, be balance $W$ versus $1$. Then we add weight $3$. To get $2$, we write $2 = 3 - 1$. Thus we put $3$ against the object, and $1$ on the opposite it went on previously, so on the same side as the object: $W + 1$ versus $3$. Getting $3$ is just $W$ versus $3$ and $4$ is just adding $3$ to the solution for $1$, so $W$ versus $3 + 1$.

Then we add weight $9$. To get a number between $4$ and $9$, say $7$, we write $7 = 9 - 2$. We put $9$ against the object, and recall our solution for $2$ which put $1$ with the object and $3$ against the object; we will reverse this. This gives $W + 3$ versus $9 + 1$.

By the way, this system is called Balanced Ternary.