1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Pigeonhole problem Date
Two Pigeonhole Principle Questions Jan 19, 2017
Combinatorics: Pigeonhole Principle Apr 21, 2015
Discrete Math - Pigeonhole Principle Problem Jun 4, 2012
Pigeonhole Principle problem Mar 15, 2009
Pigeonhole problem? Oct 23, 2008