The Party Problem with 10 people

  • Thread starter kz26
  • Start date
  • #1
1
0

Homework Statement


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.


Homework Equations


N/A


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?

Thanks!
 

Answers and Replies

Related Threads on The Party Problem with 10 people

  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
4
Views
821
  • Last Post
Replies
8
Views
816
  • Last Post
Replies
7
Views
1K
Replies
3
Views
4K
Replies
12
Views
1K
Replies
2
Views
3K
Replies
23
Views
402
Replies
7
Views
3K
Replies
4
Views
1K
Top