# Homework Help: Best possible result of Pigeonhole Principle

1. May 30, 2012

### Solarmew

1. The problem statement, all variables and given/known data
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.

2. Relevant equations

3. 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?

2. May 30, 2012

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

3. May 30, 2012

### Infinitum

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

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}$$

4. May 30, 2012

### 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)

5. May 30, 2012

### Infinitum

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.

6. May 30, 2012

### Solarmew

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

7. May 30, 2012

### Infinitum

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.

8. May 30, 2012

### Solarmew

yeah, this book isn't the greatest :grumpy:
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 ... :uhh: ... so you think that'll cut it, or is there any way to fancy it up?

9. May 31, 2012

### Infinitum

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!

10. May 31, 2012

### Solarmew

heheh, great thanks for your help :]