- #1

mr_coffee

- 1,629

- 1

The question is, Let T = {1,2,3,4,5,6,7,8,9}. Suppose 5 integers are chosen from T. Must there be two integers whose sum is 10?

Well the book did a problem similar to this, in which the problem was the following:

Let A = {1,2,3,4,5,6,7,8}.

If give integers are selected from A, must at least 1 pair of integers have a sum of 9?

Answer:

Yes. Partition the set A into the following four disjoint subsets:

{1,8}, {2,7}, {3,6}, {4,5}

Observe that each of the integers in A occurs in exactly one of the four subsets and that the sum of the integers in each subset is 9. Thus if 5 integers from A are chosen, then by the pigeonhole principle, two must be from the same subset. It follows that the sum of thsee two integers is 9.

Now If i apply the same concept to my problem I believe it proves that its false. Because if you parititon my numbers you get:

{1,9}, {2, 8}, {3,7}, {4,6}, {5}

Your choosing 5 integers, 4 of them are going to turn out as a sum of 10, but the 5th one isn't, it will be a 5. If I'm understanding this correctly.

The Pigeonhole princple says the following:

A function from one finite set to a smaller finite set cannot be one-to one: There must be at least two elements in the domain that have the same image in the co-domain.

hm...but if i have 5 paritions, and 5 integers, that means this function is goign to be 1 to 1, because for every integer I choose, i can choose exactly 1 parition, like a1 = {1,9}, a2 = {2,8}, a3 = {3,7}, a4 = {4,6} a5 = {5}

Or is this wrong becuase {5} is not paired up?

Any advice would be great in clearing this up!

thanks