# Prove that an $s$ element subset of $1,2,…,n$ must have two distinct subsets with the same sum.

A number of problems on math.stackexchange have taken the form

Prove that an $$s$$ element subset of $$1,2,...,n$$ must have two distinct subsets with the same sum.

(For example discrete math about Pigeonhole Principle)

Suppose that the elements of the subset are $$a_1 Then the straightforward observations that

$$\,\,$$ there are $$2^s-1$$ non-empty subsets of the $$s$$ element subset

$$\,\,$$ the possible sums range from $$a_1$$ to at most $$a_1+\sum_{n-s+2}^n i$$

proves such a result providing $$2^s-1> \frac{(2n-s+2)(s-1)}{2}+1$$ or, equivalently, $$n<\frac{s^2-3s+2^{s+1}}{2(s-1)}.$$

This is a general result, albeit a rather weak one which can be greatly improved. I am interested in what general results can be proved for this type of problem.

EXAMPLE $$s=9$$.

The above result gives $$n<67.375$$ i.e. $$n\le67$$. The result of @CalvinLin (with $$a=2,b=7$$) improves this to $$73$$.

However, this bound can be greatly improved (one general method for doing this is given as an answer). Are there other methods which are even more effective for such a problem?

## 3 Answers

The following result due to Erdos is a personal favorite of mine.

Let $$S$$ be a finite set of positive integers such that each subset has a distinct sum. Then $$\sum_{a \in S} \frac{1}a < 2.$$

The proof can be found in this stackexchange thread.

• Yes a very nice result which I enjoyed reading- thanks for pointing it out. – S. Dolan Dec 9 '19 at 2:51

A simple way to strengthen the result is to restrict the subset of $$s$$ to size $$[a,b]$$. Common use cases are where $$a = 1, 2, b = s-1, s-2$$ to get rid of the extreme cases.

Then, we just require

$$\sum_{k=a}^b { s \choose k } > bn - \frac{b^2-b}{2} - \frac{a^2+a}{2} +1 .$$

• Thanks for this. I've posted a way of getting quite a large strengthening of the original result but I'm sure there will be much better ways that I would be interested in learning about. – S. Dolan Dec 9 '19 at 4:36

Let $$s=u+v+w$$. (We will choose $$u,v,w$$ later but a choice which seems to work well is for these parameters to be roughly $$\frac{s}{3},\frac{s}{6},\frac{s}{2}$$.)

Consider just those subsets which have from $$u$$ to $$s-u$$ elements.

Possible sums range from $$a_1+a_2+...+a_u$$ to $$a_{u+1}+a_{u+2}+...+a_s$$ and so we will have two distinct subsets with the same sum unless $$a_{u+1}+a_{u+2}+...+a_s-(a_1+a_2+...+a_u)+1>\sum_{k=u}^{s-u} { s \choose k }.$$

Now consider those subsets which include at least $$v$$ and at most $$w$$ of the elements of $$\{a_{u+1},a_{u+2}, ...,a_s\}$$.

Possible sums range from $$a_{u+1}+a_{u+2}+...+a_{u+v}$$ to $$a_1+a_2+...+a_u +a_{s-w+1}+a_{s-w+2}+...+a_s$$ and so we will have two distinct subsets with the same sum unless $$a_1+a_2+...+a_u +a_{s-w+1}+a_{s-w+2}+...+a_s-(a_{u+1}+a_{u+2}+...+a_{u+v})+1>2^u\sum_{k=v}^w{ s-u \choose k }.$$

Adding the two inequalities gives

$$2(a_{s-w+1}+a_{s-w+2}+...+a_s)+2>2^u\sum_{k=v}^w{ s-u \choose k }+\sum_{k=u}^{s-u} { s \choose k }$$ and therefore $$w(2n+1-w)+2>2^u\sum_{k=v}^w{ s-u \choose k }+\sum_{k=u}^{s-u} { s \choose k }$$

$$n>\frac{1}{2w}\left((w+1)(w-2)+2^u\sum_{k=v}^w{ s-u \choose k }+\sum_{k=u}^{s-u} { s \choose k } \right)$$ Therefore we will have two distinct subsets with the same sum if $$n\le \frac{1}{2w}\left((w+1)(w-2)+2^u\sum_{k=v}^w{ s-u \choose k }+\sum_{k=u}^{s-u} { s \choose k } \right)$$

EXAMPLE $$s=9$$.

Let $$u=3,v=2,w=4$$.

Then we will have two distinct subsets with the same sum unless $$n>103.75$$ and so there are two such subsets for $$n\le103$$.