Results 1 to 4 of 4
Like Tree3Thanks
  • 1 Post By Plato
  • 1 Post By MaxJasper
  • 1 Post By johnsomeone

Math Help - Problem Solving/Logic Problem

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Washington DC
    Posts
    4

    Problem Solving/Logic Problem

    In a party with 100 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Prove that the other 97 people know everyone at the party. (Assume that if A knows B, then B also knows A.)


    I'm not sure I even understand the question, so I'm having trouble even getting started
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1

    Re: Problem Solving/Logic Problem

    Quote Originally Posted by johnhisenburg87 View Post
    In a party with 100 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Prove that the other 97 people know everyone at the party. (Assume that if A knows B, then B also knows A.)
    This a a clever graph theory question.
    Suppose that J,~K,~\&~L are the three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Suppose two other people X~\&~Y are not mutually acquainted with each other.
    Consider the set \{J,K,X,Y\}. Is it true that among that set of four there is at least one person who knows each of the other three?
    How does that prove it?
    Thanks from johnhisenburg87
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    54

    Lightbulb Re: Problem Solving/Logic Problem

    Quote Originally Posted by johnhisenburg87 View Post
    In a party with 100 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Prove that the other 97 people know everyone at the party. (Assume that if A knows B, then B also knows A.)...
    Remove the 3 who don't know each other from 100. You are left with 97 people who when divided in groups of 4 at least one knows the other 3. Let's look at one group:
    {1,2,3,4} {1} knows {2,3,4}...now you can divide 97 people in groups of 4 in 3464840 ways! {1} placed in any group either knows 3 others or one person knows him. Now extend this analogy to person {2} ...{3}...{97} Hence, all know each other. [NB.: just kick the 3 out of the part!]
    Thanks from johnhisenburg87
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Problem Solving/Logic Problem

    (I'll assume that everyone at the party knows themself - it doesn't really matter to the problem.)
    Label the people P1, P2, P3, ... P100.
    We're given that 3 of them are all mutual strangers. Without loss of generality, say they're P98, P99, and P100.
    Claim 1: Each of the people P1 through P97 knows all 3 of those special ones (P98, P99, and P100).
    Reason: Assume Claim #1 is false. Then one of them (let's say it's P21), doesn't know one of those special last three (let's say it's P98, so we're assuming that P21 doesn't know P98). In that case, the set of four people {P21, P98, P99, P100} would have no one who knew all the others in that set. (P21 doesn't know all the others, because P21 doesn't know P98. P99 doesn't know all the others, because P99 doesn't know P100 or P98. The same reasoning goes for P98 and P100.) But that contradicts what we're given. Thus the initial assumption ("Assume Claim #1 is false") was false, and so Claim #1 is proven.
    Claim 2: Each of the people P1 through P97 knows all the other people P1 through P97.
    Reason: Assume Claim #2 is false. Then there's some pair (in P1 through P97) who don;t know each other. Without loss of generality, assume it's P1 and P2. So P1 and P2 don't know each other. Now consider the set of 4 people { P1, P2, P98, P99 }. None of them know all the others in that set (P1 doesn't know P2, P2 doesn't know P1, P98 doesn't know P99, and P99 doesn't know P98). But that contradicts that at least one of those 4 must know the other 3. Thus the initial assumption was false, and so Claim #2 is proven.
    Claim 3: The other 97 people (P1 through P97 in our labelling system) know everyone at the party.
    Reason: By Claim #1, each of those 97 people knows each of the special 3 people (P98, P99, P100). By Claim 2, each of those 97 people knows each of the non-special 97 other people (P1 through P97). Thus each of those 97 non-special people knows everyone at the party. QED
    Restate it this way (where no edge means the two verticies know each other):
    Proposition: Let G be a simple graph with 4 or more verticies, and the property that any induced subgraph on 4 vertices has at least one isolated vertex. If G contains a 3-clique, then G has exactly 3 edges.
    Last edited by johnsomeone; September 6th 2012 at 10:13 PM.
    Thanks from johnhisenburg87
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: October 4th 2011, 06:34 AM
  2. Help with logic problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 10th 2010, 04:37 PM
  3. logic problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: March 20th 2009, 04:11 AM
  4. Logic problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 15th 2008, 06:56 PM
  5. Logic problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 24th 2007, 06:58 AM

Search Tags


/mathhelpforum @mathhelpforum