Results 1 to 2 of 2

Math Help - the pigeon hole principle

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    9

    Exclamation the pigeon hole principle

    it is know that among any group of 3 students in a class 2 of them are friends. the total number of students is 25. prove that there is a student who has at least 12 friends.

    thnx
    justanotherperson
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi,

    suppose every student has less than 12 friends. Pick any student A, he has less than or exactly 11 friends, so the number of students other than A who are not friends with A is greater or equal to 25-12 = 13, let student B be one of them. B has also less than or exactly 11 friends. Since 13-12=1>0, there must be at least one student C, other than A and B, who is not friends with A and is not friends with B. Since A and B are not friends with each other, A,B,C is a group of three students and no two of them are friends, which contradicts our assumption. Thus there must be a student who has at least 12 friends.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 05:24 AM
  2. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 08:22 PM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 03:56 AM
  4. Pigeon Hole Principle Help!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 17th 2008, 12:14 AM
  5. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum