Two different subsets of size four with the same sum

Question

There is a question that asks:

Let $A \subset \{{1,...,80\}}, |A| = 11$
Show that there are two 4-element subsets of A with the same sum of elements

The answer is:

Number of 4 element subset: $\binom{11}{4}$

Minimal sum of 4 nums: $1+2+3+4 = 10$

Maximal sum of 4 nums: $77+78+79+80 = 314$

Number of all possible sums $<= 314-10+1 = 305$

Can someone explain here what happened and give an example? Also, what is the purpose of having $+1$ when we are taking the range between the maximal and minimal sum ?

Answer 1

"Can someone explain here what happened and give an example?"

${11\choose 4}=\frac {11*10*9*8}{1*2*3*4} =330$

The smallest possible sum is $1+2+3+4=10$ and the largest possible sum is $77+78+79+80 = 314$.

If all the sums are different then you must force $330$ different values between $10$ and $314$.... which is obviously impossible.

Exactly how many different numbers are there between $10$ and $314$ including both the $10$ and $314$? And if $m > n$ how many numbers are there between $m$ and $n$ including both the $n$ and the $m$. Well, try counting them. It's irritating but the answer is $m - n + 1$. You must add $1$ to "offset the indexing". You'll have to try it a few times to convince yourself but the idea is if you "reset" $10$ to be the "new $0$" then $314$ will be the new $314 - 10$. But we reset $10$ to be the new $1$ so $314$ will be the new $314-10+1$.

Try it. Between $23$, and $29$ including $23$ and $29$ is $23,24,25,26,27,28,29$ are $7$ number. $29-23=6$ (and those are the numbers from $23$ to $29$ not including $23$ and $29-23+1 = 7$ (and those are all the numbers including $23$).

[It was hard to do in the 2nd grade when I first had to do it; and it's still hard to do.]

Answer 2

This argument uses the pigeonhole principle. The smallest possible sum of four elements in $[80]$ is $10$, because you can just add the four smallest elements. Similarly, the largest possible sum of four elements is $314$. Then every sum is going to be at least $10$ and at most $314$ so there are $305$ sums possible. But if $|A|=11$, there are ${11\choose 4}=330$ size-$4$ subsets of $A$. Then you have $330$ different subsets, and you're trying to get a different sum for each of them, but you only have $305$ sums possible. It's like trying to fit $330$ pigeons in $305$ pigeonholes- eventually, some will have to go in the same pigeonhole.

Answer 3

When counting the number of all possible sums, you know that the maximum sum is 314. There are 314 positive integers up to 314. If you remove the bottom 10 because the minimal sum is 10, there are 304 numbers that are greater than 10 but no greater than 314. However, 10 is a valid sum, so that is one greater than 304. There are 305 valid sums (including 10).

You have $\dbinom{11}{4} = 330$ 4-element subsets. Among those 4-element subsets, if you put them in a row and started assigning sums (pretend we were allowed to do that), you might wind up with the first 305 of them with different sums. But after the first 305, you still need to assign sums to the remaining 25 subsets. Each of those 25 subsets will have a sum that you have already assigned. So, at least two of the subsets will have the same sum. It does not matter if you are doing the assigning or if they are assigned by the random elements that are assigned to them. The fact remains that there are more subsets than there are possible sums, so by the Pigeonhole Principle, at least 25 pairs of subsets will have the same sum.