tag:blogger.com,1999:blog-5871184605628305545.post984288679486625148..comments2013-05-25T03:36:33.414-07:00Comments on Puzzled: Pieces of a StoneAnonymoushttp://www.blogger.com/profile/02364548875097103884noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5871184605628305545.post-64342597171682552642013-04-02T05:21:03.577-07:002013-04-02T05:21:03.577-07:00The answer by Manoj is correct.
@Anshul: Try your ...The answer by Manoj is correct.<br />@Anshul: Try your solution with a base case of 13kg weight. It won't work. Try using Manoj's approachAnonymoushttps://www.blogger.com/profile/02364548875097103884noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-82407204132405828272013-01-03T22:19:01.467-08:002013-01-03T22:19:01.467-08:00log2(n)
break the stone into weights w_i's wit...log2(n)<br />break the stone into weights w_i's with weight being.. <br />w_i= ((2^i)-1)<br />Anonymoushttps://www.blogger.com/profile/07786840826196653362noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-33320205312553045432012-08-12T14:41:44.379-07:002012-08-12T14:41:44.379-07:00Let m be the minimum number of pieces required. Th...Let m be the minimum number of pieces required. Then m is the least positive integer such that 3^m >= 2n+1. <br /><br />Let w_1,w_2,...,w_m be the weights required. Then w_i = 3^(i-1) for i = 1,2,...,(m-1) and w_m = n-(sum of all other weights). <br /><br />PROOF:- Let us say n be the largest weight I can form using m weights (sum = n and each w_i is integer ). Then 3n+1 is the largest weight that can be formed using m+1 weights. This is because using the previous m weights, n positive and n negative weights can be formed which when combined with a weight of 2n+1 gives all weights in the range n+1 to 3n+1. Denote by M_n, the minimum number of weights required to measure all the weights between 1 and n. from the above discussion, we can say that M_(3n+1) = M_n + 1. Also, M_1 = 1. So, M_n = 2 for n = 2,3,4.....` The rest is trivial.Anonymoushttps://www.blogger.com/profile/05482063307493931410noreply@blogger.com