PROBLEM
Suppose a shop keeper needs to weigh all the weights from 1 kg to 121 kg (no fractions) i.e. 1 kg, 2 kg, 3 kg . . . up to 121 kg using balance. How can the shopkeeper choose minimum number of weights so that she/he will be able to weigh all the weights up to 121 kg? What are the values of individual weights?Hint: It is allowed to put weights in both sides of measuring balance.
SOLUTION
Let { x(i) for i = 1 to n} denote the values of weights chosen.
The objective is to find values of x(i) so that weighing is possible for any number up to 121 kg. Since 121 kg is the maximum weight to be measured, we can choose all the weights such that their summation is greater than or equal to 121.
Hence { ∑ x(i) for i = 1 to n } >= 121
Let S(n) = { ∑ x(i) for i = 1 to n }
By definition
S(n-1) = { ∑ x(i) for i = 1 to (n-1) }
Therefore S(n) = S(n-1) + x(n)
Let us assume we know the values of x(i) for i = 1 to (n-1). And let us assume that these values are optimum values for measuring all the weights up to S(n-1).
Given this, how can we choose the value of x(n) so that S(n) will be maximum and we will be able to measure all the additional weights from S(n-1)+1 to S(n)?
We should choose x(n) so that it satisfies following expression :
x(n) - S(n-1) = 1 + S(n-1)
Hence x(n) = 1 + 2 S(n-1)
By definition, S(n-1) = S(n-2) + x(n-1)
Hence x(n) = 1 + 2 [ S(n-2) + x(n-1) ]
= 1 + 2 S(n-2) + 2 x(n-1)
By definition we know 1 + 2 S(n-2) = x(n-1)
Hence x(n) = x(n-1) + 2 x(n-1) = 3 x(n-1)
Therefore x(n) = 3 x(n-1)
We know the base condition: x(1) = 1 and S(1) = 1
x(2) = 3 * x(1) = 3 * 1 = 3
S(2) = S(1) + x(2) = 1 + 3 = 4
x(3) = 3 * x(2) = 3 * 3 = 9
S(3) = S(2) + x(3) = 4 + 9 = 13
x(4) = 3 * x(3) = 3 * 9 = 27
S(4) = S(3) + x(4) = 13 + 27 = 40
x(5) = 3 * x(4) = 3 * 27 = 81
S(5) = S(4) + x(5) = 40 + 81 = 121
Since S(5) >= 121, we will stop here and the solution is 5 number of weights: [ 1 3 9 27 81]
Mathematically, { ∑ 3^i for i = 0 to n-1 } >= w (where w is the max weight to be measured, 121 in this example)
The mathematical formula for { ∑ 3^i for i = 0 to n-1 } = (3^n - 1)/2
Hence (3^n - 1)/2 >= w
(3^n - 1) >= 2w
3^n >= 1 + 2w
Hence n >= log3(1+2w)
The minimum integer value of n that satisfies above condition will be the answer for n i.e. optimum number of weights required to weigh up to w kg.
Alternatively n = log3(1+2w)
If it comes in fraction then it needs to be rounded up.
for w = 121, n = log3(1+2*121) = log3(1+242) = log3(243) = 5
And values of weights are:
x(1) = 3^0 = 1
x(2) = 3^1 = 3
x(3) = 3^2 = 9
x(4) = 3^3 = 27
x(5) = 3^4 = 81
