Results 1 to 6 of 6

Math Help - Pigeonhole theorem problem

  1. #1
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    Pigeonhole theorem problem

    Problem #1:
    Suppose N objects are distributed between B boxes in such a way that no box is empty. How many objects must we choose in order to be sure that we have chosen the entire contents of at least one box?


    My strategy was to find out the maximum number of contents one box can have, say M.
    Then if I choose M objects I can satisfy the given task.
    But I'm stuck on finding this maximum number.
    I know that by using the pigeonhole principle, I can say at least one box has at most or at least some number of contents.
    How can I say all boxes have at most some number of contents?


    Problem #2:
    There are twelve signs of the Western Zodiac. Suppose there are 145 people in a room. Show that there must be 13 people who share the same sign of the Western Zodiac.


    I'm confused about the wording. Is the problem different from "show that there must be at least 13 people who share a zodiac"?
    If so, I need hints to find how to narrow down from saying "at least 13 people share one zodiac" to "exactly 13 people share one zodiac".
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2012
    From
    Ireland
    Posts
    600
    Thanks
    165

    Re: Pigeonhole theorem problem

    in #2 you are splitting 145 objects between 12 groups. Consider the case when the objects are most spread out
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1

    Re: Pigeonhole theorem problem

    Quote Originally Posted by Yuuki View Post
    Problem #1:
    Suppose N objects are distributed between B boxes in such a way that no box is empty. How many objects must we choose in order to be sure that we have chosen the entire contents of at least one box?


    Problem #2:
    There are twelve signs of the Western Zodiac. Suppose there are 145 people in a room. Show that there must be 13 people who share the same sign of the Western Zodiac.
    I have absolutely no idea what #1 means.

    For #2, if there are 12 boxes and 144 balls then if you put all of the balls into the boxes is it possible that each box contains at most 12 balls?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    Re: Pigeonhole theorem problem

    Thank you, I realized where I was stuck on #2.
    I thought there had to be some zodiac-subset that had contained precisely 13 people and no more.
    But if 15 people had the same zodiac, it would still be true that 13 out of these 15 share the same zodiac, right?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Oct 2012
    From
    Ireland
    Posts
    600
    Thanks
    165

    Re: Pigeonhole theorem problem

    I believe your method for #1 is correct, when they say choose they mean remove. If no box can be empty then the maximum number in 1 box is N-B+1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    Re: Pigeonhole theorem problem

    Thanks Shakarri.

    So after I put one item in each box so that no box is empty, I have N-B objects left.
    If I put all of that in one box, that box will have the max number of contents possible.
    Since this box has N-B+1 objects in it, choosing N-B+1, I'm guaranteed to exhaust at least one box?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 16th 2013, 02:20 AM
  2. Pigeonhole Theorem
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: July 20th 2010, 09:07 AM
  3. Pigeonhole Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 15th 2009, 04:31 PM
  4. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: October 18th 2008, 02:41 PM
  5. A pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 12th 2007, 10:22 AM

Search Tags


/mathhelpforum @mathhelpforum