Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Pigeonhole problem set

  1. Dec 1, 2005 #1

    It was a big mistake leaving my assignment till the last minutes. Now i'm stuck on a few questions and got no where to turn to except the net.
    Please do give any hints you may have..
    Thank You!

    1. Let A subset {1,2,3,....,25} where |A| = 9. For any subset B of A let SB denote the sum of the elements in B. Prove that there are distinct subsets C, D of A such that |C|=|D|=5 and SC=SD.

    2.Let R subset Z+ X Z+ (Z+ means positive int, and X means cross product) be the relation given by the following recursive definition.
    1. (1,1) element of R; and
    2. for all (a,b) element of R, the three ordered pairs (a+1,b), (a+1,b+1), and (a+1, b+2) are also in R.
    Prove that 2a _> b for all (a,b) element of R.
    Last edited: Dec 1, 2005
  2. jcsd
  3. Dec 1, 2005 #2
    How many 5-subsets of A are there? How small and how large could their sums possibly be?
  4. Dec 1, 2005 #3
    the number of subset of A of length 5 is 126.

    there smallest sum would be 1+2+3+4+5=17 and largest 25+24+23+22+21 = 115.
    Last edited: Dec 1, 2005
  5. Dec 1, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What do you mean still clueless? You have 126 sets and only at most 98 possible sums and the thread is entitled pigeon hole principle.
  6. Dec 1, 2005 #5
    I got it now, at first i thought the question requires you to take the number of combination of the set A in account.

  7. Dec 1, 2005 #6


    User Avatar
    Science Advisor
    Homework Helper

    1+2+3+4+5 is not 17, but it doesn't make a big difference.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook