Results 1 to 11 of 11
Like Tree2Thanks
  • 1 Post By romsek
  • 1 Post By Deveno

Math Help - Subsets question

  1. #1
    Junior Member
    Joined
    Oct 2012
    From
    London
    Posts
    54

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,789
    Thanks
    1147

    Re: Subsets question

    Quote Originally Posted by nubshat View Post
    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?
    Thanks from HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,418
    Thanks
    1854

    Re: Subsets question

    Quote Originally Posted by romsek View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2012
    From
    London
    Posts
    54

    Re: Subsets question

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2012
    From
    London
    Posts
    54

    Re: Subsets question

    Quote Originally Posted by romsek View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2012
    From
    London
    Posts
    54

    Re: Subsets question

    Quote Originally Posted by Deveno View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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.
    Thanks from nubshat
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2012
    From
    London
    Posts
    54

    Re: Subsets question

    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    709
    Thanks
    294

    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:

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 11th 2014, 11:44 PM
  2. Help with choosing subsets question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 1st 2012, 10:55 PM
  3. Subsets question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 11th 2010, 03:58 PM
  4. Replies: 2
    Last Post: June 22nd 2010, 08:43 PM
  5. subsets question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 6th 2010, 08:56 AM

Search Tags


/mathhelpforum @mathhelpforum