Weighing Problem - Discrete Mathematics Puzzle
Source: Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB)
Problem:
Solution:
Highlight the part between the * symbols for the answer.
* Assuming a two-pan balance (weights may go on either pan, as in Vinod Reddy's setup):
Part 1: minimum number of weights = the smallest m with (3^m - 1)/2 >= n, i.e. m = ceil(log_3(2n + 1)), using weights 1, 3, 9, ..., 3^(m-1). Upper bound: each weight has 3 states (left pan, right pan, unused), giving at most (3^m - 1)/2 distinct positive outcomes. Achievability: balanced ternary - every integer up to (3^m-1)/2 is a sum of distinct signed powers of 3, and inductively the new weight 3^m = 2*(1+3+...+3^(m-1)) + 1 extends the reachable range exactly to (3^(m+1)-1)/2.
Part 2 (k copies of each distinct weight): each weight now has 2k+1 states (-k..k pans), so m distinct weights cover at most ((2k+1)^m - 1)/2 values, and the bound is achieved by 1, (2k+1), (2k+1)^2, ..., giving m = ceil(log_(2k+1)(2n + 1)). Same induction: with weights up to (2k+1)^(m-1), k copies each, the largest gap-free reach is k*(1 + (2k+1) + ... ) = ((2k+1)^m - 1)/2.
(If weights may sit on only ONE pan, replace base 3 by base 2: powers of 2, m = ceil(log_2(n+1)); with k copies, powers of k+1.)
Solution by Vinod Reddy G and Aashay (with Anoopam Agarwal) from the comments. *
Problem:
For a given positive integer n, what would be the minimum no. of weights required so that we can weigh all positive integers <= n
Follow up Generalized problem:
If we have k copies of each distinct weight, then what is the minimum no. of distinct weights required ?
Old Related Puzzle:
There is a very different popular problem but knit in the same story (posted 4 years back on the blog): Weighing Problem
Follow up Generalized problem:
If we have k copies of each distinct weight, then what is the minimum no. of distinct weights required ?
Old Related Puzzle:
There is a very different popular problem but knit in the same story (posted 4 years back on the blog): Weighing Problem
Note : Weights are of integer values only.
Solution:
Highlight the part between the * symbols for the answer.
* Assuming a two-pan balance (weights may go on either pan, as in Vinod Reddy's setup):
Part 1: minimum number of weights = the smallest m with (3^m - 1)/2 >= n, i.e. m = ceil(log_3(2n + 1)), using weights 1, 3, 9, ..., 3^(m-1). Upper bound: each weight has 3 states (left pan, right pan, unused), giving at most (3^m - 1)/2 distinct positive outcomes. Achievability: balanced ternary - every integer up to (3^m-1)/2 is a sum of distinct signed powers of 3, and inductively the new weight 3^m = 2*(1+3+...+3^(m-1)) + 1 extends the reachable range exactly to (3^(m+1)-1)/2.
Part 2 (k copies of each distinct weight): each weight now has 2k+1 states (-k..k pans), so m distinct weights cover at most ((2k+1)^m - 1)/2 values, and the bound is achieved by 1, (2k+1), (2k+1)^2, ..., giving m = ceil(log_(2k+1)(2n + 1)). Same induction: with weights up to (2k+1)^(m-1), k copies each, the largest gap-free reach is k*(1 + (2k+1) + ... ) = ((2k+1)^m - 1)/2.
(If weights may sit on only ONE pan, replace base 3 by base 2: powers of 2, m = ceil(log_2(n+1)); with k copies, powers of k+1.)
Solution by Vinod Reddy G and Aashay (with Anoopam Agarwal) from the comments. *
Isn't it log3(n)+1 ?
ReplyDeleteThis comment has been removed by the author.
ReplyDelete2^0 + 2^1 +2^2 +2^3 +2^4 +2^m = 20 * (2^(m+1) - 1)/(2-1) = 2^(m+1) – 1 > n
ReplyDelete2^(m+1) > n + 1
m+1 > log (n+1) / log 2
m > [log (n+1) / log 2] - 1
The minimum no. of weights = the smallest integer value of m which satisfies the above inequality
Solution to Generalised problem: Minimum number of distinct weights required (M) = ceiling (log (base=k+1) (n)).
ReplyDeleteTo show that it is possible in this number of weights,
Choose each weight as a power of k+1.(1, k+1, (k+1)^2, (k+1)^3....(k+1)^(M-1)).
And now note that every number less than or equal to n can be written uniquely in base k+1 using at most k in the coefficients=> at most k weights
Now to prove that this is the best we can do, suppose we have J different weights and K pieces of each weight.
Then, the maximum number of combinations of these possible are (k+1)^j [we can choose 0 to k pieces of each weight].
Assuming these combinations dont overlap and every weight <=N are represented by these combinations,
(k+1)^j >= N. => j>=log (base(k+1) (N)). Since J is an integer, we have j>= ceiling(log(base(k+1)(N)).
But from our original representation, we have M = ceiling(log(base(k+1)(N)), which implies j>=M
Therefore M is the best case representation.
assuming no repetition of weight,
ReplyDeleteif we can use both sides of a weighing machine then " k | sigma(3^k) >=n ",
if only one side of weighing machine is available then " k | sigma(2^k) >= n"
floor( log2 (n) ) + 1.
ReplyDeleteFor example when n = 1, no. of weights = 0 + 1 = 1(1)
n = 2, no. of weights = 1 + 1 = 2 (1,1)
n = 3, no. of weights = 1 + 1 = 2 (1,2)
n = 4, no. of weights = 2+ 1 = 3 (1,1,2)
n = 5, no. of weights = 2 + 1 = 3 (1,2,2)
no of weights required will be three up to n = 7. For n = 8 to n = 15, no. of weights required will be 4. For 15 -> 4(1,2,4,8). Transition happens at n = perfect power of 2.
For the first part - 1,3,9,... till the heaviest weight becomes greater than or equal to n.
ReplyDeleteExplanation :
Represent the number n in base 3.
Let it be something like 122102110001.
We have only one weight for each power of 3, and hence can only form values containing digits 1 or 3 in them.
But we can also add other weights to the side containing 'n'. So, we add weights corresponding to thse places that have 2 in n's representation and repeat this step again if new 2's are obtained after addition.
That is we add 011001000000 or 3^6, 3^9 and 3^10, thus forming:
122102110001
+011001000000
211110110001
+100000000000
1011110110001.
This new number contains only ones or zeroes. Also, the ones are in different places than the ones which we add to create the number. So, log(base 3)(n) + 1, weights will do.
It is clear that the higher the base, less number of weights will be required to represent the number. Also, we can represent each digit if and only if we have [base/2] (greatest integer function) weights for each value (values are base^i for i=0,1,2,...).
ReplyDeleteI am assuming we weigh using a two pan model i.e if we have weights 1 and 3 then weighing 2 is possible by keeping 3 in one pan and 1 in another pan. Lets define reach(S) where S is a set of weights is the maximum n such that all numbers <= n can be weighed.
First of all for a given m weights we can weigh at most (3^m-1)/2 numbers because each number has three possibilities,it can go to either of pans or none at all so 3^m. the -1 is because of removing the case when none of the numbers come in any of the pans. Finally for each configuration there is an equivalent configuration when we reverse weights in both pans so the division by 2.
Now we will construct a set of weights S inductively such that |S| = m and reach(S) = (3^m-1)/2.
Basis : for m = 1 the set S = {1} and reach(S) = 1 = (3^m-1)/2. Now lets say its true for all m < M.i.e for all m < M there exists a set of weights S such that |S| = m and reach(S) = (3^m-1)/2. Let the set for M-1 be T and
Tr = reach(T). Now add the weight Tn = 2*Tr+1 to the set T. Now with the new set we can weight all numbers from 1 to Tr(because of original M-1 weights) and Tr+1 to Tn-1(using Tn and original achievable weighs of 1 to Tr) and then from Tn+1 to Tn+Tr.
So the reach of new constructed set is Tn+Tr i.e 3*Tr+1 = 3*((3^(M-1)-1)/2)+1 = (3^M-1)/2. and the weights turn out to be 1,3,9,27,... Now its easy to answer the reverse question i.e for a given n what is the minimum carnality set S such that reach(S) >= n.Here the minimum carnality is m = ceiling(log(n base 3)) and the set is {1,3,9,..,3^m}
Now in the case when k copies can be taken the bound on reach(S) where |S| = m will be ((2k+1)^m-1)/2(why?). And in the induction step of the construction let T,Tr be defined as above and Tr = ((2*k+1)^(M-1)-1)/2. Then we add 2*Tr+1 to the set T. Here k copies of 2*Tr+1 can be used. Now using these k copies and original set we can get the reach of new set to be ((2*k+1)^M-1)/2(how?).
Similar to first problem we can use this to answer the reverse question easily.
Your Solution is correct. I solved it using similar approach.
DeleteYou did a small calculation mistake. Let me correct it.
minimum carnality of m = ceiling(log(2n+1 base 3)).
For the 2nd case :
On calculating, answer will come out to be ceiling(log((2n+1) base (2k+1)))
For every weight wi, we can use it as 1.wi , 2.wi, 3.wi....k.wi or 0.wi, or -1.wi, -2.wi....-k.wi.
There are 2k+1 possibilities for each weight. So, for m weights, we can weigh at maximum (2k+1)^m no. But 0 will also be included in it, Also, For every positive no. there is negative no. (Just reverse the sign of each weight). So, there is at maximum ((2k+1)^m - 1)/2 no. which can be weighed. This is an upper bound. Now use Induction to show that this upper bound is achieved.
The weights would come out to be 1, 2k+1, (2k+1)^2....(2k+1)^(m-1)
:)
Hi Aashay,
DeleteSince you had the similar approach you might already have figured out the solutions but here are two other puzzles.
So the problem setting is same as the above one except some additional constraints. First lets say we have the weights w0,w1,w2..wm such that wo<w1<w2<...wm
a) what is the minimum number of weights that must be used to weigh all numbers <= n if it is constrained that no two neighbour weights are to be used at the same time i.e if wi is used then neither of wi-1 and wi+1 are to be used.
b) what is the minimum number of weights that must be used if it is constrained that no two neighbour weights are to be used in the same pan(or opposite pan).
Cheers :)
I saw your reply today only.
DeleteThanks for sharing variations of problem :)
Ans : a ) For m weights w1, w2,.. wm , max reach = floor( (2^(m+1)) /3) i.e. min weights required = ceil( log (3n base 2)) - 1
weights will come out to be : 1, 2, 4, 8, 16... 2^(m-1)
Brief outline of solution : Let Tk denote reach of first k weights, and Wk denotes kth weight.
Then, Tk + 1 = W(k+1) - T(k-1) (why?)
Base case : W1 = 1, W2=2, T1 = 1, T2=2
Use Induction to get weights and max reach.
b)
Tk + 1 = W(k+1) - Tk
=> W(k+1) = 2*Tk + 1
Also, Tk = Wk + T(k-2)
Base case : W1 = T1 = 1, W2=T2 = 3
Recursively find out W's and T's
if k is odd : W(k+1) = 1 + 2*( W1 + W3 + W5 + ... + Wk )
if k is even : W(K+1) = 1 + 2*( W2 + W4 + W6 + ..... + Wk )
weights are coming out to be : 1, 3, 7, 17, 41, 99...
:)
1. Log(2x+1)/Log(3)
ReplyDelete2. Log(2kx+1)/Log(2k+1)
The previous submit was wrong, I guess.
ReplyDelete1. floor(log(2x+1)/log(3))+1
2. floor(log(2x+1)/log(2k+1))+1
Logic: Given that with k copies of weights (w_i) you can do a 2k+1-ary encoding of all the numbers from -k*sum(w_i) to k*sum(w_i). Therefore, the most weights-number efficient way to do it would be to place weights as 1, 2k+1, (2k+1)^2, (2k+1)^3, .... and so on. The largest weight that can be measured in this way would be (1+(2k+1)+(2k+1)^2+.....)*k.
That is the two-pan answer (weights on both sides): ceil(log3(2n+1)). If the balance allows weights on one pan only, it is ceil(log
ReplyDeleteCorrect for the one-pan interpretation (answer: ceil(log2(n+1)) weights 1,2,4,...). If weights can go in both pans you do better wi
ReplyDeleteCorrect for the one-pan version of the follow-up, and the (k+1)^j counting bound is the right optimality argument. For two pans the
ReplyDeleteRight - those two sums are exactly the two cases: 1+3+...+3^(m-1) = (3^m - 1)/2 >= n for two pans, 2^m - 1 >= n for one pan. (repli
ReplyDeleteCorrect for one-pan (allowing repeated weights, as your (1,1,2) example for n=4 shows). Transition points are at powers of 2, as yo
ReplyDeleteCorrect - this is balanced ternary in constructive form: digits of 2 are resolved by carrying (adding the next power of 3 flips 2
ReplyDeleteThe counting bound is exactly right - and combined with the powers-of-3 construction achieving (3^m - 1)/2, it proves optimality,
ReplyDeleteSecond version is right (up to the floor/ceiling edge: ceil(log_{2k+1}(2n+1)) is the clean form - see Aashay's correction). The (2k
ReplyDeleteCorrect - ceiling is the right rounding, and the (2k+1)^m >= 2n+1 count with the sign-symmetry argument closes both parts. (replie
ReplyDeleteFun variants - (a) drives you toward Fibonacci-style/Zeckendorf structures, which matches Aashay's floor(2^(m+1)/3) answer below. W
ReplyDeleteNice work - the recurrence T_k + 1 = W_{k+1} - T_{k-1} is the right invariant for the no-neighbors constraint, and the powers-of-2
ReplyDelete