Results 1 to 3 of 3

Math Help - Pidgeon hole theorem

  1. #1
    Junior Member
    Joined
    Nov 2006
    Posts
    43
    Thanks
    1

    Pidgeon hole theorem

    Hi! I was reading an example in my book in the section about pidgeonhole theorem. I hav eno clue what this question is talking about, can someone explain or clarify? Thanks =]

    Assume that in a group of six ppl, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

    The explanation is: Let A be one of the six ppl. Of the five other ppl in the group, there are either three or more who are friends of A, or three or more who are enemies of A. (Why? wthek) This follows from the pigeonhole principle, since when five objects are divided into two sets, one of the sets has at least 3 elements. In the former case, suppose that B, C, and D are friends of A. If any two of these three individuals are friends, then these two and A form a group of three mutual friends. Otherwise, B, C, and D form a set of three mutual enemies. The proof in the latter case, when there are three or more enemies of A, proceeds in a similar manner.
    Why can't there be 4 friends and 2 enemies?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    “Show that there are either three mutual friends or three mutual enemies in the group.”
    In order for the given explanation to be correct, the sentence above must be taken to mean at least three and not exactly three.

    “Why can't there be 4 friends and 2 enemies?”
    Well there could be. If there are four friends then certainly there are three.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2006
    Posts
    43
    Thanks
    1
    Thanks. =]
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon-hole Principle (3)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 5th 2011, 09:22 AM
  2. [SOLVED] Pigeon-Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 30th 2011, 02:48 AM
  3. Pidgeon hole principle problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2010, 01:21 PM
  4. can someone poke a hole in this?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 26th 2009, 07:19 PM
  5. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 01:41 PM

Search Tags


/mathhelpforum @mathhelpforum