Prove or disprove that in an 8-element subsets of $\{1,2…,30\}$ there must exist two $4$-element subsets that sum to the same number.

Question

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

Answer 1

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

Some observations about the $d_i$.

(1) Any two non-adjacent differences are unequal.

(2) Given three non-adjacent differences, none is the sum of the other two.

(3) Given two adjacent differences, the sum of these differences can replace one of the differences in observations (1) and (2). (We still require the 'combined difference' to be non-adjacent to the other differences involved.)

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.

To return to the main proof where we know that the differences $\{d_1,d_4,d_7\}=\{1,2,4\}$.

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.

Answer 2

This is NOT a proof.

I have written a code and run it, and indeed, in every $8-$plet of different numbers among $\{1,2,\ldots,30\}$, there exist (at least) two different quadruplets with the same sum.

The most interesting however is that, this holds even when $n=30$ is replaced by $n=31, ,32,\ldots,40$. In the case for $n=41$ (and apparently for every number larger than $41$), such $8-$plets do exist. In particular, for $n=41$, there exist exactly $4$ such $8-$plets: $$ 1,\,2,\,3,\,11,\, 20,\, 35,\, 38,\, 41 \\ 1,\,2,\,3,\,20,\, 29,\, 35,\, 38,\, 41 \\ 1,\,4,\,7,\,13,\, 22,\, 39,\, 40,\, 41 \\ 1,\,4,\,7,\,22,\, 31,\, 39,\, 40,\, 41 $$

Answer 3

An additional answer concerning the case $n=41$

The examples for $n=41$ given by @YiorgosS.Smyrlis contain some important pointers for the construction of such examples for other similar problems. This answer (too large for a comment) lists some points which at the very least show why these examples do not have two sets of size $4$ with equal sums. First we note that the last two sets of size $8$ in the examples are images of the first two under $k\to 42-k$.

(1) Modulo $9$ the numbers in the first two examples are both $1,2,3,2,2,8,2,5$.

(2) The totals of all eight numbers are odd and therefore if there were two subsets of size $4$ with equal sums they would have at least one number in common. We can delete any such numbers and suppose we have two subsets of size at most $3$ with no common elements.

(3) The numbers $1$ and $3$ are the only numbers not equal to $2$ modulo $3$ and so they are in neither subset or are both in the same subset. Since $1+3+41=45$ this severely limits the size of numbers in the other set and is easily seen to be impossible.

(4) When we ignore the numbers $1$ and $3$, the total of the remaining numbers is still odd and so our two subsets must each have just two elements.

(5) The numbers $35$ and $41$ are the only numbers not equal to $2$ modulo $9$ and so they are in neither subset or are both in the same subset. Together they are too large to have the same sum as any other pair of numbers and so they can be ignored. The total of the remaining numbers is still odd! So no two subsets with equal sums can exist.

Answer 4

The statement is false. Take for example a subset with 7 odd numbers and 1 even number. Then we divide this subset into two 4-element subsets. One of them will have 4 odd numbers whose sum will be an even number while the other will have 1 even number and 3 odd numbers which will add up to an odd number.

Example: 1,3,5,7,9,11,13,14 Total sum is 63 and if we were to form 2 subsets, sum in each would not be a whole number.