I'm having trouble with three problems dealing with the pigeon hole principle. They are:
- 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.
- 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?
- Show that any subset of size ten of the first 24 positive integers contains two pairs of values with the same sum.
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?