The Weights' Problem - 30/03/2013

[showmyiq]

This puzzle was proposed by Sergey Sokolov via Facebook

What is the minimum number of weights needed to measure every object with total weight of 1gr, 2gr, .. ,120 gr?
Can you find universal formula describing the same algorithm for object with total weight of 1gr, 2gr, …, Xgr?

The Weights' Problem

The-Weights-Problem-Puzzle.jpg.gif (39.69 KiB) Viewed 33206 times

[shashank201090]

its simple
divide x till its not zero and every power of 2 we get should be the weight value and 1gm included.

[showmyiq]

Your logic is absolutely correct but no answer is provided.
Your name will be published as the one who successfully solved the puzzle!

I will provide my way of thinking and generalization of the issue:

Let’s define such set A_s - equal to such set of elements, which can generate all the numbers from 1 to s (included). In our case we are looking for such A_120 with cardinality |A_120| = x, x->min.

We can easily see, that A_1 = {1}

There are different infinite solutions for A_2, for example A_2 = {1,1}, or A_2={1,1,1) and so on (this apply to all the sets with i>1).

Ok, what about A_3? Well A_3 = {1,2}.

Following this logic, we can see that A_7 = {1,2,4} is the minimum solution for i=7 (therefore x=3).
But since walking backwards is not very good approach, we can directly attack the given task by manipulating 120. The pattern extracted shows the minimum weights we need is exactly 7.

A_120 = {60,30,15,8,4,2,1}

You can see that x=7 and it’s not perfect solution (because we have duplicates, like 15 can be represented by {15} or {8,4,2,1}, but that’s the best solution possible).

If you want to calculate A_s, then the minimum X will be defined as {floor(S/2^1), floor(S/2^2), …., floor(S/2^x) =1)

*by floor I defined the up-round value. floor(3/2) = floor(1.5) = 2

As I can analyze further, the best way to avoid duplicates is to supply S equals to 2^j, for any integer j.
Another good reason to use binary math in computers …

Final Answer: 60, 30, 15, 8, 4, 2, 1

[shashank201090]

better solution guyz
use 1,3,9,27,81 to slove.

[showmyiq]

Yes, but that solution is for using scales (you have solved the current puzzle of the day). I mean part I is using weight (ordinary weight – the ones we are using to measure our weight) and part II is using scales (with two weighting plates). That’s why in part II we can lower the total weights by one. I will publish your name as the one who solved the current puzzle and will add few words by myself.

Thanks!

[shashank201090]

ok, good explanation admin.