Counting Celebrity Cliques

Probability Level 5

A party $P$ is a set of distinct people with a relation $\text{knows}$ .

A non-empty subset $C$ of $P$ is a celebrity clique if everyone in the clique is known by everyone in the party, but the members of the clique only know each other. Formally,

$\forall x \in P, y \in C :: x \text{ knows } y \wedge (y \text{ knows } x \implies x \in C)$

What is the maximum number of possible celebrity cliques in a party of 16 people?

Inspired by Richard Bird's Pearls of Functional Programming

The answer is 1.

1 solution

Guillermo Templado
Sep 5, 2016

Source: Richard Bird's Pearls of functional Programming . This is Mary's solution (page 57).

Suppose that $C_1$ and $C_2$ are two celebrity cliques. Pick any $c_1$ in $C_1$ and $c_2$ in $C_2$ . We have that $c_1$ knows $c_2$ from the fact that everybody in the clique $C_2$ is known by everybody at the party. But since clique members know only other members of the clique, it follows that $c_2 \in C_1$ . Since $c_2$ was arbitrary, we have $C_2 \subseteq C_1$ and, by symmetry, $C_1 \subseteq C_2$ .

Furthemore, there is the possibilty that there exists a celebrity clique in which everybody knows everybody.

Counting Celebrity Cliques

Inspired by Richard Bird's Pearls of Functional Programming

The answer is 1.

1 solution

0 pending reports