15
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ This is a good question but I wonder whether it would be a better fit on the math se because it isn't really a puzzle. $\endgroup$
    – quarague
    Jul 7, 2022 at 8:45
  • 1
    $\begingroup$ @quarague (A bit of a belated response, but...) Questions about puzzles are perfectly acceptable here! Questions don't have to be puzzles (though a lot of them are). $\endgroup$
    – Deusovi
    Jul 9, 2022 at 20:11

2 Answers 2

47
$\begingroup$

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.

scales in three configurations

(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.

scales in nine configurations with weights of 1lb and 5lb

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

number line with 9 achievable numbers marked

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:

number line with 27 achievable numbers marked

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

same as previous number line, annotated

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:

image of number line, marked for 1lb, 1+3lb, and 1+3+9lb

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".

$\endgroup$
2
  • $\begingroup$ What a great answer, the visuals really help with comprehension and the way you structured it was expertly done to teach bit by bit and come to a cool conclusion. $\endgroup$ Jul 6, 2022 at 20:15
  • $\begingroup$ That's a genius answer. I had already understood the original answer but you made me discover the concept of balanced ternary in a very efficient and visual way $\endgroup$
    – GabrielH
    Jul 7, 2022 at 11:28
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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