Proving Subset Sum Equality and Recursive Relations - Pigeonhole Problem Set

[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.

 

[Muzza]

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

 

[andytran]

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

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.

 

[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.

 

[andytran]

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.

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

 

[AKG]

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