Library / /1343 of 1394

, 2019

Combinatorics Difficulty 6.1 National Olympiad Prove it United States

Problem:
Five people are at a party. Each pair of them are friends, enemies, or frenemies (which is equivalent to being both friends and enemies). It is known that given any three people $A$ , $B$ , $C$ :
- If $A$ and $B$ are friends and $B$ and $C$ are friends, then $A$ and $C$ are friends;
- If $A$ and $B$ are enemies and $B$ and $C$ are enemies, then $A$ and $C$ are friends;
- If $A$ and $B$ are friends and $B$ and $C$ are enemies, then $A$ and $C$ are enemies.
How many possible relationship configurations are there among the five people?

Solution

Solution:
If $A$ and $B$ are frenemies, then regardless of whether another person $C$ is friends or enemies with $A$ , $C$ will have to be frenemies with $B$ and vice versa. Therefore, if there is one pair of frenemies then all of them are frenemies with each other, and there is only one possibility.

If there are no frenemies, then one can always separate the five people into two possibly "factions" (one of which may be empty) such that two people are friends if and only if they belong to the same faction. Since the factions are unordered, there are $2^{5} / 2 = 16$ ways to assign the "alignments" that each gives a unique configuration of relations. So in total there are $16 + 1 = 17$ possibilities.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.