1
$\begingroup$

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<a_2< ...<a_s.$ 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?

$\endgroup$
1
$\begingroup$

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.

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

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 .$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – S. Dolan Dec 9 '19 at 4:36
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.