The Logical Puzzle - 18 Dec 2007

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 (3^num_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?