The Art and Craft of Problem Solving

138 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS

Example 4.3.6 Let n be any positive integer. Show that the set of weights

1,3, 32 , 33 , 34 , ...

grams can be used to weigh an n-gram weight (using both pans of a scale), and that

this can be done in exactly one way.

Solution: For example, if n = 10 , the n-gram weight is balanced by a I-gram

weight and a 9-gram weight. The corresponding arithmetic fact is

10 = 1 + 32.

If n = 73, the n-gram weight is joined by a 9-gram weight on one pan, which is bal­

anced by an 8 I-gram weight and a I-gram weight. This corresponds to the statement

73 + 32 =^34 + 1,

which is equivalent to

We will be done if we can show that for any positive integer n it is possible to write

n as a sum and/or difference of distinct powers of 3, and that this can be done in exactly

one way. It is sort of like base-3, but not allowing the digit 2, and instead admitting the

"digit" - 1. Indeed, playing around with this idea can lead to an algorithm for writing

n as a sum/and or difference of powers of 3, but it is hard to see why the representation

will be unique.

Here's a generatingfunctionological^8 approach: Consider the function

II (x) := (1 +x+x-I)(I +x^3 +x-^3 ).

The two factors of II each contain the exponents 0, 1, - 1, and 0,3, -3, respectively.

When II is multiplied out, we get

II (x) = 1 +x+x-I +x^3 +x^4 +x^2 +x-^3 +x-^2 +x-^4. (7)

Every integer exponent from -4 to 4, inclusive, is contained in this product, and each

term has a coefficient equal to 1. Each of these nine terms is the result of choosing

exactly one term from the first factor of II and one term from the second factor, and

then multiplying them (adding their exponents). In other words, the exponents in (7)

are precisely all possible ways of combining the two numbers 1 and 3 with additions

and/or subtractions and/or omissions. (By "omissions," we mean that we don't have

to include either 1 or 3 in our combination. For example, the combination "+3" omits

(^1) .)
Let's move on. Consider
Jz(x) := (1 +x+[
(^1) )(1 +x (^3) +x- (^3) )(I +x (^32) +x- 3
\
(^8) The tenn "generatingfunctionology" was coined by Herbert Wilf, in his book of the same name [ 4 7]. We
urge the reader at least to browse through this beautifully written textbook, which, among its many other channs,
has the most poetic opening sentence we've ever seen (in a math book). Incidentally, [ 43 ] and [ 3 8] also contain
excellent and very clear matenal on generating functions.