mathematics - Trapped in my Cellar

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

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.