Unique way to partition into two parts of equal weight - MathOverflow

Unique way to partition into two parts of equal weight

2010-04-27T16:46:30Z

A special case says it all ... Let $ w_1 < w_2 < \ldots < w_{12} $ be an increasing sequence of $12$ integers ("weights") such that the total weight $W=\sum_{k=1}^{12}w_k$ is even.

Say that $I \subseteq \lbrace 1,2, \ldots ,12 \rbrace$ is an exact subset iff the sum $\sum_{k \in I}w_k$ equals $\frac{W}{2}$. My question is : is there a sequence for which $ \lbrace 1,2,5,7,10,12 \rbrace $ is exact and is the only exact subset (up to complementation) ?

Answer by Tony Huynh for Unique way to partition into two parts of equal weight

2010-04-27T19:06:27Z

I believe the answer is yes. Consider the sequence

100, 200, 201, 202, 500, 601, 700, 701, 801, 1000, 1194, 1200.

It is easy to see that the set indexed by {1,2,5,7,10,12} is the unique exact subset (up to complementation).

Answer by damiano for Unique way to partition into two parts of equal weight

2010-04-28T11:13:57Z

Just an expansion on my comment. I will assume that exact sequences need to have half the number of indices of the whole sequence. Then a sequence is exact for some choice of weights if and only if it is exact for one weight. (This is already argued, both in my comment and in Tony Huynh's.)

The final question to be answered is when is a subsequence exact for some choice of weights. This is again very easy. A subset I of {1,...,2n} of size n obviously determines an increasing bijection $j_I$ between I and its complement. The subset I is an exact subsequence for some choice of weights if and only if the function $i \mapsto j_I(i)-i$ for $i \in I$ does not have constant sign.