Proving subset sums with the pigeon hole principle

Question

I'm having trouble with three problems dealing with the pigeon hole principle. They are:

1. Prove that any subset of size ten of the first 40 positive integers must have two different subsets of size three with the same sum.
2. What is the largest value of m for which it is true that any subset of size ten of the first m positive integers must have two different subsets of size three with the same sum?
3. Show that any subset of size ten of the first 24 positive integers contains two pairs of values with the same sum.

My attempts:

For problem (1) I essentially tried to brute force it with a C++ program. I got some interesting results (if they turn out to be right). My program returned that there existed 9,880 possible sums for the first 40 positive integers (assuming size three) (e.g.) a+b+c and that there was only 112 unique sums. Therefore, by the pigeon hole principle there must be a sum which repeats.

Problem (2) I honestly did not know how to deal with this problem. However, when I first read the question I did not think that m had an upper bound (i.e. it works for every m). But, now I'm not so sure and do not know where to start.

Problem (3) For this problem I also tried a brute force method and got a total of 176513040 possible sums with 47 being unique. However, I don't think this is right. Nor do I think that my answer to problem 1 is right.

Can anyone offer some advice?

Thank you!

Answer 1

It's hard to think about questions such as these because there's lots of quantifiers. So here's a special case of question 1:

Show that the set $S = \{1, 3, 4, 7, 9, 10, 11, 13, 16, 19\}$ must have two three-element subsets with the same sum.

Now that the question is this specific, we can of course solve the problem by inspection: $\{1,10,19\}$ and $\{9,10,11\}$ have the same sum, for example. But we also want to generalize this to other sets eventually.

So here's an argument that generalizes: there are $\binom{10}{3} = \frac{10\cdot 9\cdot 8}{6} = 120$ different three-element subsets of $S$. The smallest possible sum is $1+3+4 = 8$ and the largest possible sum is $13+16+19=48$, so all three-element subsets have a sum between $8$ and $48$. Since this leaves only $41$ possibilities for the sum, and there's $120$ three-element subsets, some two of those subsets must have the same sum.

So now, to find answers to your questions, we need to:

1. Show that the same argument holds when $S$ is any ten-element subset of $\{1, 2, 3, \dots, 40\}$. We don't know what the smallest and largest possible sum are in $S$ without knowing $S$; but how small and how big can they get?
2. Once you've figured out the answer to question 1, for what values of $m$ in place of $40$ would the same argument work? (How does the range of possible sums depend on the value of $40$?)
3. Can you make the same argument work with two-element subsets instead of three-element subsets?

Answer 2

What you need to do is to correctly count the possibilities.

For problem (1) you need to know how many subsets of size three there is of a set of size 10. To get a subset you will pick three different elements, the first element can be choosen in 10 ways, next in 9 ways (since the first picked element can't be picked again) and finally the third in 8 different ways. This gives $10\times 9\times 8$ possibilities, but it doesn't matter which order you pick the same elements, given a pick there's $6=3\times 2\times 1$ (which is seen in similar way) ways to reorder that which brings us to $120={10\times9\times8\over3\times2\times1}$. Then you know that the certainly can't be larger than $120=3\times40$ and no less than $3=3\times1$ (yes we can tighten somewhat, but we need not).

Note well that the error you did in your attempt on the first question was that you tried to pick subsets of the entire set, but the question asked about a subset of size ten of that set. Your number is however correct (check with formula below), but be careful about reading the question.

The other is solved in similar way. The formula you need is that the number of subsets of size $k$ out of a set of size $n$ is $${n!\over k!(n-k)!} = {n\times(n-1)\times\dots\times(n-k+1)\over k\times(k-1)\times\cdots\times1}$$

The notation $n!$ means the product of all positive integers up to including $n$. We can see that this is the number of ways we can reorder a collection of size $n$. We see this by the reasoning above, to arrange the collection we sequentially picks $n$ elements, first we can pick $n$, then there's $n-1$ left so we can pick $n-1$ and so on until we only have one left. One can interpret the formula as a count of the number of ways we can rearrange the whole set (of size $n$), the subset (of size $k$) and the rest of the original set (of size $n-k$).