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!

Advanced Pigeonhole principle

  1. Jul 5, 2010 #1
    Hi all,
    I have a question and hope to solve.
    problem terms :
    1- there are K holes.
    2- there are N group of Pigeon.
    3- there are M Pigeon in any Pigeon group.
    4- each group of Pigeon can chose Z hole so that K >= Z >= M.
    5- we don`t know which hole selected by a Pigeon only we know M Pigeon in group select Z hole.
    6- the capacity of each hole is exact one Pigeon.
    How we can determine last Pigeon group can not enter to the selected holes (because the selected hole are full)?
  2. jcsd
  3. Jul 5, 2010 #2


    User Avatar
    Science Advisor

    The explanation is a bit unclear, but this is how I interpreted it:

    There are K pigeonholes, N groups and M pigeons in each group. Z is a number between M and N, and is the number of holes each group occupies. The question is to determine if all pigeons can fit in the holes or not.

    If that is so, then obviously, since each group occupies Z holes, and they all fit in, M*Z must be less than or equal to N. If M*Z is larger than N, the last group will not be able to choose Z holes. I can hardly see how this is a more complex situation than the classical pigeonhole principle, so I assume my interpretation is incorrect. Besides, what is the relevance of 6- if every group need Z holes each.
  4. Jul 5, 2010 #3
    Jarle, read more carefully. Z is number between K and M or can be equal (term 4) no between N and M
    this question is a bit hard and need more think
  5. Jul 6, 2010 #4


    User Avatar
    Science Advisor

    Yes, I meant between or equal to K or M. I confused a few variables. It should be (N/M)*Z, not M*Z. And this must be compared to K, not N. Explain how it matters how man pigeons that fit into a hole when all you know is that a group of M pigeons occupies Z holes?
  6. Jul 6, 2010 #5
    I am sorry for my English
    Let me for an example :
    there is 4 holes, first pigeons group arrive and this group have 2 pigeons, pigeons select first and second holes now another group is coming and in the new group there is only one pigeon that select first hole, there are totally 3 pigeons and 4 holes and with your formula all must be true but in fact pigeons can not enter to holes because first hole selected by 2 pigeons now lets change the situation, first pigeons*group select first, second and third holes and now we have the answer because 2 pigeons in the first group can enter to holes 2 and 3 and pigeon in the second group can enter to hole 2. this problem will be solved by a recursive routine but I need a formula
    this forum disappoint me I think it have many mathematician and I expect more reply
  7. Jul 6, 2010 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You can't expect a lot of replies when it's hard to figure out what you're asking. So the pigeons select Z holes that they are allowed to go into, and the requirement is that M of them are empty?

    This is going to depend heavily on which Z holes the pigeons select... you can't answer it based only on M,N,Z and K.

    As an example with two pigeons and two holes: M=1,Z=1, K=2, N=2:

    First pigeon selects first hole. Second pigeon selects first hole. They fail to fit

    First pigeon selects first hole. Second pigeon selects second hole. They fit.

    What kind of criterion do you have for which holes the pigeons are allowed to select?
  8. Jul 6, 2010 #7
    please think more higher, it is completely clear that holes capacity is exact one pigeon so when the first pigeon select a hole other pigeons of group must select another holes.
    in the older post there is an example but more explain : we know any group of pigeons select Z holes from K holes and K >= Z >= M but we don`t know which hole are selected by pigeons so we can suppose if next group select one hole of previous group holes, pigeons of the previous group did not enter to this specific hole (if K > M and no K = M). this condition may be check every time that new group arrive for all older groups
  9. Aug 11, 2011 #8
    It's not easy to understand the situation after the first reading..the pigeons select Z holes that they are allowed to go into, and the requirement is that M of them are empty..how can we predict? they are unpredictable))
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Advanced Pigeonhole principle
  1. Advanced calculus (Replies: 3)

  2. Advanced algebra (Replies: 7)