by showmyiq » Mon Apr 01, 2013 7:58 pm
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