Prove that there are at least two different 6 element subsets whose sum are equal

Question

If set $A=\{x_1,x_2,...x_{12}\}$, all of which are positive integers, and $x_i \le 150$ and $1\le i\le 12$,

Prove that there are at least two different $6$ element subsets, $S(a)$ and $S(b)$, that the sum of the elements in $S(a)$ equals the sum of the elements in $S(b)$.

Thanks for help.

Answer 1

Hint: The tags you used correctly included the tag pigeonhole-principle. Use it. Answer the question of how many six-element subsets there are and compare that number to the number of possible sums there are. What does the result of the comparison imply?

As a very loose upperbound estimate on the number of possible sums... if you add six positive numbers all of which are less than or equal to $150$... what can you say about their sum? As for counting the number of subsets possible, the term "binomial coefficient" is relevant here.

$~$

$6\times 150 = ?~~~~~~~\binom{12}{6}=?$

---

"When you do $6\times 150$, that is to find the total number of possible subsets, correct?"

No. The number of possible subsets has nothing to do with $150$. Had we been talking about a set $\{x_1,x_2,\dots,x_{12}\}$ where each $x_i$ is between $1$ and $31$, the number of possible subsets is the same as in the original example.

We have a twelve element set and we want to ask how many subsets there are... That is precisely what the binomial coefficient is used for. The number of $k$-element subsets from a set with $n$ elements is the definition of the binomial coefficient $\binom{n}{k}$. So... we have a twelve element set and we ask how many six-element subsets there are? There are $\binom{12}{6} = 924$ subsets.

Next... We are curious how many different sums of six elements might be possible. As a very crude estimate, we can say "oh, well, the sum will be smallest when all numbers are as small as possible, so the smallest sum will be at least as large as $1$ (we could have done better and noted that the elements must have been distinct, so the smallest possible sum would have been $1+2+3+4+5+6=21$, but it doesn't matter that we were relaxed here) and the largest sum will be when all numbers are as large as possible, so the largest sum will be at most as large as $150+150+150+150+150+150$ (again, we could have been stricter here and noted again that since the numbers should all have been different that the largest possible sum would have been $150+149+148+147+146+145$, but again it doesn't matter)"

So, since every sum is somewhere between $1$ and $900$, it follows that there are at most $900$ distinct sums. I must emphasize again that this is a very crude estimate. A more elaborate argument might have gotten that total down much further, perhaps down to as low as $600$ or so possible different sums given a particular collection of numbers in the set, but again... it doesn't matter since we got the number below $924$.

---

Now......... If we have more pigeons than holes, and we put each pigeon into a hole, there must be at least one hole with more than one pigeon in it.

We have our $924$ different subsets... these will be our pigeons. We will put them into our different holes which are our possible sums between $1$ and $900$ (some of which can't even be used, which we don't care), specifically following the pattern that we put our subset into the hole that corresponds to what the sum of that subset actually is...

We have more pigeons than holes... we have more subsets than possible sums... so there is at least one hole with more than one pigeon in it... so there is at least one subset sum with at least two subsets having that sum...