Best possible result of Pigeonhole Principle

[Solarmew]

Homework Statement

Show that the PHP is the best possible result. Meaning show that m pigeons can occupy n hole in such a way that no hole contains more than floor[(m-1)/n] + 1 pigeons.

Homework Equations

The Attempt at a Solution

well, first i thought I would break this up into cases.
1. floor[(m-1)/n] is an integer
then n * [(m-1)/n] + 1 = m - 1 + 1 = m

2. floor[(m-1)/n] is not an integer. (m-1)/n = floor[(m-1)/n] + Ɛ
then I guess we could break this up into another 3 cases
i. 0 < Ɛ < 1/2
ii. Ɛ = 1/2
iii. 1/2 < Ɛ < 1

but i don't think this is the right approach :\...

i'm actually not entirely sure what I'm supposed to do with this one ...
maybe show that when m divides n, the number of pigeons in every hole is no more than ceiling(m/n) ... that's not too hard, just do n*ceil(m/n) = m pigeons, just as expected
but I'm not sure what to do if m doesn't divide n ... any hints?

 

[Solarmew]

can i maybe say that if m divides n, then m/n is an integer, so there are m/n = ceiling(m/n) pigeons in every hole as expected

if m doesn't divide n, then there are floor(m/n) pigeons in every hole and since
m - n*floor(m/n) < n, the remaining pigeons can be distributed into the holes, no more than one in each, so that no hole will have more than floor(m/n)+1=ceiling(m/n) as expected?

 

[Infinitum]

2. floor[(m-1)/n] is not an integer. (m-1)/n = floor[(m-1)/n] + Ɛ
then I guess we could break this up into another 3 cases
i. 0 < Ɛ < 1/2
ii. Ɛ = 1/2
iii. 1/2 < Ɛ < 1

Well, floor function always gives an integer, so this case doesn't show up.

1. floor[(m-1)/n] is an integer
then n * [(m-1)/n] + 1 = m - 1 + 1 = m

I'm unsure how you got this step, for almost all m,

\left \lfloor (m-1) \right \rfloor \neq m-1

You can try proving this by contradiction. Use the fact that

\left \lfloor \frac{(m-1)}{n} \right \rfloor + 1 \geq \frac{(m-1)}{n}

 

[Solarmew]

what about my second post? it seems like that might be a step in the right direction maybe? :shy:
i'm actually trying to use the ceiling function because it's less messy ... not sure why the book wrote it out that way when floor((m-1)/n)+1 = ceiling(m/n)

 

[Infinitum]

I re-read the problem,

Show that the PHP is the best possible result. Meaning show that m pigeons can occupy n hole in such a way that no hole contains more than floor[(m-1)/n] + 1 pigeons.

The question should be framed in a way that, there exists at least one hole containing not more than floor[(m-1)/n] + 1 pigeons. The way it is now, the maximum number of pigeons in one hole can be m-n+1, by putting 1 pigeon each in n holes, and all the rest in one hole, and this number for many cases, is wee more than floor[(m-1)/n] + 1.

if m doesn't divide n, then there are floor(m/n) pigeons in every hole and since
m - n*floor(m/n) < n, the remaining pigeons can be distributed into the holes, no more than one in each, so that no hole will have more than floor(m/n)+1=ceiling(m/n) as expected?

I am a bit confused what you did here.

 

[Solarmew]

I re-read the problem,
The question should be framed in a way that, there exists at least one hole containing not more than floor[(m-1)/n] + 1 pigeons. The way it is now, the maximum number of pigeons in one hole can be m-n+1, by putting 1 pigeon each in n holes, and all the rest in one hole, and this number for many cases, is wee more than floor[(m-1)/n] + 1.
I am a bit confused what you did here.

unfortunately that is how it's stated in the book :\ it says "Show that Theorem 50 (PHP) is the best possible result" and so on what i said in the first post.

As far as m - n*floor(m/n) < n
so if m is not divisible by n, then n*floor(m/n) will give the biggest multiple of n less than m, then the remainder will be less than n, otherwise we have not found the biggest multiple.
Since the remainder is less than n, it means each left over pigeon can go in some hole, so the total for some holes will increase from the floor(m/n) to ceiling(m/n) which is what the problem is asking us to prove - each hole will contain no more than ceiling(m/n)

i know, this is a pretty convoluted assbackwards way of doing it XD but this is the best i can do dammit! XD

 

[Infinitum]

unfortunately that is how it's stated in the book :\ it says "Show that Theorem 50 (PHP) is the best possible result" and so on what i said in the first post.

This is what strong form of PHP actually says,
When n pigeons are put into k pigeonholes, there exists at least 1 pigeonhole containing not less than \left \lceil \frac{n}{k} \right \rceil pigeons, and atleast one pigeonhole containing not more than \left \lfloor \frac{n}{k} \right \rfloor pigeons. I believe there is a mistake in that book. Taking the example of m=8, and n=5, and considering holes numbered as a, b, c, d, e. You can put 4 pigeons in a, and one each in the rest. That gives max no. of pigeons in one hole = 4. From the given problem it comes out floor[(8-1)/5] + 1 = 2, and that's obviously wrong.

Your above logic holds for the rephrased question, its a bit non-mathematical and not-so-well-stated, but acceptable, I think.

 

[Solarmew]

yeah, this book isn't the greatest
the way i interpreted it, is that while you can stuff all the pigeons in one hole, IT IS POSSIBLE to distribute pigeons in such a way that each hole has no more than ceiling(m/n) ... and that's what it wants proof of ... ... so you think that'll cut it, or is there any way to fancy it up?

 

[Infinitum]

yeah, this book isn't the greatest
the way i interpreted it, is that while you can stuff all the pigeons in one hole, IT IS POSSIBLE to distribute pigeons in such a way that each hole has no more than ceiling(m/n) ... and that's what it wants proof of ... ... so you think that'll cut it, or is there any way to fancy it up?

Well, yes, it is possible. To prove it is possible, all you need to do is show

n(\left \lfloor \frac{(m-1)}{n} \right \rfloor + 1) \geqslant m

Because if the maximum number of pigeons per box was taken, then they would have to equal to or more than their total number.

It looks mathematical, too!

 

[Solarmew]

heheh, great thanks for your help :]