How can I show that for any set of $8$ distinct positive integers not exceeding $30$, there must exist two distinct $4$-elements subsets that same up to the same number?
I tried using pigeon hole principle, but i still don't get it.
There are $$\binom {8}4=70$$ four-elements subsets of an $8$-element set.
The least possible sum is $1+2+3+4=10$ and the greatest possible sum is $27+28+29+30=114$. Hence, there are $105$ sums.
I have no idea how to continue because the number of possible integer sums is greater than the number of four-element subsets.
The $4$-element subsets are not necessarily non-overlapping.
Edit:
For example, from $X=\{1,3,9,11,15,20,24,29\}$ , we can choose two different subsets $\{1,3,15,24\}$ and $\{3,9,11,20\}$ because they both sum up to $43$.
Best Answer
Let the elements of $X$ be $a_1<a_2<...<a_8$ and denote the seven successive differences by $d_i=a_{i+1}-a_i.$
Consider the subsets of size $4$ which contain either $2$ or $3$ elements of $\{a_5,a_6,a_7,a_8\}$. There are $$\begin{pmatrix}4\\1\\\end{pmatrix}\begin{pmatrix}4\\3\\\end{pmatrix}+\begin{pmatrix}4\\2\\\end{pmatrix}\begin{pmatrix}4\\2\\\end{pmatrix}=52$$ of these subsets and the possible sums of their elements range from $a_1+a_2+a_5+a_6$ to $a_4+a_6+a_7+a_8$. So, by the pigeon-hole principle, we are finished unless $$a_4+a_6+a_7+a_8-(a_1+a_2+a_5+a_6)+1\ge 52$$ $$\text {i.e.} 2(a_8-a_1)\ge51+d_1+d_4+d_7.$$ Since $a_8-a_1\le 29$ we must have $d_1+d_4+d_7\le7$. Using the observations given below, $d_1,d_4,d_7$ are all different and no two can add to the third and so $\{d_1,d_4,d_7\}=\{1,2,4\}$ and $\{a_1,a_{8}\}=\{1,30\}.$
The proofs of these are all elementary and of the same form. As an example, suppose we have $d_2+d_3=d_5+d_7$, which is a combination of (2) and (3). Then $$a_4-a_2=a_6-a_5+a_8-a_7.$$ The sets $\{a_4,a_5,a_7\}$ and $\{a_2,a_6,a_8\}$ then have the same sum and $a_1$, say, can be added to each.
Let $d$ be a difference adjacent to whichever of $\{d_1,d_4,d_7\}$ is $1$. Then, by the observations, $\{d,d+1\}\cap\{2,4,6\}$ is empty. So $d\ge7$.
Let $d$ be a difference adjacent to whichever of $\{d_1,d_4,d_7\}$ is $2$. Then, by the observations, $\{d,d+2\}\cap\{1,3,4,5\}$ is empty. So $d\ge6$.
Let $d$ be a difference adjacent to whichever of $\{d_1,d_4,d_7\}$ is $4$. Then, again by the observations, $\{d\}\cap\{1,2,3\}$ is empty. So $d\ge4$.
The sum of the differences (which is $29$) is now at least $(1+2+4)+(7+6+4)+d$, where $d$ is the 'other' difference adjacent to $d_4$. Therefore $d_4=4$ and the two differences adjacent to it (which cannot be equal) are $4$ and $5$. The differences adjacent to the differences of $1$ and $2$ are thus forced to be $7$ and $6$, respectively. Then $a_1+a_8=a_3+a_5$ and we are finished.