1. ## Subsets question

Let S be any subset of {1,2,3,...,100} of size 12. Prove that there exist at least 4 different subsets of S such that the sum of elements of each set is the same. (For example, if S = {1,4,5,21,22,31,40,42,60,73,88,99}, we have the following 4 subsets that all sum to 103: {21,22,60}, {1,4,5,22,31,40}, {4,99}, {4,5,21,73}).

I can see that this statement is true for a few base cases like S = {1,2,3,4,5,6,7,8,9,10,11,12} but I don't know how to prove that it's true for any S.

We recently learned pigeonhole principle in class so I think I'm suppose to incorporate this into my solution but I don't know how.

I don't even know where to start. Any help would be appreciated.

2. ## Re: Subsets question

Originally Posted by nubshat
Let S be any subset of {1,2,3,...,100} of size 12. Prove that there exist at least 4 different subsets of S such that the sum of elements of each set is the same. (For example, if S = {1,4,5,21,22,31,40,42,60,73,88,99}, we have the following 4 subsets that all sum to 103: {21,22,60}, {1,4,5,22,31,40}, {4,99}, {4,5,21,73}).

I can see that this statement is true for a few base cases like S = {1,2,3,4,5,6,7,8,9,10,11,12} but I don't know how to prove that it's true for any S.

We recently learned pigeonhole principle in class so I think I'm suppose to incorporate this into my solution but I don't know how.

I don't even know where to start. Any help would be appreciated.
The smallest sum of 12 terms is 78
The largest sum of 12 term is 1134

Thus there are $1134 -78+1 =1057$ different values the sum can take.

There are $\begin{pmatrix}100 \\ 12\end{pmatrix} =1050421051106700$ subsets of size 12 and this is much much larger than $4 \cdot 1057$

Can you see how to apply the piegonhole principle?

3. ## Re: Subsets question

I assume you suggest that the pigeons are all subsets consisting of 12 numbers and holes are possible sums that range from 78 to 1134. But the problem is not about different subsets of size 12 having the same sum. It's about four subsets of a given set of size 12 having the same sum.

4. ## Re: Subsets question

Originally Posted by romsek
The smallest sum of 12 terms is 78
Do you see how romsek got this? The set with the smallest 12 terms is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} and they sum to 78.

The largest sum of 12 term is 1134
And the set with the largest 12 numbers is {89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100} which sum to 1134.

(I write this because I had to think about it for a moment!)

Thus there are $1134 -78+1 =1057$ different values the sum can take.

There are $\begin{pmatrix}100 \\ 12\end{pmatrix} =1050421051106700$ subsets of size 12 and this is much much larger than $4 \cdot 1057$

Can you see how to apply the piegonhole principle?

5. ## Re: Subsets question

Originally Posted by emakarov
I assume you suggest that the pigeons are all subsets consisting of 12 numbers and holes are possible sums that range from 78 to 1134. But the problem is not about different subsets of size 12 having the same sum. It's about four subsets of a given set of size 12 having the same sum.
Yes this is correct. I'm looking to prove that at least 4 subsets out of any subset of size 12 have the same sum.

6. ## Re: Subsets question

Originally Posted by romsek
The smallest sum of 12 terms is 78
The largest sum of 12 term is 1134

Thus there are $1134 -78+1 =1057$ different values the sum can take.

There are $\begin{pmatrix}100 \\ 12\end{pmatrix} =1050421051106700$ subsets of size 12 and this is much much larger than $4 \cdot 1057$

Can you see how to apply the piegonhole principle?
If I am correct, to apply the pigeonhole principle, the pigeons would be the number of subsets of size 12 which is 1050421051106700 and the pigeonholes would be the number of possible sums of these subsets (1057). So by the pigeonhole principle, there are at least $\left \lceil \frac {1050421051106700}{1057} \right \rceil \simeq$ 9 x $10^{11}$ different subsets with the same sum, but I'm looking to prove that at least 4 subsets of any subset of size 12 have the same sum. I'm not sure how to prove this though, I tried using the same reasoning you did by trying to figure out what the smallest and largest sums are, but it's different for every subset of 12. Any ideas on how I can do this?

7. ## Re: Subsets question

We aren't summing 12 numbers, we are only summing 4 out of a set of 12. Having chosen our 12 number set, there's only going to be 450 subsets we can make. Since the smallest sum of 4 elements might be 10, and the largest 394, we need to substantially rule out "how many sums are possible" to successfully apply the pigeonhole principle (we need to cut down the 385 figure to somewhere less than 150).

For example, if our set was {1,2,3,4,5,6,95,96,97,98,99,100} can we make the sum be 350? 250? There's going to be "gaps". Let's start at the bottom:

1+2+3+4 = 10
1+2+3+5 = 11
1+2+3+6 = 12
2+3+4+5 = 14
2+3+4+6 = 15
2+4+5+6 = 16
3+4+5+6 = 18
1+2+3+95 = 101 <---big gap, here, in the first 92 "possible" sums, only 8 actually occur.

I'm too lazy to work out the details, but I suspect the "largest gap" between successive numbers of the 12 element set, controls how many sums we can leave out, and if this gap is small (like 1, or 2), the range of sums is severely curtailed.

8. ## Re: Subsets question

Originally Posted by Deveno
We aren't summing 12 numbers, we are only summing 4 out of a set of 12
It doesn't have to be of size 4, the subset could be of any size. Like in the example given: {21,22,60}, {1,4,5,22,31,40}, {4,99}, {4,5,21,73} all sum up to 103, but they're not all size 4. Does this change the proof?

9. ## Re: Subsets question

Yes! It greatly increases the number of subsets we have to choose from to 450 to 4096, in which case since we only have 385 numbers to choose as sums, after choosing 1155 subsets (which conceivably might line up nicely as 3 sets each corresponding to any particular sum-value), the 1156-th will have to make our 4th set that sums to the same number as some other 3.

10. ## Re: Subsets question

Originally Posted by Deveno
Yes! It greatly increases the number of subsets we have to choose from to 450 to 4096, in which case since we only have 385 numbers to choose as sums, after choosing 1155 subsets (which conceivably might line up nicely as 3 sets each corresponding to any particular sum-value), the 1156-th will have to make our 4th set that sums to the same number as some other 3.
I think I got it now thanks for all the help.

11. ## Re: Subsets question

Hi,
I thought you might be interested in what the wikipedia article, Pigeonhole principle - Wikipedia, the free encyclopedia, calls the generalized pigeon hole principle. Here's a short discussion together with a solution to your problem: