The Powers of 3

Let0ˆ9s put our thinking caps on.

I was recently flipping through a book of mind-bending word problems, and happened upon the following:

0ˆ6A postal worker bought a new pan balance to weigh mail. He needs to be able to weigh packages in 1 pound increments from 1 to 35 pounds. He wants to buy the least number of weights. Which weights should he buy?0ˆ7

At first, I thought of the powers of 2. He should buy 1, 2, 4, 8, 16 and 32 pound weights. This was the answer in the back of the book as well.

It is true that every natural number (especially those less that 35) can be constructed from selectively adding the powers of two. Imagine the base 2 (a.k.a. binary. The conversion is simple.) representation of a natural number. In base 2, every digit is either a one or a zero. If a given place value in the binary representation is a one, use that weight; if it is a zero, don0ˆ9t use that weight.

I wondered to myself, 0ˆ6Why must we use base 2? What numbers would we miss if we used a higher base, say, base 3?0ˆ7 The first few powers of 3, for easy reference, are 1, 3, 9, 27 and 81. How could the postman measure a 2 pound package using those weights? Then it occurred to me that the postman could put the package and the 1 pound weight on one pan, and the 3 pound weight on the other. In base 2, we only added or discarded weights. But what if we added, discarded and subtracted weights? Then we could powers of 3 to buy fewer weights for heavier packages. For example, to weigh a 46 pound package, the postman would add the 1 and 81 weights, discard the 3, and subtract the 9 and 27.

I came up with this more efficient solution because I0ˆ9m a genius. Because I0ˆ9m so smart, I won0ˆ9t stoop to prove that every natural number can be constructed by adding, discarding or subtracting the powers of three. I will leave the proof as an exercise for the reader.

← Previously: Unposted | All posts | Next: More geekiness, anyone? →