Subset-sum pigeonhole bound ($2^{|S|}>1+{\sum }_{s\in S}s⟹\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,\dots ,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,\dots ,n\}$, the largest possible $T$ is $r(2n-r+1)/2$. Thereforeis 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.