Homework Help: Pigeonhole problem set

1. Dec 1, 2005

andytran

Hi,

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. Dec 1, 2005

Muzza

How many 5-subsets of A are there? How small and how large could their sums possibly be?

3. Dec 1, 2005

andytran

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
4. Dec 1, 2005

matt grime

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.

5. Dec 1, 2005

andytran

I got it now, at first i thought the question requires you to take the number of combination of the set A in account.

thx

6. Dec 1, 2005

AKG

1+2+3+4+5 is not 17, but it doesn't make a big difference.