Results 1 to 6 of 6

Math Help - A question about sets

  1. #1
    Member zzizi's Avatar
    Joined
    Feb 2010
    From
    London
    Posts
    83

    A question about sets

    Hi

    Can someone help me with the following problem? I'd particularly appreciate an explanation, and hints on how to prove it. - THANKS in advance

    Q) Suppose there is list of 10 integers n1,n2,n3, ...,n10, each of which lies
    between 1 and 50 inclusively.

    (part a) Let S be a nonempty subset of the list entries. Show that if I add up the
    integers in S then the total lies between 1 and 500.

    (b) Show that it is always possible to fi nd two di fferent subsets S and S' of the list
    entries such that the sum of the integers in S equals the sum of the integers
    in S'
    .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: A question about sets

    Part (a) says that the sum of k numbers, each of which is from 1 to 50 and where 1 ≤ k ≤ 10, lies between 1 and 500. This is obvious.

    For part (b) use the pigeonhole principle where pigeons are subsets and holes are numbers from 1 to 500.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member zzizi's Avatar
    Joined
    Feb 2010
    From
    London
    Posts
    83

    Re: A question about sets

    Quote Originally Posted by emakarov View Post
    Part (a) says that the sum of k numbers, each of which is from 1 to 50 and where 1 ≤ k ≤ 10, lies between 1 and 500. This is obvious.

    For part (b) use the pigeonhole principle where pigeons are subsets and holes are numbers from 1 to 500.
    Thank you
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member zzizi's Avatar
    Joined
    Feb 2010
    From
    London
    Posts
    83

    Re: A question about sets

    Quote Originally Posted by emakarov View Post
    For part (b) use the pigeonhole principle where pigeons are subsets and holes are numbers from 1 to 500.
    I came up with the following proof, could you kindly give some feedback or corrections as my proof writing ability is still a work in progress!

    Suppose you have two different subsets, S & S'. Then by the Pidgeonhole principle, since S'>S, there has to be at least two integers between 1 - 500 that are contained in both sets.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: A question about sets

    Quote Originally Posted by zzizi View Post
    Suppose you have two different subsets, S & S'. Then by the Pidgeonhole principle, since S'>S, there has to be at least two integers between 1 - 500 that are contained in both sets.
    Sorry, this won't work. First, you start the proof by considering two arbitrary subsets S and S'. Such a proof corresponds to a theorem that starts with "For all subsets S and S', ..." One prove universal claims by considering an arbitrary object. In your case, however, the claim starts with "There exist two subsets S and S' such that ..." To prove it, you either need to construct these subsets or invoke another result that proves existence, such as pigeonhole principle. Viewed from another angle, it is wrong to start a proof by considering some S and S' when your task is to prove that such subsets (with equal sums) exist!

    Second, S' > S does not make sense because S and S' are subsets, not numbers, and it is not clear what it means for one subset to be greater than another. Also, you have not shown S' > S, so you can's say "since S'>S."

    Third, it is not clear how your situation satisfies the premise of the pigeonhole principle. Finally, the problem does not ask to show that two numbers belong to both sets, rather, that there exist two sets with the same sum.

    To appy pigeonhole principle, you need to calculate how many nonempty subsets of 10 numbers (pigeons) there are. Each number is associated with its sum (hole). You can apply the principle if the number of subsets is greater than the number of possible sums.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member zzizi's Avatar
    Joined
    Feb 2010
    From
    London
    Posts
    83

    Re: A question about sets

    Thank you very much for your advice and help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about sets
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: December 3rd 2011, 11:06 AM
  2. Question about sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 16th 2010, 11:45 AM
  3. Sets question.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: February 21st 2009, 12:47 AM
  4. question on sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 28th 2008, 06:02 AM
  5. Sets question
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: May 29th 2008, 04:53 AM

Search Tags


/mathhelpforum @mathhelpforum