52

1) You are a shopkeeper who is selling sugar between 1-100 kg .Now you have to design 5 weights in such a way that any integer weight between 1-100 can be measured in a single attempt ,without using more than 5 weights.You can't repeat weights.

He gave me time like 1 hour to figure it out, and i tried it as hard as i could. But finally i couldn't figure out more than this that weights have to be distributed on both sides of measurement.

Does anybody have some clue as what could be the answer.

emory
  • 239
mrigendra
  • 513
  • What does it mean, "you can't repeat weights?" No two of these five weights may be the same? And why would that make the problem any easier? – Kaz Oct 31 '13 at 15:02
  • And btw, what is a "single attempt"? By a single attempt, I can only have two answers: yes or no, and surely not 100 different answers. Do I miss something? – yo' Oct 31 '13 at 15:10
  • 1
    Perhaps the "single attempt" aims to check the correctness of a weight claimed for a premeasured amount of sugar? – hardmath Oct 31 '13 at 15:33
  • Single attempt, as in, you can't measure 1kg of sugar 100 times or even 50kg of sugar twice...you have to balance the scale with 100kg of sugar on it. – Tim Lehner Oct 31 '13 at 20:02

3 Answers3

58

Use powers of $3$: $1,3,9,27,81$ can weigh anything up to $121$.

The trick is to place weights on both sides of the pan. Without that, the maximum you can do is with powers of two, and five of those will allow you to go up to $63$. At least if you only consider exact weighings. If you're allowed to infer that the weight is $14$ if it is heavier than $13$ and lighter than $15$ will probably allow you to go a bit higher, and I don't yet see a systematic way of going about this.

$121$ is the maximum you can do with 5 weights. See http://www.uri.edu/artsci/math/clark/mthdl/scale/explore.pdf for necessary and sufficient conditions.

On the other hand, since you can optimally go up to $121$, there is some choice if you only want to go up to $100$. There are 132 sets of weights that work, 15 of them measuring up to exactly $100$, and the lexicographically smallest one is $1,3,7,22,67$.

Further, the proof for sufficiency is constructive. That is, you can figure out an algorithm to tell you which weights go on which side for any of these sets of weights.

ronno
  • 11,390
  • 2
    How do you measure 41 kg with these weights without repeating weights? – Alexander Vlasev Oct 31 '13 at 11:11
  • 20
    Put $81$ on one scale, the sugar and $1,3,9,27$ on the other. – ronno Oct 31 '13 at 11:12
  • 4
    Oh I see. Riiight you can put them on both sides – Alexander Vlasev Oct 31 '13 at 11:13
  • 1
    If integer weight is assumed and we only need to get at that amount, we can double each weight and use two measurements for any weight that is not exact to show that the weight is a number in between. – abiessu Oct 31 '13 at 12:30
  • @ronno Would the powers of four ( or five...) also work? – this Oct 31 '13 at 13:12
  • 5
    @self.: No. This can be thought of as an expression of base 3 in a strange way. When counting in base 3 you have for each power of 3 a value of either zero, one or two. With this solution we are doing the same thing effectively but we give them values of one (its on the oposite side to the item being weighed), zero (not on the scales) or minus one (its on the same side as the weight being measured. If you wanted higher powers you'd need multiples of some weights. eg if you always had two of each size then powers of five would work. Powers of four would work as well but be inefficient. – Chris Oct 31 '13 at 13:19
  • @Chris Interesting way of looking at base 3! I wrote out some of the base 3 numbers in this form, and it's strange, because when you carry you don't set to 0, but to -. – Cruncher Oct 31 '13 at 14:50
  • Okay, powers of 3 can weigh up to 121. Is there or are there more solutions to this problem , where 5 weights can weigh up to 100? – krikara Oct 31 '13 at 14:52
  • @Cruncher: yeah, its more the mathematical analogy that is easy to imagine. I imagine I would get completely muddled if I tried to actually do maths like that... :) – Chris Oct 31 '13 at 14:58
  • 5
    @Chris: The system is known as balanced ternary. – Brian M. Scott Oct 31 '13 at 15:39
  • @krikara I would suspect, that finding all possible solutions would be even more interesting than this great answer. – Cruncher Oct 31 '13 at 15:45
  • 3
    Nice. But why powers of three? – Grimm The Opiner Oct 31 '13 at 16:41
  • 2
    @user1158692 Because, effectively, there are three options for each weight: it can go on the left side of the balance, the right side of the balance, or not go on the balance at all. This suggests a ternary system for representing which of the three choices is made for each weight, and that leads to the base-three representation. – Steven Stadnicki Oct 31 '13 at 17:24
  • 1
    @krikara There is basically a optimization problem. The first two weights must be 1 and 3. Each subsequent weight can be no greater than twice the sum of the weights before it plus 1. The total sum of the weights must be greater than or equal to 100. So, for example, { 1, 3, 8, 25, 63 } is a perfectly valid solution. – Kyle Hale Oct 31 '13 at 19:38
  • @KyleHale That's what I was thinking earlier, but that's not strictly true - a linear combination of two weights can serve as a single weight; for instance, one could start 1, 6, 9 (which gets you to 10) and then 21, 63. This comes just short (you get to 94), but I'm not 100% certain that the same idea couldn't be used to get to 100 while violating the 'no greater than twice the sum of the weights before' condition. – Steven Stadnicki Oct 31 '13 at 20:22
  • @StevenStadnicki Actually, you've stumbled on the reason that rule is so airtight: ignoring it leaves too many gaps to fill. If the maximum consecutive weight that a group of 3 weights can generate is x, the 2 remaining weights' maximum is 2x + 1 and 6x + 3. For their sum to be 100, x must be at least 11. – Kyle Hale Oct 31 '13 at 21:18
  • Balanced ternary is the key. In fact, there was an idea that early electronic computers would use it instead of binary. – Eric Jablow Nov 01 '13 at 01:59
  • @BrianM.Scott: Cool. I should have known it was a well studied thing. A name means I can read more about it. :) – Chris Nov 01 '13 at 09:36
6

If you used $1,2,4,8..$ kg weights, you could measure until $127$ kg only using seven different weights on one side of scale. Because numbers $0-127$ is written with maximum seven digits in base $2$, i.e. $100=1100100_2$. You can use only one side of scale because you only have $0$ and $1$ digits in base $2$.

On the other hand, in base $3$ you have $1,0,2$ and you can use max five digits to represent numbers in $0-100$. But you have to repeat weights if you use just one side of scale due to digit $2$. But you can rewrite a number in base $3$ as substraction of two numbers in the same base which have only digits $0$ and $1$. For example, $7=21_3$, which means you have to use two $3$ kg and one $1$ kg to measure $7$ kg if you only use one side of scale. But since you are not restricted to only one side, you can write $7$ as $101_3-10_3$. You put $101_3=10$ kg to left side, $7$ kg and $10_3=3$ kg to right.

newzad
  • 4,855
  • 1
    A simple proof of sufficiency: Write the weight to be measured (W say) as 121 - X. 121 is 11111 in ternary representation. If i-th digit (from right starting from 0) of X is 0, put the weight 3^i in the right arm of the scale. If it is 1, put 3^i in neither arm. If it is 2, put it in the left arm. Let the left and right sums be L and R. It can be easily seen that R - L = W. Not only do R and L contain only 0's and 1's in ternary, they don't contain 1 in the same place (power of 3). – Prasanth S Oct 31 '13 at 18:55
  • @SPrasanth that seems a very clever algorithm. Thanks. – newzad Oct 31 '13 at 19:02
  • @SPrasanth I didnt get that, can you please elaborate? – ADJ May 16 '16 at 14:01
  • @SPrasanth I dont see it working, e.g. for 121=11111 in ternary, according to your logic "If it is 1, put 3^i in neither arm", you wont put any weight in any arm, which is wrong. Or did I misunderstood? – ADJ May 17 '16 at 04:21
  • @Tingya I know this is late, but regardless... Step 1 is to write the weight W as 121-X. Then we look at the ternary rep of X. So for W=121, X=0, and all the weights will go in the right arm. – Prasanth S Nov 22 '16 at 04:37
  • The following can work as a proof: Let X be x0 x1 x2 x3 x4 in ternary. 121 = 3^0 + ... + 3^4, X = x0 3^0 + ... + x4 3^4, then W = 121 - X = (1-x0) 3^0 + (1-x1) 3^1 + ... + (1-x4) 3^4. 1-xi will be one of 0,1 and -1. If 1-xi = 1, we put 3^i in the right arm, if 1-xi is -1 we put it in the left arm (since we have to subtract 3^i to get W). That way R-L = W – Prasanth S Nov 22 '16 at 04:47
0

Minimum weight is 1 kg max is 18 kg

You can obtain 25337 combinations

Here is the code

a = 1

Do While a < 100

   b = a + 1
   Do While b < 100
    c = b + 1
    Do While c < 100
        d = c + 1
        Do While d < 100
            e = d + 1
            Do While e < 100
                total = a + b + c + d + e
                If total = 100 Then
                    counter= counter + 1
                    Text1.Text = counter
                End If
                e = e + 1
                DoEvents
            Loop
            d = d + 1
        Loop
        c = c + 1
    Loop
    b = b + 1
Loop
a = a + 1
If a > 18 Then
    Text2.Text = "THE END"
End If

Loop

xerxesgunes
  • 1