Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: The Party Problem with 10 people

  1. Oct 15, 2011 #1
    1. The problem statement, all variables and given/known data
    Assume that every pair of people are (mutual) friends or enemies.

    Show that in a group of 10 people, there are either 3 mutual friends or 4
    mutual enemies.

    Hint: Fix one person X. Start out by observing that X has either k friends
    or 10-k enemies for an appropriately chosen k.

    2. Relevant equations

    3. The attempt at a solution
    A proof was shown in class for the case where there are 6 people, that involved a K6 graph. Is there any way to do this problem without using a graph since a K10 graph is quite large?

  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted