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.
How might I select the weights' weights such that he may NEVER escape?
How might I minimise the total weight? (having achieved 1.)
What is the lowest highest weight that a weight must have? (having achieved 1. and 2.)
How much wood must the woodchuck chuck? Just kidding :D
As always explanations/"proofs" are maybe more important than the figures themselves.
mathematics logical-deduction optimization weighing
d'alar'cop
d'alar'copd'alar'cop
$\begingroup$ "non-zero integers" allows negative numbers? $\endgroup$
– leoll2
$\begingroup$ To those wondering, a quacogram is closely related to the more common guacogram, which is the average weight of a fresh avacado. $\endgroup$
– Adam Davis
$\begingroup$ Couldn't Doorknob♦ always free himself by deleting this question and eliminating the scenario from our universe? $\endgroup$
– Engineer Toast
$\begingroup$ @Engineer there's no internet in my cellar $\endgroup$
– d'alar'cop
$\begingroup$ @d'alar'cop Imprisonment against one's will I can get behind. There's lots of reasons to do that. Complicated doors with unbeatable locks? That's not very nice but at least it'll keep him busy as he tries all $2^{99}$ combinations. No internet, though? Now you've gone too far! $\endgroup$
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
The woodchuck must chuck all it could if the woodchuck could chuck wood.
warspyking
JS1JS1
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.
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''f''
$\begingroup$ ant11 has an intuitive proof as to why it MUST be powers of 2. $\endgroup$
$\begingroup$ if it's right... then the lowest highest would be $2^{n-1}$. What do you reckon? $\endgroup$
$\begingroup$ 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. $\endgroup$
– f''
$\begingroup$ 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}$. $\endgroup$
$\begingroup$ @d'alar'cop $1,2,4,8,...,2^{95},3*2^{96},5*2^{96},6*2^{96},7*2^{96}$ works if I didn't make another mistake. (So does the set I gave above, with $2^{96}$ removed from every element.) $\endgroup$
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 TarnawskiJakub Tarnawski
$\begingroup$ So it's an open problem. Thank you. $\endgroup$
$\begingroup$ 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 $\endgroup$
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.
ant11ant11
$\begingroup$ "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? $\endgroup$
– user2357112 supports Monica
$\begingroup$ @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. $\endgroup$
$\begingroup$ @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. $\endgroup$
$\begingroup$ @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. $\endgroup$
$\begingroup$ @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. $\endgroup$
– David Richerby
To my surprise the total weight could be minimized to
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.
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$
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 ThakkarKaran Thakkar
$\begingroup$ I tried this earlier, but you can't do it. 50+99 = 51+98, so he can leave the cellar. $\endgroup$
– ajpolt
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 BeckersIvo Beckers
$\begingroup$ it's different now :p thanks for staying in the spirit of the puzzle $\endgroup$
$\begingroup$ The amount of atoms in the earth are roughly $10^{50}$, and $2^{100}$ is 'only' $1.27\times 10^{30}$ $\endgroup$
– Mathias711
Not the answer you're looking for? Browse other questions tagged mathematics logical-deduction optimization weighing or ask your own question.
There are at least three Kevins on Puzzling. I plan to trap them in my labyrinth
Doorknob's Revenge
Lots of Gold Golden Coins and a Scale
200 Discs - weighing problem
Using a balance scale the minimum number of times, find the median weight person
Six balls, six weighings
212 weights of 1 gram
Using a balance to determine any weight with a set of weights weighing powers of 3
30 fake coins out of 99 coins
30 fake coins out of 99 coins v2
Simplified triple beam scale