### July 6-11, 1998 - Swarthmore, Pennsylvania

1998 Summer Institute || Participant Projects || List of Participants || Sum98 Staff || Agenda

## Weights and binary digits

#### Rob Rumppe

To weigh any object in integrals from 1 gram to 255, if each weight costs \$1, what is the least you'll have to pay?

A professor requires that each member of her class own a set of weights that will enable the student to find the weight of any object whose weight is an integral amount between 1 and 255 grams. Regardless of its size, each weight costs \$1.00.

One of the students has only \$10 to his name. In distress, at the bookstore he meets a math student who points out that he probably won't need every weight: "If you have a one-gram weight and a two-gram weight, you can put them together to make a three-gram weight."

The two students sit down to figure out what other weights will and will not be needed. The question is: what is the least amount of money that can be spent to meet the professor's requirement?

Several people soon arrived at an answer of \$8 by directly listing combinations and then extrapolating to find a pattern.

Answer 1: 128g, 64g, 32g, 16g, 8g, 4g, 2g, 1g = \$8.00

Rob went on to demonstrate his Day 2 pronouncement that "the answer to a problem may not be as interesting as why that answer answers the problem" by stating the first few cases of the optimal solution:

to weigh 1g, the student uses one 1g weight
to weigh 2g, the student uses one 2g weight
to weigh 3g, the student uses one 2g weight and one 1g weight
to weigh 4g, the student uses one 4g weight
to weigh 5g, the student uses one 4g weight and one 1g weight
to weigh 6g, the student uses one 4g weight and one 2g weight
to weigh 7g, the student uses one 4g weight and one 2g weight and one 1g weight
to weigh 8g, the student uses one 8g weight
...

Listing the weights of 1g, 2g, 4g, 8g, ... suggested a pattern: consecutive powers of two, up to 128. Rob then constructed a table that revealed the solution's connection to binary digits:

```     the number of ...

128  64  32  16   8   4   2   1

... gram weights required to represent ...
... the integral mass
0   0   0   0   0   0   0   1                1
0   0   0   0   0   0   1   0                2
0   0   0   0   0   0   1   1                3
0   0   0   0   0   1   0   0                4
0   0   0   0   0   1   0   1                5
0   0   0   0   0   1   1   0                6
0   0   0   0   0   1   1   1                7
0   0   0   0   1   0   0   0                8
...
```

Collapsing the first eight columns in the table shows the binary representations for the numbers in the rightmost column:

```0000001 -- 1
0000010 -- 2
0000011 -- 3
0000100 -- 4
0000101 -- 5
0000110 -- 6
0000111 -- 7
0001000 -- 8
...
```

Rob's method for motivating and arriving at this binary representation of integers appealed to many participants.

Rob then suggested the possibility of another solution pointed out to him by Ron Knott based on consecutive powers of 3:

```        243   81   27   9   3   1
```
By placing one weight on one side of a pan balance and another on the other to subtract, the optimal solution appears to be \$6.

Answer 2: 243g, 81g, 27g, 9g, 3g, 1g = \$6.00

(Below, /\ represents the fulcrum of the balance.)

```       0 /\ 1     = 1
1 /\ 3     = 2
0 /\ 3     = 3
0 /\ 3 + 1 = 4
1 + 3 /\ 9     = 5
3 /\ 9     = 6
3 /\ 9 + 1 = 7
et cetera. . .

```