1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Best possible result of Pigeonhole Principle

  1. May 30, 2012 #1
    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. jcsd
  3. May 30, 2012 #2
    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?
  4. May 30, 2012 #3
    Well, floor function always gives an integer, so this case doesn't show up. :wink:

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

    [tex]\left \lfloor (m-1) \right \rfloor \neq m-1 [/tex]

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

    [tex]\left \lfloor \frac{(m-1)}{n} \right \rfloor + 1 \geq \frac{(m-1)}{n}[/tex]
  5. May 30, 2012 #4
    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)
  6. May 30, 2012 #5
    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.
  7. May 30, 2012 #6
    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
  8. May 30, 2012 #7
    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 [itex]\left \lceil \frac{n}{k} \right \rceil[/itex] pigeons, and atleast one pigeonhole containing not more than [itex]\left \lfloor \frac{n}{k} \right \rfloor[/itex] 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. o:)
  9. May 30, 2012 #8
    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? :cool:
  10. May 31, 2012 #9
    Well, yes, it is possible. To prove it is possible, all you need to do is show

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

    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! :biggrin:
  11. May 31, 2012 #10
    heheh, great :biggrin: thanks for your help :]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook