Counting Celebrity Cliques

Discrete Mathematics 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

Problem Loading...

Note Loading...

Set Loading...