Track / Stage 7 / 26 of 300 #1426 of 1964

Problem 1426

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.0 Prove it

In a group of five people any two are either friends or enemies , no three of them are friends of each other and no three of them are enemies of each other . Prove that every person in this group has exactly two friends .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Assume a person has three friends:
- Let's denote this person as $A$ and their three friends as $B, C,$ and $D$ .
- According to the problem, no three people can be mutual friends. Therefore, among $B, C,$ and $D$ , at least one pair must be enemies.
- Without loss of generality, assume $B$ and $C$ are enemies.

2. **Consider the implications of $B$ and $C$ being enemies:**
- Since $B$ and $C$ are enemies, and they are both friends with $A$ , we need to check the relationship between $B$ and $D$ , and $C$ and $D$ .
- If $B$ and $D$ are friends, and $C$ and $D$ are friends, then $B, C,$ and $D$ would form a friend-triangle, which contradicts the problem's conditions.
- If $B$ and $D$ are enemies, and $C$ and $D$ are enemies, then $B, C,$ and $D$ would form an enemy-triangle, which also contradicts the problem's conditions.

3. Conclude that a person cannot have three friends:
- Since having three friends leads to a contradiction, it follows that no person in the group can have three friends.

4. Assume a person has three enemies:
- Let's denote this person as $A$ and their three enemies as $B, C,$ and $D$ .
- According to the problem, no three people can be mutual enemies. Therefore, among $B, C,$ and $D$ , at least one pair must be friends.
- Without loss of generality, assume $B$ and $C$ are friends.

5. **Consider the implications of $B$ and $C$ being friends:**
- Since $B$ and $C$ are friends, and they are both enemies with $A$ , we need to check the relationship between $B$ and $D$ , and $C$ and $D$ .
- If $B$ and $D$ are enemies, and $C$ and $D$ are enemies, then $B, C,$ and $D$ would form an enemy-triangle, which contradicts the problem's conditions.
- If $B$ and $D$ are friends, and $C$ and $D$ are friends, then $B, C,$ and $D$ would form a friend-triangle, which also contradicts the problem's conditions.

6. Conclude that a person cannot have three enemies:
- Since having three enemies leads to a contradiction, it follows that no person in the group can have three enemies.

7. Conclude that each person must have exactly two friends and two enemies:
- Since no person can have three friends or three enemies, and each person must have relationships with four other people, it follows that each person must have exactly two friends and two enemies.

$\blacksquare$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.