The Weights Puzzle
From the 1966 Moscow Math Olympiad:
Prove that you can choose six weights from a set of weights weighing 1, 2, …, 26 grams such that any two subsets of the six have different total weights. Prove that you can’t choose seven weights with this property.
Let us define the sequence a(n) to be the largest size of a subset of the set of weights weighing 1, 2, …, n grams such that any subset of it is uniquely determined by its total weight. I hope that you agree with me that a(1) = 1, a(2) = 2, a(3) = 2, a(4) = 3, and a(5) = 3. The next few terms are more difficult to calculate, but if I am not mistaken, a(6) = 3 and a(7) = 4. Can you compute more terms of this sequence?
Let’s see what can be said about upper and lower bounds for a(n). If we take weights that are different powers of two, we are guaranteed that any subset is uniquely determined by the total weight. Thus a(n) ≥ log2n. On the other hand, the total weight of a subset has to be a number between 1 and the total weight of all the coins, n(n+1)/2. That means that our set can have no more than n(n+1)/2 subsets. Thus a(n) ≤ log2(n(n+1)/2).
Returning back to the original problem we see that 5 ≤ a(26) ≤ 8. So to solve the original problem you need to find a more interesting set than powers of two and a more interesting counting argument.
Share:
Dan:
Just note that lower bound for a(n) can be slightly improved by considering instead of different powers of two the Fibonacci numbers (any integer can be represented in unique way as sum of Fibonacci numbers – Zeckendorf representation).
24 August 2010, 3:39 pmInstead of:
a(n) ≥ log2n
one gets
a(n) ≥ loggn, g – golden ratio
Tanya Khovanova:
Dan,
Zeckendorf representation uses non-consecutive Fibonacci numbers. There are many way to represent a number as a sum of Fibonacci numbers: 9 = 8 + 1 = 5 + 3 + 1.
24 August 2010, 3:42 pmAndrew Buchanan:
A solution is: 11,17,20,22,23,24
Call a set of +ve integers *distinctive* if every subset sums to a distinct value.
Call the maximum of a finite set its *max*.
Let m(k) be the minimum max over all distinctive k-sets (i.e. the sets of order k).
We are interested to track the distinctive k-sets which exhibit a max value = m(k).
It’s easy to see that:
m(1) = 1, exhibited by {1}
m(2) = 2, exhibited by {1,2}
m(3) = 4, exhibited by {1,2,4} or {2,3,4}
and slightly harder to see that:
m(4) = 7, exhibited by {3,5,6,7}
But what happens after that?
One clear pattern is emerging of powers of 2: {1}, {1,2}, {1,2,4}…
But for k=4, this pattern would give {1,2,4,8} and we can see that this is not optimal.
But how about extending the pattern which goes {1}, {1,2}, {2,3,4}…?
Suppose that we have a distinctive set where for all relevant i, the sum of any i members is always less than the sum of any i+1 members. We will call such a set *orderly*. It’s
pretty clear that {1}, {1,2}, {2,3,4} are all orderly.
What is less obvious is that from any orderly k-set, S, we can construct an infinite number of orderly (k+1)-sets.
PROOF BY CONSTRUCTION:
Write the 2^k subset-sums of S in numerical order, dividing them up into *segments* according to the order of the subset:
a_(0,1),
a_(1,1), a_(1,2), … a_(1,k),
a_(2,1), a_(2,2), … a_(2,k(k-1)/2),
…
a_(i,1), a_(i,2), … a_(i,C(k,i)),
…
a_(k,1)
If we made T=S U {0}, then T is not distinctive. Every subset-sum of T can be made in 2 ways, with and without 0.
But if we define U = T+n i.e.g U = {x | x-n in T} for some suitably large n yet to be defined, then there are two families of subset-sums of U:
a_(0,1),
n+a_(1,1), n+a_(1,2), … n+a_(1,k),
2n+a_(2,1), 2n+a_(2,2), … 2n+a_(2,k(k-1)/2),
…
in+a_(i,1), in+a_(i,2), … in+a_(i,C(k,i)),
…
kn+a_(k,1)
and:
n+a_(0,1),
2n+a_(1,1), 2n+a_(1,2), … 2n+a_(1,k),
3n+a_(2,1), 3n+a_(2,2), … 3n+a_(2,k(k-1)/2),
…
(i+1)n+a_(i,1), (i+1)n+a_(i,2), … (i+1)n+a_(i,C(k,i)),
…
(k+1)n+a_(k,1)
Now no two values from the same family are the same, because all that has happened in each family is that the segments have been spread further apart.
If n is suitably large, then there will be no overlaps across the two families. The segments from the two families will alternate in size.
Firstly:
in+a_(i-1,1), in+a_(i-1,2), … in+a_(i-1,C(k,i-1)) < in+a_(i,1), in+a_(i,2), … in+a_(i,C(k,i)),
as long as:
a_(i-1,C(k,i-1)) < a_(i,1)
which is always true, by the assumption that the original set was orderly.
But secondly:
in+a_(i,1), in+a_(i,2), … in+a_(i,C(k,i)), a_(i,C(k,i))-a_(i,1).
So if we set n*(k) = 1 + max{i | a_(i,C(k,i))-a_(i,1)}, then for any n >= n*(k), U is orderly. The old segments concatenate in pairs to make new ones:
in+a_(i-1,1), in+a_(i-1,2), … in+a_(i-1,C(k,i-1)) concatenated with in+a_(i,1), in+a_(i,2), … in+a_(i,C(k,i))
becomes:
b(i,1), b(i,2), … b(i,C(k+1,i))
where:
b(i,j) = in+a_(i-1,j), for j =< C(k,i-1)
b(i,j) = in+a_(i,j-C(k,i-1)), otherwise
END OF PROOF
Now we will always take n = n*(k), because we are looking for the minimal solution.
Let’s see this at work, then. m(3)=4, exhibited by (2,3,4). The subset sums are:
0,
2,3,4,
5,6,7,
9
n*(3) = 3 (the span of the largest segment, so the two families for subset-sums for the next level up:
0,
5,6,7,
11,12,13,
18
3,
8,9,10,
14,15,16,
21
These concatenate in pairs as:
0,
3,5,6,7,
8,9,10,11,12,13,
14,15,16,18,
21
We can read off the set exhibiting M(4)=7 from the second row.
Now let’s explore unknown terrain. n*(4)=6, so we make two families:
0,
9,11,12,13,
20,21,22,23,24,25,
32,33,34,36,
45
6,
15,17,18,19,
26,27,28,29,30,31,
38,39,40,42,
51
These concatenate in pairs as:
0,
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
Reading the second row, the set exhibiting M(5)=13 is {6,9,11,12,13}
Now for the next stage note that n*(5)=11 not 10. (There are gaps in the two longest segments at 16 & 35.)
We can then see that M(6)=24, exhibited by {11,17,20,22,23,24}.
24 is =< 26, so we have a constructive proof of the first part of the puzzle.
8 September 2010, 6:43 pmKonstantin Knop:
Tanya, its a well-known (but still open!) problem.
11 September 2010, 3:31 pmSee https://www.research.att.com/~njas/sequences/A005318 and references therein