1
$\begingroup$

For $S\subset\{1,2,...,117\}$ and $|S|=10$, let $A$ and $B$ be distinct subsets of $S$. $s_A$ is the sum of the elements in $A$ and $s_B$ is the sum of those in $B$. How can I prove that there must be at least one such pair for which $s_A=s_B$?

I see that the pigeonhole principle is going to come in handy here through some comparison between the least and greatest possible sums, but I'm rusty on the exact methods for this technique.

$\endgroup$
4
1
$\begingroup$

Suppose that $m$ is the smallest element of $S$. Let $t$ denote the sum of all elements of $S$. If $$t-m+1<2^{10}-1=1023\,,\text{ or equivalently }t-m\leq 1021\,,$$ then the claim follows, since there are $2^{10}-1$ nonempty subsets of $S$ whose element sums lie (inclusively) betweem $m$ and $t$. Now, prove that $t-m\leq 1021$ must hold.

Well, we have $$t-m\leq \sum\limits_{k=0}^8\,(117-k)=1017\leq 1021\,.$$ The statement is still true if we take $S\subseteq \{1,2,3,\ldots,118\}$ instead. This argument does not work any longer because $$\sum\limits_{k=0}^8\,(118-k)=1026>1021\,.$$
However, note that if $S$ has four consecutive elements, then we are done. In the case that $S$ has no four consecutive elements, we have $$t-m\leq 118+117+116+114+113+112+110+109+108=1017\leq 1021\,.$$ Therefore, the claim is still true. It is a bit more challenging to show that the statement is also true if we take $S\subseteq \{1,2,3,\ldots,119\}$. It would be interesting to find out the largest integer $k$ for which there exists $S\subseteq \{1,2,3,\ldots,k\}$ with $10$ elements such that no two nonempty subsets of $S$ have the same element sum.

$\endgroup$
1
  • $\begingroup$ Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer. $\endgroup$ – notadoctor Nov 17 '18 at 4:36
0
$\begingroup$

@Batominovski raises the interesting question of finding the maximum value of $k$. In the post

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

the following simple bound is established, where $s=|S|$, $$k<\frac{s^2-3s+2^{s+1}}{2(s-1)}.$$ This gives @Batominovski's value of $k= 117$ for $s=10$. However, the refined bound given in one of the answers to the previously mentioned post is $$k\le\frac{1}{2w}\left((w+1)(w-2)+2^u\sum_{i=v}^w{ s-u \choose i }+\sum_{i=u}^{s-u} { s \choose i } \right).$$ For $s=10,u=3,v=2,w=5$ this gives the significantly greater value of $k=182$.

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