Solving Problem with Pigeonhole Principle: Sum of 10?

[mr_coffee]

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

 

[0rthodontist]

The argument the book is using does not work, as you have figured out. What you need to do is construct a counterexample.

 

[mr_coffee]

Thanks ortho,

could my counter example be
if you have 9 integers, 1-9, and only 5 holes, that means you can only pair up, 4 holes in which the two integers sums will be 10, such as: {1,9}, {2,8}, {3,7}, {4,6}, but your still left with 5, in which no integer will pair up with it because they are already used in the upper pigeon holes.

That kinda sounds too abstract,

acutally if u pair up the integes, you will be left with 1 empty hole, and 1 hole only having 1 integer in it.

 

[Sane]

It's wrong because 5 is not paired up. All that means is your example does not support the pigeonhole principle. If you're familiar with what the pigeonhole principle is used for, you'll see why this quality is important to realize, and what that means about the set of values.

 

[Hurkyl]

could my counter example be

No; that looks nothing like a counter example. A counter example for

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?​

is a selection of 5 integers from T, no two of which sum to 10.

It's wrong because 5 is not paired up.

Why would you think that?

 

[mr_coffee]

Thanks for the responces,

Hurkyl,
So your counter example was just the opposite of what the claim was or did somthing get cut off, you went from the question to "...is a selection"

I kinda think Sane is right becuase the pigeon hole princpal says;

If n pigeons fly into m pigeonholes and n > m, then at least one hole must contain two or more pigeons.

So n (pigeons) is the set {1,2,3,4,5,6,7,8,9} and m is the 5 integers chosen (holes), n > m, but it violates the statement that "then at least one hole must contain 2 or more pigeons" Becuase 1 hole is left empty and the other hole is left unparied with another integer, because all the integers have already beeen used up. Could this be used to show its a false claim?

 

[Sane]

Yes, mr coffee explained for me why his example does not sufficiently meet the pigeonhole principle. You are attempting to solve for all sets that meet a certain condition, where the allocated room is five complete sets. Only four sets match the conditions, and therefore there is a hole that is not being put to use. Although one hole does not seem like a significant waste, this algorithm being implemented in a scope one million times larger will result in millions of wasted holes (or equivilently, millions of unused dynamically allocated memory blocks).

 

[mr_coffee]

Sane,

It says, Must there be two integers whose sum is 10?
Now because it fails this condition of the pigeon hole princ. is that enough to say, no, there doesn't have to be 2 integers whose sum is 10.

 

[Sane]

Your algorithm can't successfully determine the correct number of holes, because it is not supplied with sufficiently unified data to calculate it correctly. Therefore, in that respect it does not meet the pigeonhole principle in most circumstances. However, it all depends on what your definition of meeting the principle relies upon, and the unity of your data set in relation to a set that does work.

What is this for by the way? I guess this could depend on the context as well, in respect to what the goal to be accomplished is.

 

[mr_coffee]

Sane,

Its for a descrete math problem, The problem just says:
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? Why?

The book had an example where the answer did not fit the p-hole case, it was the following:

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

If four integers are selected from A, must at least one piar of integers have a sum of 9?

The answer is no. This is a case where the pigeonhole principle does not apply; the number of pigeons is not larger than the number of pigeonholes. FOr instance, if you selected the numbers 1,2,3,4, then since the largest sum of any two of these numbers is 7, no two of hem add up to 9.

Hm...So for my case I could also say the same thing correct?

In my case, I need to select 5 numbers, from {1,2,3,4,5,6,7,8,9}, if i select the numbers 1,2,3,4,5 then since the largest sum of any two of these number is 9, no two of them add up to 10.

 

[Sane]

Oh, I see... so we're not talking about optimizing the pigeonhole, we're just talking about finding at least a certain amount of holes that will be filled. So yes, to disprove the question, take a counter-example, as Hurkyl earlier suggested. How you would write this out as your teacher expects the solution, I'm not quite sure. It's probably just as simple as a counter example.

 

[mr_coffee]

thanks guys! sorry for the confusion,
This would work fine i think!

In my case, I need to select 5 numbers, from {1,2,3,4,5,6,7,8,9}, if i select the numbers 1,2,3,4,5 then since the largest sum of any two of these number is 9, no two of them add up to 10.

 

[Sane]

Let me know how it went. Was that what your professor was expecting for an answer? I'm curious to know.