The following is a programming task from my childhood:
Assume, we have a weight of integer value (say, X) and an infinite set of weights 1, 3, 9, 27, … Assuming that we have ideal pharmaceutical scales. The task is to balance weight X using set of weights, if we can put any amount of weights on any scale.
The solution is to factor X in 3-nary presentation:
X = x_0 * 1 + x_1 * 3 + x_2 * 9 + … + x_n * 3^n
where all x_i are in {0, 1, 2} (i.e. in mod3 ring in mathematical terminology).
Let’s use [y] notation for integer part of y.
Let’s assume that we put X on scale A and the second scale has name B. Let’s denote Y sum of all weights on A and Z as sum of all weights on B.
We denote Y = y_0 * 3^0 + y_1 * 3^1 + … + y_n * 3^n
At the beginning we have Y = X and Z = 0;
The idea is to go from 0 to n (and, possibly n+1) and do the following (*):
- if x_i = 0 we are fine, do nothing;
- if x_i = 1, put 3^i on scale B;
- if x_i = 2, put 3^i on scale A and now Y = Y + 3^i, which is, actually makes y_i = 0 and y_(i+1) = y_(i+1) + 1;
Now let’s prove that X will be balanced by this algorithm in not more than [log_3(X)]+1 steps by induction:
[
1) if n = 0, X in {0, 1, 2} by (*) we have
ether 0 on all scales in 1 step
or 1 on both scales in 1 step
or {X, 1} on scale A and 3 on scale B in 2 steps;
2) let’s assume that the proposition is correct for any k <= n, and we have log_3 X = n+1, so, assuming that we’ve already done n steps (added or did not added 1 on level n+1)
we have now 4 possible situations:
a) y_(n+1) in {0, 1} on step n and [step do not add 1 to y_(n+1);
b) y_(n+1) = 2 on step n and [step do not add 1 to y_(n+1);
c) y_(n+1) in {0, 1} on step n and [step adds 1 to y_(n+1);
d) y_(n+1) = 2 on step n and [step adds 1 to y_(n+1);
I) in cases a) – c) on step n+ 1 we have y_(n+1) in {0, 1, 2} and y_k = 0 for all k > (n+1); by (*) and like in 1) we can complete balancing in not more than 2 steps, so having total (n+2) steps at maximum;
II) in case d) on step n+1 we have y_ (n+1) = 0 and y_(n+2) = 1 which can we balanced by putting 3^(n+2) on B, which adds 2 more steps casing finish in (n+2) steps.
We also pay attention, that for each n we put 3^n only on A if y_n = 2 or on B if y_n = 1 and nowhere if y_n = 0. So we do not need more than 1 weight with value 3^n for all n.
]
This proposition arise 1 interesting question: What is the least amount of weights k^n for all n do we need to balance any X on such scales?
First of all, let’s point our attention, that the question is trivial if the only place we can put our weights (except X) is B. In this case we have to have k-1 weights of each k^i weight which represents X in k-nary system.
We have 2 cases k is even and k is odd.
I) If k is odd that in k-nary system x_i will be in {0, … , k-1} where k-1 is even. In this case let’s prove we need (k-1)/2 weights.
For each i if we have y_i <= (k-1)/2, we put y_i weight on B. if y_i >= (k-1)/2 (**) we have z = k – y_i <= (k-1)/2 (***) is the amount s.t. (y_i + z) mod k = 0 and (y_i + z) div k = 1.
It means that z is the amount we can put on A to have 0 there and shift 1 to the next level. And we can not have amount of weights < (k-1)/2 since (**) and (***) can reach equality.
II) if k is even, k-1 is odd, let’s denote k-1 = 2l+1, [(k-1)/2] = l weights is not enough since there is a middle value [(k-1)/2] + 1 = l+1which is strictly greater than [(k-1)/2] = l and l is not enough to shift it to next level, since (l+1) + l = 2l + 1 = k-1 <k, but [(k-1)/2]+1 = l + 1 weight is enough, since, we can up on B amounts up to l + 1 and z = 2l – (l + 1) = l – 1 < l + 1, so we have enough amount of weights to shift to the next level. By the way, [(k-1)/2] + 1 = l + 1 = (2l + 2)/2 = k/2
To summarize, we have the following:
The least amount of k^i weights for each i to balance scales is (k-1)/2 is k is odd and k/2 if k is even. Or, simply, [k/2]
In our proposition we had odd situation so we had (3-1)/2 = 1 weight enough to balance.
Artem's Blog 