Trapped in my Cellar

Question

I have taken Doorknob hostage in my cellar. He is "perfectly" trapped - solid walls, solid floor, solid roof, no windows, etc. The only way out is a steel door and the only way to unlock the door is by means of two-pan balance scale (accurate to the quacogram).

I have provided 100 weights. Each weight will have its own (non-zero positive integer) weight (in quacograms) accurately written on it. He must put a non-zero number of weights on either side of the scale pans such that they balance perfectly (no trickery on the weights allowed - just the weights). Doorknob has no computer or writing implements - also he is is always able to somehow manoeuvre the weights no matter their weights.

1. How might I select the weights' weights such that he may NEVER escape?
2. How might I minimise the total weight? (having achieved 1.)
3. What is the lowest highest weight that a weight must have? (having achieved 1. and 2.)
4. How much wood must the woodchuck chuck? Just kidding :D

As always explanations/"proofs" are maybe more important than the figures themselves.

Answer 1

Part 1: What is a possible combination of weights?

Use power of 2 weights from 2^0 to 2^99 (obvious, everyone already said so)

Part 2: What is the lowest total weight?

User12408 already showed that the lowest total weight can be obtained by using power of 2 weights to reach total weight 2^100-1. A quick summary of the proof:

With 100 weights, there are 2^100 possible weight combinations (each weight can either be in a subset or not). Given that "no weights" is one of these 2^100 subsets, the best to hope for is for the subsets to cover weight values 0..2^100-1, which can be achieved by using power of 2 weights.

Part 3: What is the lowest highest weight? This is the interesting part.

Some people said that 2^99 was the answer for this. But that is not true.

Take for example the case of 5 weights. One might think that 1 2 4 8 16 would be the optimal set.

However, a counterexample is the set: 6 9 11 12 13

This set produces the following distinct subset sums: 6 9 11 12 13 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 38 39 40 42 45 51

(Edit: A four weight counterexample is: 3 5 6 7 by the way)

Something similar can be done for the 100 weight case, but it would be hard to find the optimal solution.

As Jakub Tarnawski pointed out, this is an open problem that even has some kind of reward for a solution (this link comes from Jakub's answer): http://www.openproblemgarden.org/op/sets_with_distinct_subset_sums

Also:

The woodchuck must chuck all it could if the woodchuck could chuck wood.

Answer 2

1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

   • The set of powers of 2 is also the only way to achieve this total weight: To have a total weight of $2^{100}-1$, every integer from 0 to $2^{100}-1$ must correspond to some set of the weights. In particular, if we choose the weights from lowest to highest, we must always choose the smallest integer that is not a sum of any other set of weights, because otherwise there would be no set with that as its total weight. Then ant11's construction is forced.

Answer 3

I'm not sure about the version of the problem where you want to minimize the sum, but you'll probably be surprised to find out that the version where you want to minimize the maximum number is known - and an open problem in combinatorics :)

See here for example: http://www.openproblemgarden.org/op/sets_with_distinct_subset_sums

The powers of two are the most natural construction, but not the best possible; for example, if you wanted to give 4 weights, you could give 1,2,4,8, but you could also give 3,5,6,7 (and 7 < 8).

In Karan Thakkar's answer, it's easy to give two subsets that sum up to the same value, for example 50 + 53 = 51 + 52. (I'm writing this here since it seems that I can't comment.)

The powers of two are indeed optimum for minimizing the sum, but proofs that people were giving in the comments are unconvincing. The one in user12408's answer works.

Answer 4

Without loss of generality the smallest weight is 1. None of the weights can be the same, so the next smallest weight must be two. Three is now no longer possible, so the next smallest weight is four. If the next weight is less than 8, it is some combination of the previous weights, so the next smallest weight is 8. Induct, and the weights must be the powers of two, up to $2^{99} $. This is the smallest possibility.

Answer 5

To my surprise the total weight could be minimized to

188849

Which is better than $2^{100}-1$

This can be achieved by

Dividing the total number of weights (100 in this case) in two equal groups of 50 each.

Group 1
50 to 99 derived by logic that sum of 2 smallest elements in group is higher than maximum value present in group.
in general first value equals to $n$ where $n=count($group_length$)$.

$x= \sum_{n=50}^{99} n = 3725$

Group 2
Would consist of numbers from $x-$ min value of group 1 $ - 1$ upto $ x - 1$
i.e. from $x - 49$ up to $x-1$ i.e. ( 49 elements)
50th element of group 2 can be found as $ = max(g1) + max(g2) + 1$ which in our case is 3824

Total, lowest, highest weight.

Considering above case
Total weight $\sum_{n=3676}^{3725} + 3824 = 188849 $
Lowest and highest weights 50, 3824 respectively.

Answer 6

Assuming Doorknob is human let's just take 100 weights of 1000 kilo. He would not be able to lift it so he couldn't escape. This is the only practical solution since $2^{100}$ is huge! Even more than the number of atoms in the universe I believe.