Question

Show that among any group of 20 people (where any two people are either friends or enemies), there are either four mutual friends or four mutual enemies.

Short answer

The resultant answer is, in a group of 20 people (where two people are either friends or enemies), there are four mutual enemies or four mutual friends.

Step-by-step solution

Given data

The given expression is, in a group of 10 people (where two people are either friends or enemies), there are either three mutual friends or four mutual enemies, and there are either three mutual enemies or four mutual friends.

Concept of Pigeonhole principle

If the number of pigeons exceeds the number of pigeonholes, at least one hole will hold at least two pigeons, according to the pigeon hole principle.

Find the possible combinations for group X and Y

Let us divide the group of 20 people in Group X with the first 10 people and Group Y with the second 10 people. By the result, Group X and Group Y both have either three mutual friends. For four mutual enemies E (\(3F\) or \(4{\rm{E}}\) ), and there are either three mutual enemies or four mutual friends (\(3E\) or \(4\;{\rm{F}}\) ).

The possible combinations for group \({\rm{X}}\) and \({\rm{Y}}\) are then:

\(3F\)or \(4{\rm{E}}\), \(3F\) or \(4{\rm{E}}\) …… (1)

\(3F\)or \(4{\rm{E}}\), \(3E\) or \(4\;{\rm{F}}\) …… (2)

\(3F\)or \(4{\rm{E}}\), \(3F\) or \(4{\rm{E}}\) …... (3)

\(3F\)or \(4{\rm{E}}\), \(3E\) or \(4\;{\rm{F}}\) ..…. (4)

It then needs to show that it has 4 mutual friends or 4 mutual enemies in each case.

Simplify first and second equation

First equation: \(3F\) or \(4{\rm{E}}\), \(3F\) or \(4{\rm{E}}\) "or" indicates that one of the two statements has to be true:

\(\begin{array}{l}(3F,3F) \Rightarrow 6{\rm{ mutual friends }}\\(3F,4E) \Rightarrow 4{\rm{ mutual enemies }}\\(4E,3F) \Rightarrow 8{\rm{ mutual enemies }}\\(4E,4E) \Rightarrow 8{\rm{ mutual enemies }}\end{array}\)

It then notes that, in each option, it has 4 mutual friends or 4 mutual enemies.

Second case: \(3F\) or \(4{\rm{E}}\), \(3E\) or \(4\;{\rm{F}}\) "or" indicates that one of the two statements has to be true: \((3F,3E) \Rightarrow 12\) people ( 6 pairs) and thus there exist at least one more pair of students among the remaining 8 people that is either friends or enemies

\(4\)mutual friends or \(4\) mutual enemies:

\((3F,4F) \Rightarrow 4\)mutual friends

\((4E,3E) \Rightarrow 4\)mutual enemies

\((4E,4F) \Rightarrow 4\)mutual enemies

It then notes that, in each option, it has 4 mutual friends or 4 mutual enemies.

Simplify third and fourth equation

Third case: \(3F\) or \(4{\rm{E}}\), \(3F\) or \(4{\rm{E}}\)"or" indicates that one of the two statements has to be true:

\[(3E,3F) \Rightarrow 12{\rm{ people ( }}6{\rm{ pairs)}}\]and thus, there exist at least one more pair of students among the remaining 8 people that is either friends or enemies.

\(4\)mutual friends or \(4\) mutual enemies:

\(\begin{array}{l}(3E,4E) \Rightarrow 4{\rm{ mutual enemies }}\\(4F,3F) \Rightarrow 4{\rm{ mutual friends }}\\(4F,4E) \Rightarrow 4{\rm{ mutual friends}}\end{array}\)

It then notes that, in each option, it has 4 mutual friends or 4 mutual enemies.

Fourth case: \(3F\) or \(4{\rm{E}}\), \(3E\) or \(4\;{\rm{F}}\)"or" indicates that one of the two statements has to be true:

\[\begin{array}{l}(3E,3E) \Rightarrow 6{\rm{ mutual enemies }}\\(3E,4F) \Rightarrow 4{\rm{ mutual friends }}\\(4F,3E) \Rightarrow 4{\rm{ mutual friends }}\\(4F,4F) \Rightarrow 8{\rm{ mutual friends}}\end{array}\]

It then notes that, in each option, it has 4 mutual friends or 4 mutual enemies.

Hence, the resultant answer is, in a group of 20 people (where two people are either friends or enemies), there are four mutual enemies or four mutual friends.