Suppose you have a balance scale and four weights of 1 unit, 2 units, 4 units and 8 units. How many different weights can you match? If you know binary arithmetic, it’s easy to see that you can match any weight up to fifteen units inclusive. With the object in the left-hand pan of the scale and the weights in the right-hand pan, these are the matches:

01 = 1

02 = 2

03 = 2+1

04 = 4

05 = 4+1

06 = 4+2

07 = 4+2+1

08 = 8

09 = 8+1

10 = 8+2

11 = 8+2+1

12 = 8+4

13 = 8+4+1

14 = 8+4+2

15 = 8+4+2+1

The weights that sum to

*n*match the 1s in the digits of

*n*in binary.

01 = 0001 in binary

02 = 0010 = 2

03 = 0011 = 2+1

04 = 0100 = 4

05 = 0101 = 4+1

06 = 0110 = 4+2

07 = 0111 = 4+2+1

08 = 1000 = 8

09 = 1001 = 8+1

10 = 1010 = 8+2

11 = 1011 = 8+2+1

12 = 1100 = 8+4

13 = 1101 = 8+4+1

14 = 1110 = 8+4+2

15 = 1111 = 8+4+2+1

01 = 0001 in binary

02 = 0010 = 2

03 = 0011 = 2+1

04 = 0100 = 4

05 = 0101 = 4+1

06 = 0110 = 4+2

07 = 0111 = 4+2+1

08 = 1000 = 8

09 = 1001 = 8+1

10 = 1010 = 8+2

11 = 1011 = 8+2+1

12 = 1100 = 8+4

13 = 1101 = 8+4+1

14 = 1110 = 8+4+2

15 = 1111 = 8+4+2+1

But there’s another set of four weights that will match anything from 1 unit to 40 units. Instead of using powers of 2, you use powers of 3: 1, 3, 9, 27. But how would you match an object weighing 2 units using these weights? Simple. You put the object in the left-hand scale, the 3-weight in the right-hand scale, and then add the 1-weight to the

__left-hand__scale. In other words, 2 = 3-1. Similarly, 5 = 9-3-1, 6 = 9-3 and 7 = 9-3+1. When the power of 3 is positive, it’s in the right-hand pan; when it’s negative, it’s in the left-hand pan.

This system is actually based on base 3 or ternary, which uses three digits, 0, 1 and 2. However, the relationship between ternary numbers and the sums of positive and negative powers of 3 is more complicated than the relationship between binary numbers and sums of purely positive powers of 2. See if you can work out how to derive the sums in the middle from the ternary numbers on the right:

01 = 1 = 1 in ternary

02 = 3-1 = 2

03 = 3 = 10

04 = 3+1 = 11

05 = 9-3-1 = 12

06 = 9-3 = 20

07 = 9-3+1 = 21

08 = 9-1 = 22

09 = 9 = 100

10 = 9+1 = 101

11 = 9+3-1 = 102

12 = 9+3 = 110

13 = 9+3+1 = 111

14 = 27-9-3-1 = 112

15 = 27-9-3 = 120

16 = 27-9-3+1 = 121

17 = 27-9-1 = 122

18 = 27-9 = 200

19 = 27-9+1 = 201

20 = 27-9+3-1 = 202

21 = 27-9+3 = 210

22 = 27-9+3+1 = 211

23 = 27-3-1 = 212

24 = 27-3 = 220

25 = 27-3+1 = 221

26 = 27-1 = 222

27 = 27 = 1000

28 = 27+1 = 1001

29 = 27+3-1 = 1002

30 = 27+3 = 1010

31 = 27+3+1 = 1011

32 = 27+9-3-1 = 1012

33 = 27+9-3 = 1020

34 = 27+9-3+1 = 1021

35 = 27+9-1 = 1022

36 = 27+9 = 1100

37 = 27+9+1 = 1101

38 = 27+9+3-1 = 1102

39 = 27+9+3 = 1110

40 = 27+9+3+1 = 1111

To begin understanding the sums, consider those ternary numbers containing only 1s and 0s, like *n* = 1011_{[3]}, which equals 31 in decimal. The sum of powers is straightforward, because all of them are positive and they’re easy to work out from the digits of *n* in ternary: 1011 = 1*3^3 + 0*3^2 + 1*3^1 + 1*3^0 = 27+3+1. Now consider *n* = 222_{[3]} = 26 in decimal. Just as a decimal number consisting entirely of 9s is always 1 less than a power of 10, so a ternary number consisting entirely of 2s is always 1 less than a power of three:

999 = 1000 - 1 = 10^3 - 1 (decimal)

222 = 1000_{[3]} - 1 (ternary) = 26 = 27-1 = 3^3 - 1 (decimal)

If a ternary number contains only 2s and is *d* digits long, it will be equal to 3^*d* – 1. But what about numbers containing a mixture of 2s, 1s and 0s? Well, all ternary numbers containing at least one 2 will have a negative power of 3 in the sum. You can work out the sum by using the following algorithm. Suppose the number is five digits long and the rightmost digit is digit #1 and the leftmost is digit #5:

01. *i* = 1, *sum* = 0, *extra* = 0, *posi* = true.

02. if *posi* = false, goto step 07.

03. if digit #*i* = 0, *sum* = *sum* + 0.

04. if digit #*i* = 1, *sum* = *sum* + 3^(i-1).

05. if digit #*i* = 2, *sum* = *sum* - 3^(i-1), *extra* = 3^5, *posi* = false.

06. goto step 10.

07. if digit #*i* = 0, *sum* = *sum* + 3^(i-1), *extra* = 0, *posi* = true.

08. if digit #*i* = 1, *sum* = *sum* - 3^(i-1).

09. if digit #*i* = 2, *sum* = *sum* + 0.

10. *i* = *i*+1. if *i* <= 5, goto step 2.

11. print *sum* + *extra*.

As the number of weights grows, the advantages of base 3 get bigger:

With 02 weights, base 3 reaches 04 and base 2 reaches 3: 04-3 = 1.

With 03 weights, base 3 reaches 13 and base 2 reaches 7: 13-7 = 6.

With 04 weights, 000040 - 0015 = 000025

With 05 weights, 000121 - 0031 = 000090

With 06 weights, 000364 - 0063 = 000301

With 07 weights, 001093 - 0127 = 000966

With 08 weights, 003280 - 0255 = 003025

With 09 weights, 009841 - 0511 = 009330

With 10 weights, 029524 - 1023 = 028501

With 11 weights, 088573 - 2047 = 086526

With 12 weights, 265720 - 4095 = 261625...

But what about base 4, or quaternary? With four weights of 1, 4, 16 and 64, representing powers of 4 from 4^0 to 4^3, you should be able to weigh objects from 1 to 85 units using sums of positive and negative powers. In fact, some weights can’t be matched. As you can see below, if *n* in base 4 contains a 2, it usually can’t be represented as a sum of positive and negative powers of 4 (one exception is 23 = 2*4 + 3 = 11 in base 10). Certain other numbers are also impossible to represent as that kind of sum:

1 = 1 ← 1

2 has no sum = 2

3 = 4-1 ← 3

4 = 4 ← 10 in base 4

5 = 4+1 ← 11 in base 4

6 has no sum = 12 in base 4

7 has no sum = 13

8 has no sum = 20

9 has no sum = 21

10 has no sum = 22

11 = 16-4-1 ← 23

12 = 16-4 ← 30

13 = 16-4+1 ← 31

14 has no sum = 32

15 = 16-1 ← 33

16 = 16 ← 100

17 = 16+1 ← 101

18 has no sum = 102

19 = 16+4-1 ← 103

20 = 16+4 ← 110

21 = 16+4+1 ← 111

22 has no sum = 112

23 has no sum = 113

24 has no sum = 120

25 has no sum = 121

26 has no sum = 122

27 has no sum = 123

[...]

With a more complicated balance scale, it’s possible to use weights representing powers of base 4 and base 5 (use two pans on each arm of the scale instead of one, placing the extra pan at the midpoint of the arm). But with a standard balance scale, base 3 is the champion. However, there is a way to do slightly better than standard base 3. You do it by botching the weights. Suppose you have four weights of 1, 4, 10 and 28 (representing 1, 3+1, 9+1 and 27+1). There are some weights *n* you can’t match, but because you can match *n*-1 and *n*+1, you know what these unmatchable weights are. Accordingly, while weights of 1, 3, 9 and 27 can measure objects up to 40 units, weights of 1, 4, 10 and 28 can measure objects up to 43 units:

1 = 1 ← 1

2 has no sum = 2

3 = 4-1 ← 10 in base 3

4 = 4 ← 11 in base 3

5 = 4+1 ← 12 in base 3

6 = 10-4 ← 20

7 = 10-4+1 ← 21

8 has no sum = 22

9 = 10-1 ← 100

10 = 10 ← 101

11 = 10+1 ← 102

12 has no sum = 110

13 = 10+4-1 ← 111

14 = 10+4 ← 112

15 = 10+4+1 ← 120

16 has no sum = 121

17 = 28-10-1 ← 122

18 = 28-10 ← 200

19 = 28-10+1 ← 201

20 has no sum = 202

21 = 28-10+4-1 ← 210

22 = 28-10+4 ← 211

23 = 28-4-1 ← 212

24 = 28-4 ← 220

25 = 28-4+1 ← 221

26 has no sum = 222

27 = 28-1 ← 1000

28 = 28 ← 1001

29 = 28+1 ← 1002

30 has no sum = 1010

31 = 28+4-1 ← 1011

32 = 28+4 ← 1012

33 = 28+4+1 ← 1020

34 = 28+10-4 ← 1021

35 = 28+10-4+1 ← 1022

36 has no sum = 1100

37 = 28+10-1 ← 1101

38 = 28+10 ← 1102

39 = 28+10+1 ← 1110

40 = has no sum = 1111*

41 = 28+10+4-1 ← 1112

42 = 28+10+4 ← 1120

43 = 28+10+4+1 ← 1121

`*N.B. 40 = 82-28-10-4, i.e. has a sum when another botched weight, 82 = 3^4+1, is used.
`