Solving Pidgeonhole Principle with Induction – A Helpful Guide

In summary, the Pidgeonhole Principle states that if you have kn+1 objects and n pigeonholes, there will always be at least one pigeonhole with k+1 objects in it, no matter how the objects are distributed. This can be logically proven by considering the distribution of objects in each pigeonhole and the remaining object.
  • #1
lovemake1
149
1

Homework Statement


Pidgeonhole principle: If kn+1 objects are placed in n pigeonholes, then some pigeohoe contains atleast k+1 objects.



Homework Equations





The Attempt at a Solution



I completely understand this problem but I am not sure where or how to start.
If there are n = 5 holes and we set k to be 2.
then there are 11 objects in total and according to the principle, some pidgeonhole would occupy (2)+1 = 3 objects in one hole.


Do we use induction?

Assume k, n is natural:
Assume kn + 1 is nautral:
Then kn+1 > k + 1
Then kn > k
n > 1 ?
...

Can someone please give me a hint?
Helps appreciated.
 
Physics news on Phys.org
  • #2
I don't think induction is the way to go for this problem.

Suppose you had kn objects and n pigeonholes (note spelling). One way to distribute the n objects would be to divide them equally among all the pigeonholes, with k objects in each hole. Of course, if you put more an extra object in one pigeonhole, another pigeonhole would end up with (k - 1) objects.

Now, if you have kn + 1 objects, and n pigeonholes, you can again distribute kn of the objects equally, with k of them in each pigeonhole, and you'll have one left over. Can you show that no matter how you distribute the objects, there has to be at least one pigeonhole with k + 1 objects in it?
 
  • #3
Is there some mathematical way of showing that no matter how we distribute it, there's always one pigeonhole with k + 1 objects in it ?
I can represent this with an example, kn + 1 / n gives the number of objects to be placed in each hole to evenly distribute. But the remainder of 1 gives us one item left to be placed in some hole in which it will occupy k + 1.
 
  • #4
lovemake1 said:
Is there some mathematical way of showing that no matter how we distribute it, there's always one pigeonhole with k + 1 objects in it ?
Yes. The way I have in mind is a logical argument.
lovemake1 said:
I can represent this with an example, kn + 1 / n gives the number of objects to be placed in each hole to evenly distribute. But the remainder of 1 gives us one item left to be placed in some hole in which it will occupy k + 1.
First, kn + 1/n is the same as kn + (1/n). I know you meant (kn + 1)/n, so use parentheses so that other people understand what you really mean.

Second, what you show above isn't an example. What you had in your 1st post with n = 5 and k = 2 - that's an example.

If you have n pigeonholes and kn + 1 objects, and you put k objects in each pigeonhole, you have one object left over. Is there any way of distributing the kn + 1 objects so that no pigeonhole has more than k objects?

That's what you need to argue.
 
  • #5


Hello! I would suggest approaching this problem using mathematical induction. This technique involves proving that a statement is true for a base case, and then showing that if the statement is true for a certain value, it is also true for the next value. In this case, you can start by proving the statement for n = 1, where there is only one pigeonhole and k = 1. Then, you can assume that the statement is true for n = m, where m is any positive integer. From there, you can use the Pidgeonhole principle to show that the statement is also true for n = m+1. This will prove the statement for all natural numbers, as desired. I hope this helps!
 

1. What is Pidgeonhole Logic proof?

Pidgeonhole Logic proof is a mathematical method used to prove the existence of a solution to a problem by showing that there must be at least one instance where the solution is possible based on the number of available options and constraints.

2. How does Pidgeonhole Logic proof work?

In Pidgeonhole Logic proof, the problem is first divided into smaller sub-problems or "pigeonholes" which represent the possible solutions. The number of pigeonholes is then compared to the number of available options and constraints to determine if there must be at least one instance where a solution is possible.

3. What types of problems can be solved using Pidgeonhole Logic proof?

Pidgeonhole Logic proof can be applied to a wide range of mathematical and logical problems, including combinatorics, number theory, and graph theory. It is particularly useful in problems involving permutations, combinations, and existence proofs.

4. What are the limitations of Pidgeonhole Logic proof?

Pidgeonhole Logic proof can only prove the existence of a solution, but it does not provide a method for finding the solution. It also relies on the assumption that the options and constraints are well-defined and accurate, which may not always be the case.

5. Can Pidgeonhole Logic proof be used to solve real-world problems?

Yes, Pidgeonhole Logic proof can be applied to real-world problems that can be translated into mathematical or logical statements. It has been used in various fields such as computer science, engineering, and economics to prove the existence of optimal solutions.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
11
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
Replies
13
Views
1K
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
738
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
983
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top