0
$\begingroup$

How many subsets $I$ of $S:=\{1,\cdots,n\}$ exist such that

$\sum_{i \in I} x_i \neq \sum_{j \in S-I} x_j$

for all $0 < x_1 < \cdots < x_n$?

Let $b_n$ be this number. Then we are interested in the number $a_n := 2^n - b_n$.

Is there any reference which considers this situation, where maybe I can read things up in this situation?

Any help is appreciated.

For $n = 3$ consider:

0 () ['x2', 'x3', 'x1']

1 ('x1',) ['x2', 'x3']

2 ('x2',) ['x3', 'x1']

3 ('x3',) ['x2', 'x1']

4 ('x1', 'x2') ['x3']

5 ('x1', 'x3') ['x2']

6 ('x2', 'x3') ['x1']

7 ('x1', 'x2', 'x3') []

Then only 3 and 4 are valid, (for instance 5 is not valid since $x_1+x_3>x_2$) so we get $a_3$ = 2.

$\endgroup$
7
  • $\begingroup$ You mean that this inequality holds for all sequences $0<x_1<\dots <x_n$? $\endgroup$ Commented Jul 16, 2016 at 14:17
  • $\begingroup$ Yes, thats what I mean. $\endgroup$
    – user6671
    Commented Jul 16, 2016 at 14:18
  • 1
    $\begingroup$ Do you require proper subsets? Also, your sequence seems wrong. For $n = 3$ you have $\{1\}, \{2\}, \{1,3\}, \{2,3\}$. For $n = 4$ I get at least 10: $\{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}$ and their complements. For $n = 5$ you should have $$ \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\} $$ and their complements. So it seems you inserted an extra $2$ in your sequence? $\endgroup$ Commented Jul 16, 2016 at 14:42
  • 1
    $\begingroup$ My previous comment lists $b_n$ if they are proper subsets. If they are not then you add 2. They don't seem to agree with your $a_n$. (In particular, how is $a_2 = 2$ when $a_1 = 0$? If you count only proper subsets, $b_1 = 0$ and $b_2 = 2$. But if you count all subsets, $b_1 = 2$ and $b_2 = 4$.) Can you do a few examples to show how you computed "manually" those numbers? $\endgroup$ Commented Jul 16, 2016 at 14:49
  • 1
    $\begingroup$ Though the question is not well formulated, it is, after all, quite reasonable. $\endgroup$ Commented Jul 16, 2016 at 15:27

1 Answer 1

9
$\begingroup$

I claim that $b_n=2\binom{n}{[n/2]}$ for $n\geqslant 1$. If $\sum_{i\in I} x_i\ne \sum_{i\notin I} x_i$, then either the sign is always '$>$' or always '$<$' (since the set of strictly increasing sequences is convex and therefore connected.) So, we need to prove that there are exactly $\binom{n}{[n/2]}$ subsets $I$ for which $\sum_{i\in I} x_i>\sum_{i\notin I} x_i$ whenever $0<x_1<\dots<x_n$. For any set $I$ construct a lattice path as follows: it start from the origin, and on $i$-th step goes from $(a,b)$ to $(a+1,b)$ if $n+1-i\in I$ and goes to $(a,b+1)$ otherwise. Note that condition $\sum_{i\in I} x_i>\sum_{i\notin I} x_i$ holds if and only if our path lies in the region $\{(a,b):a\geqslant b\}$, i.e., if it does not intersect the line $\ell:\{b=a+1\}$. In other words, out of $k$ greatest values of an index $i$ at least half should belong to $I$. For calculating the number $N$ of such paths do the standard trick. $N$ equals the number of all paths of length $n$ to the possible endpoints $(n,0),(n-1,1),\dots,(\lceil n/2\rceil,\lfloor n/2\rfloor)$ minus the number of paths from the origin to these endpoints, which intersect $\ell$. For any considered endpoint $P(a,b)$, the number of paths from the origin to $(a,b)$ which intersect $\ell$ equals the number of paths from the origin to the point $P^*$ symmetric to $P$ in $\ell$ (bijection is the symmetrizing the part of the path after the last point of $\ell$ on it). So, we sum up the number of paths to $(k,n-k)$ with $n\geqslant k\geqslant n/2$ and subtract the number of paths to points $(n-k-1,k+1)$, $n\geqslant k\geqslant n/2$. Since the number of paths to $(n-k-1,k+1)$ equals the number of paths to $(k+1,n-k-1)$, we see that everything except paths to $(\lceil n/2\rceil,\lfloor n/2\rfloor)$ cancel, that proves our claim.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer. I will need some time to go through your proof! Thanks again!!! $\endgroup$
    – user6671
    Commented Jul 16, 2016 at 15:28

You must log in to answer this question.