1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Calculus Party

  1. Mar 1, 2015 #1
    1. The problem statement, all variables and given/known data

    Prove that at any party there are two people who know the same number of people. Assume that if A knows B, then B knows A. Assume also that everyone knows himself or herself. [Hint: Use indirect reasoning.]

    2. Relevant equations

    Proof by contradiction.

    3. The attempt at a solution

    I started by trying to show that if no one knew the same number of people as anyone else, that that would lead to a contradiction. But I'm stuck even at this point. Any suggestions?
     
  2. jcsd
  3. Mar 1, 2015 #2

    RUber

    User Avatar
    Homework Helper

    Assume there are N people, who all know different numbers of people.
    then there is a person who knows the most people and a person who knows the fewest people.
    What is the smallest number of people anyone could know?
    What is the largest number of people anyone could know?
    Arrange people in order of how many people they know.
    Consider how the people could know each other, then see what happens when you get to the middle. I think the person who knows one less than half will necessarily be known by everyone in the top half.
     
  4. Mar 1, 2015 #3
    Each of the N members could know only themselves, or, in the extreme case, everyone could know everyone else (including themselves). I'm not sure what you mean by the "middle": are you assuming that one person knows only h/erself, one person knows 2 people,...,one person knows N people and that I should order accordingly?
     
  5. Mar 1, 2015 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure. The only way that they can all be different is that 1 person knows only himself, one person knows 2 people, one person knows 3 people, etc until finally there is one person that knows everybody. What does that say about the one person that knows only himself?
     
  6. Mar 1, 2015 #5

    RUber

    User Avatar
    Homework Helper

    If knowing yourself doesn't count, then you could have people knowing 0 to N-1, or 1 to N without initial contradiction.
     
  7. Mar 1, 2015 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    But knowing yourself does count. The problem statement says that. You are suggesting a variation on the problem, right?
     
  8. Mar 1, 2015 #7

    RUber

    User Avatar
    Homework Helper

    I missed that part in the initial problem.
    I think the variation might be interesting to consider, but the same conclusion is reached since the maximum anyone would be able to know would be N-1.
     
  9. Mar 1, 2015 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure. If somebody knows N-1 people (not counting themselves), then there is nobody that can know 0 people. It's just a different way of counting the people you know. It doesn't change the conclusion that two people must count the same number.
     
    Last edited: Mar 1, 2015
  10. Mar 2, 2015 #9
    Thanks for your help everyone...it makes a lot more sense now. The only way everyone knows a different number of people is if one person knows only h/erself, another person knows 2 people, ..., and one person knows everyone. But this would mean that the person who doesn't know anyone else in fact knows the socialite, which leads to a contradition, so at least two people must know the same number of people.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Calculus Party
  1. Basic Calculus (Replies: 6)

Loading...