20

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.

d'alar'cop
  • 12,892
  • 4
  • 49
  • 90

6 Answers6

13

  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.
f''
  • 33,665
  • 4
  • 120
  • 165
  • ant11 has an intuitive proof as to why it MUST be powers of 2. – d'alar'cop May 14 '15 at 00:30
  • if it's right... then the lowest highest would be $2^{n-1}$. What do you reckon? – d'alar'cop May 14 '15 at 00:32
  • 4
    However, the proof isn't rigorous. It doesn't show that there can't be some way to 'skip' a number that somehow makes the highest weight smaller. – f'' May 14 '15 at 00:36
  • @user12408 I agree, I was not rigorous. Your proof of the minimum is very nice. – ant11 May 14 '15 at 00:42
  • 1
    There are ways to 'skip' numbers while the highest weight remains the same, for example $2^{99}-2^{98},2^{99}-2^{97},2^{99}-2^{96},...,2^{99}-2^2,2^{99}-2^1,2^{99}-2^0,2^{99}$. – f'' May 14 '15 at 00:44
  • how does that skip numbers? Isn't it the same thing? – d'alar'cop May 14 '15 at 00:49
  • ant11's proof involves choosing the smallest possible weight every time, but this example shows that the same result can be achieved without selecting the smallest possible numbers. It doesn't use any weights less than $2^{98}$. – f'' May 14 '15 at 00:53
  • OK, yes, sorry. So, you are saying that the minimum can be higher in this way... so why doesn't that imply that you can slide the whole thing down? – d'alar'cop May 14 '15 at 00:59
  • Anyway, I don't know - I'll need to see proofs maybe :p – d'alar'cop May 14 '15 at 01:03
  • 1
    @d'alar'cop $1,2,4,8,...,2^{95},32^{96},52^{96},62^{96},72^{96}$ works if I didn't make another mistake. (So does the set I gave above, with $2^{96}$ removed from every element.) – f'' May 14 '15 at 01:37
  • @user12408 Maybe, but what I don't see is: if it does work, then why doesn't that same idea extend indefinitely? – d'alar'cop May 14 '15 at 01:46
  • if you mentiom that this is an open problem as in the other answer... and also do part 3. I'll give you the tick. – d'alar'cop May 15 '15 at 03:21
  • "other answer" = http://puzzling.stackexchange.com/a/14978/2484 – d'alar'cop May 15 '15 at 08:42
8

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.

warspyking
  • 14,500
  • 10
  • 78
  • 144
JS1
  • 17,874
  • 3
  • 52
  • 103
7

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.

Jakub Tarnawski
  • 71
  • 2
  • So it's an open problem. Thank you. – d'alar'cop May 14 '15 at 20:38
  • This is very important to me and the qn in general... that there is a clear possible solution not involving powers of 2 and thus a possibility if minimising the sum to beneath 2^99 is something – d'alar'cop Jul 11 '17 at 16:26
5

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.

ant11
  • 638
  • 4
  • 14
  • 5
    "Without loss of generality the smallest weight is 1." - why? Do you have a construction that reduces other sets of weights to sets where the smallest weight is 1? – user2357112 May 14 '15 at 03:13
  • @user2357112 1 can be read as "x" where x is the minimal weight that the balance scale is able to "detect". – dmg May 14 '15 at 08:05
  • 1
    @dmg: Why would we be able to decide, without loss of generality, that the set of weights includes the smallest weight the scale can detect? – user2357112 May 14 '15 at 08:10
  • @user2357112 How about you read that question again? We are the ones that choose the weights. ant11 meant that without loss of generality we can say that $x = 1$ – dmg May 14 '15 at 08:23
  • 2
    @dmg: We get to choose the weights, but we're trying to minimize total weight, and we cannot say without loss of generality that there is a solution with $x=1$ that minimizes the total weight. – user2357112 May 14 '15 at 08:26
  • Huh. This also seems to work if you take 2, 3 and 4 as the smallest weights, then powers of 2 from there upwards. Not as valid an answer, since 1 is less than 3, but slightly odd. Also, even if these weights are in grams, the heaviest is 100 times the weight of the planet. d'alar'cop has a very large cellar – LowIntHighCha May 14 '15 at 08:41
  • @user2357112 We're saying "without loss of generality, we are going to use the symbol $1$ instead of the symbol $x$" – dmg May 14 '15 at 08:43
  • 1
    @dmg: Yes, but then how do we get to the point where we're sure it's okay to put that weight into the set? – user2357112 May 14 '15 at 08:44
  • @user2357112 We're simply making sure that you cannot get the same weight by using a combination of previously included weights. – dmg May 14 '15 at 08:47
  • 1
    @dmg: That is a constraint on what weights we can add to our set, but it is not enough to determine which weights we should add. There is nothing in this answer to justify always taking the smallest valid weight. – user2357112 May 14 '15 at 08:51
  • @user2357112 Except that "2. How might I minimise the total weight?" – dmg May 14 '15 at 08:53
  • 5
    @dmg: There are plenty of optimization problems where always picking the minimum weight to add does not result in an overall minimum-weight solution. Read about greedy algorithms; you are making the mistake of thinking that a greedy algorithm will always be optimal. Nothing in this answer justifies the use of a greedy algorithm. – user2357112 May 14 '15 at 08:55
  • @user2357112 In this case it does (except for the last few terms). However, your original question has nothing to do with the optimality of the algorithm, it was about the WLOG. – dmg May 14 '15 at 09:04
  • 2
    @dmg: "WLOG" is a claim that an assumption can be made without losing generality. Assuming that the smallest weight in the set has weight 1 loses generality. – user2357112 May 14 '15 at 09:08
  • @user2357112 In this case it does not. It can be easily proven that any set $A$ (being minimal or not) can be translated to a set $A'$ containing 1 and weighing less than $A$. I suggest trying it yourself with a few suboptimal sets. – dmg May 14 '15 at 09:17
  • 2
    @dmg: I do not see how such a proof would work. I have tried various weight-reduction schemes, and every one I tried had some sort of flaw. In my original comment, I specifically asked ant11 for the construction you claim exists. Can you describe the process? – user2357112 May 14 '15 at 09:21
  • 5
    @dmg Please give details of such a scheme. For example, dividing all the weights by the smallest weight doesn't work, since the weights have to be integers. Subtracting the same amount from each weight doesn't work because 2,3,4 has no solution but 1,2,3 has one. – David Richerby May 14 '15 at 10:33
2

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.

Karan Thakkar
  • 250
  • 2
  • 9
0

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.

Ivo
  • 11,217
  • 3
  • 37
  • 58