30 July 2015
Want to weigh in on this puzzle?
I came up with this puzzle on my flight this evening. Therefore, my solution is not fully vetted. I will put my solution and then hopefully some of you will either show a better solution or vouch for mine. As of now, I am going to post the puzZle and hit the sack. I will check your answers tomorrow.
You have a traditional weighing scale and pan balance – you know where you can put weights or stuff on any of the two sides… You also have the following weights (don’t worry about the units): 1, 10, 100 and 1000.
The question is – how many different weights can you weigh combining the above weights?
I get a total of 40 possible weights possible (41 if you count 0)
Hickey said this was your easiest puzzle ever. In his words,”Duh, that would be four Rajib!” We all know it is more than that. Bob will kill me for my comments without any conversation with him, but you need to have fun at someone’s expense after a long night on planes. Who better than Bob?
15: 4C1 + 4C2 + 4C3 + 4C4
Rajib, Unless I am missing something ; the answer is the number of ways one can combine 4 distinct objects in bundles of 1, 2, 3, 4… No?
Sorry, my answer is not correct.. Just realized that the combination argument only for one pan ; I need to consider the other pan too… 🙂 jumped the solution too quickly…
4c1 + 4c2 + 4c3 + 4c4 = 15
Nick and Kenneth, I tried two different ways and came to 40. That should be right. What was your approach?
Hiten and Balaji you might not have taken into account that “subtraction” factor. E.g. With 10 and 1, I can get 9 by putting them in different pans
Oh yeah, so need to add another 4c2 (1 on each side) + 4c3×3c2 (2 on 1 side, 1 on another) + 4c4x 4c3 (3 on 1 side, 1 on another) + 3 (2 on each side) to 15 = 40.
Hope this one is right !
I’m sure there’s a simpler way to solve this!
The answers have been posted Balaji
Philippe, how did you get 31?
lemme try and explain with simple enumeration. First weighing possible is 1; then 10-1 and 10+1 and 10 the next 3 weighings possible, then (100-these four)(100+these four) and 100 are next 9 and then lastly (1000-these 13)(1000+these 13)and 1000 are the next 27
Need to take in account combinations of the weights distributed over both pans that result in unique weight of payload- start with weights in one pan: gives15 possibilities – then combine with payload in one pan and one or more weights in both pans – I forgot a couple of combinations – and finally came to 40 (zero not included)
Rajib, I think it is 4C1x1 + 4C2x2 + 4C3x3 + 4C4x4
The answer should be 40.
Approach A: For any combination, a particular weight is either in Pan A or Pan B or in neither (I will call this Pan C). So each weight can go in any of the three pans. And they are independent of each other. So the total number of combinations is 3x3x3x3 (3 to the power 4 since there are 4 weights) = 81.
One of those combinations is with all four weights in Pan C which means we are measuring zero units of weight (nothing in Pan A or Pan B). Take that out. So, we have 80 combinations.
But Pan A and Pan B are identical to each other. So we have counted twice for each possibility. E.g. Pan A having 10 and 1 and Pan B having 100 is the same as Pan A having 100 and Pan B having 10 and 1. Each of those two combinations measure 89 units.
So the unique combinations are 80/2= 40
Approach B. This is more like mathematical induction. Let’s say with “n” number of weights, we can have F(n) different weights we can measure. When you put in an additional weight – now we have “n+1” weights, how many weights can we measure?
First, we have the original F(n). We do not need the “n+1″th weight for that. Also we can weight whatever the weight of “n+1” is (say W(n+1)). But realize that for every unique weight in F(n), now we can weigh two more weights – W(n+1) minus that unique weight and W(n+1) plus that unique weight.
So F(n+1) = F(n) + 1 + 2xF(n)
Or F(n+1) = 3xF(n) + 1
For n=1, when we have only one weight, we can only weigh one weight. F(1)= 1
To see this in action, note that with two weights 1 and 10, you can weight 4 different weights – 1, 9, 10, 11
Now when you add in 100, you can of course weight the above 1,9,10,11 still. Also you can weigh 100. But for each of 1,9,10,11 you can weigh the difference of it from 100 and the addition of it with 100. So you can weigh 99, 91, 90,89 and 101,109,110,111. Hope this example helped understand the mathematical equation above. Which gives 13
Note that for the above puzzle the rule has to be that W(n+1) is strictly greater than 2 times W(n). Else you will get into overlap issues.
Every succeeding weight has to be more than twice the sum of all the previous weights – not twice of the largest previous weight.
Kenneth, I put an edit – you are right – it has to be the weight of all the combined weight. But you mean more than twice of the combined weight right?
Yes. Mea Culpa
Yes. Mea Culpa
Approach b is way cooler 🙂 this is a good post Rajib Roy