retagged by
3,494 views
1 votes
1 votes

Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

retagged by

1 Answer

1 votes
1 votes
let the group be labeled as A;B;C;D;E and F. Consider now the person labeled as
A. The remaining five people can be grouped into friends or enemies of A. Of the five other people
(other than A), there are either three or more who are friends of A, or three or more than are enemies
of A. Indeed, when a set of 5 objects (persons) is divided into two groups (friends or enemies) there
are at least d5=2e = 3 elements in one of these groups. Consider first the group of friends of A. Call
them B;C or D. If any of these three individuals are friends, then these two and A form the group
of three mutual friends. Otherwise, B, C and D form a set of three mutual enemies. The proof in the
case of three enemies of A proceeds in a similar manner.

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Oct 25, 2018
944 views
How many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds?what this question means?
1 votes
1 votes
1 answer
2
Sammohan Ganguly asked May 25, 2018
1,343 views
Suppose a graph $G$ has $6$ nodes. Prove that either $G$ or $G'$ must contain a triangle.($G'$ is the complement of $G$.) Prove it using pigeonhole principle.
4 votes
4 votes
2 answers
3
sourav. asked Aug 24, 2016
2,136 views
Show that if seven integers are selected from the first10 positive integers, there must be at least two pairsof these integers with the sum 11.Attempt-:partition will be ...
2 votes
2 votes
2 answers
4
Anu asked Jul 14, 2015
1,920 views
Prove that at a party where there are at least two people, there are two people who know the same number of other people there.