Results 1 to 4 of 4

Math Help - Discrete Maths Question

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    19

    Discrete Maths Question

    Hey, I have a question that looks relatively easy, but I'm not too sure how to go about answering this one.
    Any help would be greatly appreciated

    A group of 15 people is gathered together for a meeting. Show that at least two people must have the same number of acquaintances at the meeting.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Storm20 View Post
    Hey, I have a question that looks relatively easy, but I'm not too sure how to go about answering this one.
    Any help would be greatly appreciated

    A group of 15 people is gathered together for a meeting. Show that at least two people must have the same number of acquaintances at the meeting.
    As currently worded, I don't think the question can be answered. What is an acquaintance ....?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    19
    yeah that's the problem I was having, it's not worded very clearly. I presume it means show that two people either meet or know two other people at the meeting.

    But really....doesn't give us much scope on how to solve it mathematically.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by Storm20 View Post
    A group of 15 people is gathered together for a meeting. Show that at least two people must have the same number of acquaintances at the meeting.
    This is a common question in sections on graph theory. By two people being acquaintances we mean a two-way relationship. So in a graph representing the acquaintances in a group a edge joins two vertices(people) that are acquainted.
    Theorem: In any simple graph, |V|\ge 2, there are at least two vertices with the same degree.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with Discrete Maths Question.... stuck :(
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2010, 12:51 PM
  2. Discrete Maths
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: January 18th 2010, 06:58 AM
  3. discrete maths
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 21st 2009, 07:44 AM
  4. Discrete Maths question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 29th 2009, 02:07 PM
  5. help me in discrete maths
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 14th 2008, 06:50 AM

Search Tags


/mathhelpforum @mathhelpforum