- #1
mr_coffee
- 1,629
- 1
Hello everyone I'm not sure if I'm doing this problem correctly.
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
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