Using a balance to determine any weight with a set of weights weighing powers of 3

Question

There is a scale with an object on the left-hand side, whose mass is given in some number of units. Predictably, the task is to balance the two sides. But there is a catch: You only have this peculiar weight set, having masses 1, 3, 9, 27, ... units. That is, one for each power of 3.

I want to output a list of strings representing where the weights should be placed, in order for the two sides to be balanced, assuming that weight on the left has mass x units.

How can you calculate this using balanced ternary number system?

Answer 1

I think it's useful to represent the input number in base $3$. Our weight system can easily write numbers whose ternary representation includes only $0$'s or $1$'s, but it can't handle $2$'s very well. Thankfully, when you add the weight that corresponds to a digit occupied by a $2$, it becomes a $0$ (and carries $1$ over to the next ternary digit).

This observation should make it simple to figure out what to do in each case. For instance, suppose our input number is (in ternary) $220002022200221111222$. We will add some weights to it, that is, a ternary number made up only of $0$'s and $1$'s, so that the result is also one such number. You will see that the process also guarantees the summand and the sum will never share a $1$ in the same digit, so we are good!

Start 'scanning' the input from the right until you find a $2$ (and remember this digit, say $k$). Now, continue scanning until you find a $0$. Notice this always happens in finite time because the input is finite (so it has many $0$'s 'to the left').

You have thus found a sequence of $1$'s and $2$'s, followed by a $0$. When you add the weight that correponds to digit $k$, that digit will become a $0$ and will carry over a $1$ to the next digit. This creates a domino effect, until the $1$ carries over to a digit which was occupied by a $1$ (rather than a $2$): that digit will become a $2$. So, if instead of $1$'s our sequence had only $2$'s, the domino effect would go on until the final $0$, which would become a $1$ itself. Well, it's easy to make a $1$ into a $2$: simply add $1$ to it!

Our algorithm then modifies our scanned sequence as follows: add the ternary number which has $1$'s wherever our scanned sequence has $1$'s and also a $1$ at the starting digit (and $0$'s everywhere else).

Then it's a matter of continue scanning for such sequences in our input number until we are done. Notice once again that since our input is finite, it decomposes into finite such 'scan'-sequences. For our example, we have four such sequences, and we get:

$\begin{array}{rr} &220002022200221111222\\ + &010001000100001111001\\ =&1000010100001000000000 \end{array}$

Notice how the carry-over process guarantees the summand (the weights we add to the input mass) and the result (the weights we add on the other side to even things out) do not share $1$'s in the same ternary digits, so it's all good!

Answer 2

I revised my answer because I found a much simpler approach (this requires $\mathcal{O}(\log n)$ weighings and $\mathcal{O}([\log n]^2)$ moved weights, which may not be the most efficient, though):

1. Let $n$ be the unknown weight. Pick a $k$ such that $3^k - \sum_{i=0}^{k-1}3^i \leq n$, i.e. the largest weight such that when placed on the non-object side and all weights below on the object side does not weigh over.
2. Remove the largest weight on the object side and see if the scale weighs over. If it does, leave it. Otherwise, try to put that weight on the non-object side. If it weighs over now, remove the weight completely.
3. Repeat for the second largest weight on the object side, and so forth, this until equilibrium.

The following Python code simulates the procedure:

n = 71
L = []
k = 0
while n > sum([3**i for i in range(0,k)]): 
    k += 1
    L.append(-1)
L.pop()
L.append(1)
k = len(L)-2
while k > -1:
    if sum([3**i*L[i] for i in range(0,len(L))])+3**k <= n:
        L[k] += 1
    else:
        k -= 1
print L, sum([3**i*L[i] for i in range(0,len(L))])

Answer 3

To solve this, I began by listing out the first few natural numbers, and determining how I would balance the scale for each one.

Weight     Left        Right side
to         side        (x is the weight
measure                we are measuring)
----------------------------------------
1:         (1)         x
2:         (3)         x(1)
3:         (3)         x
4:         (3)(1)      x
5:         (9)         x(3)(1)
6:         (9)         x(3)
7:         (9)(1)      x(3)
8:         (9)         x(1)
9:         (9)         x
10:        (9)(1)      x
11:        (9)(3)      x(1)
12:        (9)(3)      x
13:        (9)(3)(1)   x
14:        (27)        x(9)(3)(1)
15:        (27)        x(9)(3)
16:        (27)(1)     x(9)(3)
17:        (27)        x(9)(1)
18:        (27)        x(9)
19:        (27)(1)     x(9)
20:        (27)(3)     x(9)(1)
21:        (27)(3)     x(9)
22:        (27)(3)(1)  x(9)
23:        (27)        x(3)(1)
24:        (27)        x(3)
25:        (27)(1)     x(3)
26:        (27)        x(1)
27:        (27)        x
28:        (27)(1)     x
29:        (27)(3)     x(1)
30:        (27)(3)     x
31:        (27)(3)(1)  x
32:        (27)(9)     x(3)(1)

I quickly noticed a pattern developing in how the weights were placed for each number.

For each weight $w$,

Place a weight on the left side if there exists an $n$ such that $n \; \text{mod} \; 3 = 1$ and $|wn - x| \le \frac{w-1}2$
Place a weight on the right side if there exists an $n$ such that $n \; \text{mod} \; 3 = 2$ and $|wn - x| \le \frac{w-1}2$

My math skills are not good enough to solve for $n$ in the above inequalities (if it's even possible). If that can be done, you can use a simple mathematical method to determine the arrangement of weights:

For each weight $w$ up to the first weight greater than $x$, solve for $n$.
If $n = 1 \mod 3$, put the weight on the left.
If $n = 2 \mod 3$, put the weight on the right.
If $n = 0 \mod 3$, don't use the weight.

Answer 4

@Fimpellizieri has the best answer here. I am putting this in as an answer since it is too big for a comment. Give your votes to him. I am just showing a simpler explanation.

As he said, take the mass $x$ that we want to weigh and represent it in ternary. For example, say the mass weighs $13,579$. In base 3, this is $200121221$.

So, we are looking for two numbers, $A$ and $B$ such that $A=x+B$. These two numbers must have base 3 representations that only include $1$s or $0$s since we can only include one weight of each kind. Also, they may not have a $1$ in the same position, but this is trivial to ensure because if they both do, then simply remove it and the equality will still hold.

Now, back to our example. Take the number $x$ in ternary and we need to solve for $A$ and $B$ as follows:

Start with $B=0$ in the following equation.

x:   200121221
B: +         0
     ---------
A:   200121221

Starting from the right, whenever we encounter a $2$ in A, put a $1$ in that position in $B$. The first $2$ in $A$ is in the second position, so put a $1$ there in $B$.

x:   200121221
B: +        10
     ---------
A:   200122001

By changing $B$, $A$ has changed as well. So simply repeat the process until $A$ has no more $2$s.

x:   200121221    200121221    200121221    200121221
B: +        10 ->      1010 ->    101010 -> 100101010
     ---------    ---------    ---------    ---------
A:   200122001    200200001    201000001   1001000001

So, we now have $B=100101010 (6834) $ and $A=1001000001 (20413)$. And you will notice that $6834+13579=20413$, so our equality holds. Also, both $A$ and $B$ contain entirely $1$s and $0$s and never a $1$ in the same place.

So, we can set up our scales as follows:

• Left side: mass $x$ plus weights for $B$
• Right side: weights for $A$

In this example, this ends up with $B=3+3^3+3^5+3^8=3+27+243+6561$ and $A=3^0+3^6+3^9=1+729+19683$.

Answer 5

The members of the set of integers $A_n$ that total the natural number $n,$ where all members of the set are a power of three can be defined as

\begin{align} A_n=\small{\left\{3^k \left(\left\lfloor 3^{-k} \left(2 n+3^{\left\lceil \log _3(2 n+1)\right\rceil }-1\right)\right/2\rfloor -3 \left\lfloor 3^{-k-1} \left(2 n+3^{\left\lceil \log _3(2 n+1)\right\rceil }-1\right)/2\right\rfloor -1\right)\\ ~\Big{|}~ k\in \mathbb{Z} \land 0 \leq k \leq \left\lfloor \log _3\left(\left(3^{\left\lceil \log _3(2 n+1)\right\rceil }-1\right)/2+n\right)\right\rfloor\right\}}\\ \end{align}

Mathematica code:

a[n_] := DeleteCases[#, 0] &@ Table[3^k*(-1 - 3*Floor[(3^(-1 - k)*
(-1 + 3^Ceiling[Log[3, 1 + 2*n]] + 2*n))/2] + 
Floor[(-1 + 3^Ceiling[Log[3, 1 + 2*n]] + 2*n)/(2*3^k)]), 
{k, 0, Floor[Log[3, (-1 + 3^Ceiling[Log[3, 1 + 2*n]])/2 + n]]}]

Then a[#] &/@ Range @ 20 gives

{{1}, {-1, 3}, {3}, {1, 3}, {-1, -3, 9}, {-3, 9}, {1, -3, 9}, 
{-1, 9}, {9}, {1, 9}, {-1, 3, 9}, {3, 9}, {1, 3, 9}, {-1, -3, -9, 27}, 
{-3, -9, 27}, {1, -3, -9, 27}, {-1, -9, 27}, {-9, 27}, {1, -9, 27}, 
{-1, 3, -9, 27}}

Clearly the negative integers in $A_n$ should go on the same side as the weight, so

f[n_] := {{Total@#}, Select[#, # > 0 &], Join[{"W"}, 
-Select[#, # < 0 &]]} &@a@# &@n

Grid[f[#] & /@ Range@20, Alignment -> Left]

gives

1      {1}          {W} 
2      {3}          {W, 1} 
3      {3}          {W} 
4      {1, 3}       {W} 
5      {9}          {W, 1, 3} 
6      {9}          {W, 3}
7      {1, 9}       {W, 3} 
8      {9}          {W, 1}
9      {9}          {W} 
10     {1, 9}       {W} 
11     {3, 9}       {W, 1} 
12     {3, 9}       {W} 
13     {1, 3, 9}    {W} 
14     {27}         {W, 1, 3, 9} 
15     {27}         {W, 3, 9} 
16     {1, 27}      {W, 3, 9} 
17     {27}         {W, 1, 9} 
18     {27}         {W, 9} 
19     {1, 27}      {W, 9} 
20     {3, 27}      {W, 1, 9}

and the first thousand values of $A_n$ are calculated in $\approx 0.5$ seconds on my (slow) machine.