Solving Problem with Pigeonhole Principle: Sum of 10?

  • Thread starter mr_coffee
  • Start date
  • Tags
    Principle
In summary, the question is asking if, given a set of 5 integers chosen from {1,2,3,4,5,6,7,8,9}, there must be two integers whose sum is 10. This is not necessarily true, as shown in the example where 4 integers are chosen from {1,2,3,4,5,6,7,8} and there is no pair with a sum of 9. This is because the pigeonhole principle does not apply in this case, as the number of integers chosen is not greater than the number of possible sums.
  • #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
 
Physics news on Phys.org
  • #2
The argument the book is using does not work, as you have figured out. What you need to do is construct a counterexample.
 
  • #3
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.
 
  • #4
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.
 
Last edited:
  • #5
mr_coffee said:
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.



Sane said:
It's wrong because 5 is not paired up.
Why would you think that?
 
  • #6
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?
 
  • #7
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).
 
Last edited:
  • #8
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.
 
  • #9
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.
 
  • #10
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.
 
  • #11
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.
 
  • #12
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.
 
  • #13
Let me know how it went. Was that what your professor was expecting for an answer? I'm curious to know.
 

FAQ: Solving Problem with Pigeonhole Principle: Sum of 10?

1. How does the pigeonhole principle apply to solving problems involving the sum of 10?

The pigeonhole principle states that if there are more items than there are container slots to hold them, at least one container must hold more than one item. In the context of the sum of 10, this means that if we have more than 10 numbers, at least two of them must add up to 10. This is a useful concept for solving problems involving the sum of 10, as it allows us to narrow down our options and find a solution more efficiently.

2. Can the pigeonhole principle be used to solve problems with a different sum, such as 15 or 20?

Yes, the pigeonhole principle can be applied to any problem involving a specific sum. The key is to determine the number of items (pigeonholes) and the number of containers (slots) in a way that allows for at least one container to hold more than one item. For example, if we have 15 numbers, we could use 10 containers and find that at least two numbers must add up to 15.

3. Are there any limitations to using the pigeonhole principle for problem-solving?

While the pigeonhole principle is a useful concept for many problem-solving scenarios, it does have its limitations. It is important to note that the principle only guarantees the existence of a solution; it does not provide a method for finding the solution. In some cases, it may also not be the most efficient approach for finding a solution.

4. How can the pigeonhole principle be used to solve real-life problems?

The pigeonhole principle can be applied to real-life problems in a variety of ways. For example, it can be used to optimize resources in industries such as transportation and manufacturing, where there may be limited space or capacity. It can also be used in scheduling and project management to ensure that deadlines are met and resources are used efficiently.

5. Are there any other strategies or principles that can be used in conjunction with the pigeonhole principle for problem-solving?

Yes, the pigeonhole principle can be combined with other problem-solving strategies and principles, such as logical reasoning, trial and error, and mathematical equations. It is often used in combination with other methods to find the most efficient and effective solution to a problem.

Similar threads

Back
Top