Solution to December’s Puzzle: Minimum Number
of Weights
Can you determine the minimum number of weights required to measure
any integer weight in the range 1 through 100 pounds using a scale?
Also, can you generalize your answer for a range 1 through n pounds?
The puzzle doesn’t restrict you to placing the item you’re weighing
on one side of the scale and the weights on the other. Therefore, you
can place weights on both sides. Weights that you place on the same
side of the scale as the item you’re weighing will have negative values,
whereas weights that you place on the other side will have positive
values. To simplify the solution’s explanation, first assume that there
was a restriction to place the item you’re weighing on one side of the
scale and the weights on the other.
Given a set of weights, to measure some item’s weight (call it w),
you need to use a subset of the weights you have—that is, each weight
from your set of weights will either be used or not used to weigh the
item. So any w in the range 1 through n can be represented with a
bitmap, where each bit represents a different weight from your set of
weights, and only the bits of the participating weights will be turned
on. A binary representation will give you the least number of weights
required to weigh any item in the range 1 through n. For example, to
represent any integer in the range 1 through 100, you need 7 bits (1,
2, 4, 8, 16, 32, and 64). Notice that you get a geometric sequence
(also known as a geometric progression) with a common ratio 2 (1×20,
1×21, 1×22, 1×23, etc.). To represent any integer in the range 1
through n, the geometric series (i.e., the sum of the numbers in the
geometric sequence) must be greater than or equal to n. The simplified
formula for the sum of the geometric sequence in our case is 2num_weights - 1,
and this sum must be greater than or equal to n. Hence, the minimum
number of weights required is ceiling(log2(n+1)).
Next, remove the restriction to place weights only on one side of
the scale. Now each weight from your set of weights can assume one
of three roles: first, placed on the same side of the scale as the item
you’re weighing (i.e., a negative value); second, placed on the other
side of the scale (i.e., a positive value); and third, not used (i.e., a 0
value). So, just as you used a string of binary digits in base 2 to represent
the set of utilized weights to solve the puzzle with the restriction,
you can use a string of digits in base 3 to represent the set of utilized
weights to solve the puzzle without the restriction. To represent any
integer in the range 1 through 100, you need five digits
that are powers of 3 (1, 3, 9, 27, and 81). Each can
be used as a positive value, negative value, or not
used. This time, the common ratio of our geometric
sequence is 3. The simplified sum of the geometric
sequence is (3num_weights - 1) ÷ 2. To represent any integer
in the range 1 through n, the minimum number
of weights required is ceiling(log3(2×n+1)).
January’s Puzzle: Counting Triangles
Can you figure out how many triangles Figure
A contains? Can you think of a methodical
approach or formula to calculate this number?
End of Article
