= Subset-sum pigeonhole bound
{title2=$2^{|S|}>1+\sum_{s\in S}s\Longrightarrow\text{two distinct subsets have equal sums}$}
Let $S$ be a finite <set> of positive <integers> and let $T=\sum_{s\in S}s$. Every <sum of a subset> is an <integer> in $\{0,\ldots,T\}$. If $2^{|S|}>T+1$, the <pigeonhole principle> forces two distinct <subsets> to have equal sums. Thus $S$ cannot be a <dissociated set>.
Cancelling their common intersection even produces two disjoint <subsets> with the same sum. Positivity means neither remaining subset can be empty. Conversely, equality of two distinct <subset sums> gives a nonzero relation with coefficients in $\{-1,0,1\}$, exactly the obstruction to being a <dissociated set>.
For an $r$-element <subset> of $\{1,\ldots,n\}$, the largest possible $T$ is $r(2n-r+1)/2$. Therefore
$$
2^r>1+\frac{r(2n-r+1)}2
$$
is a sufficient condition forcing a collision for every such <subset>. This counting bound is sufficient rather than necessary. Powers of two show how a collision-free collection can instead use the <binary representation> to make all sums different.
Back to article page
