Solving Pidgeonhole Principle with Induction – A Helpful Guide

[lovemake1]

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.

 

[Mark44]

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?

 

[lovemake1]

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.

 

[Mark44]

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.

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.