HMMT 二月 2019 · 冲刺赛 · 第 15 题

HMMT February 2019 — Guts Round — Problem 15

[ 7 ] 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?

解析

[ 7 ] 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? Proposed by: Yuan Yao Answer: 17 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 5 faction. Since the factions are unordered, there are 2 / 2 = 16 ways to assign the “alignments” that each gives a unique configuration of relations. So in total there are 16 + 1 = 17 possibilities.