Results 1 to 5 of 5

Math Help - Pigeon Holes Question

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    14

    Pigeon Holes Question

    I am stuck on this question involving the pigeon hole principle. Any help is appreciated.
    In a gathering of 30 people, there are 104 different pairs of people who know each other.
    a. Show that some person must have at least seven acquaintances.
    b. Show that some person must have fewer than seven acquaintances.

    I think this one uses the ceiling function, but I am confused.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Part a, 208/30=7. See?.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    14
    Quote Originally Posted by galactus View Post
    Part a, 208/30=7. See?.
    I feel really stupid now. Thank you. I must be tired.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    For part b, maybe try a contradiction argument of some sort. Often, that is a good approach when doing a PHP proof.

    Maybe show there is a contradiction by there being at least 105 pairs of acquaintances. That may be one way to approach it.

    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by galactus View Post
    For part b, maybe try a contradiction argument of some sort. Often, that is a good approach when doing a PHP proof.

    Maybe show there is a contradiction by there being at least 105 pairs of acquaintances. That may be one way to approach it.

    Actually the pigeons are the acquaintances and there are 208.
    Each pair contributes two acquaintances. The holes are the persons.
    If each hole had at most six pigeons see the contradiction?
    If each hole had at least seven pigeons see the contradiction?

    BTW: using graph theory makes this much easier.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Please help..Holes and Asymptotes
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 15th 2009, 05:08 PM
  2. Pigeon Hole Principle Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2009, 11:22 PM
  3. Holes and Graphs
    Posted in the Algebra Forum
    Replies: 2
    Last Post: July 15th 2008, 04:26 PM
  4. Pigeon Hole Principle Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 6th 2008, 08:42 AM
  5. big pigeon hole question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 11th 2007, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum