HMMT-Nov 2015 team, Problem 6

Marcus and four of his relatives are at a party. Each pair of the five people are either friends or enemies. For any two enemies, there is no person that they are both friends with. In how many ways is this possible?

Solution: Denote friendship between two people $a$ and $b$ by $a \sim b$. Then, assuming everyone is friends with themselves, the following conditions are satisfied: \begin{itemize}   \item $a \sim a$   \item If $a \sim b$, then $b \sim a$   \item If $a \sim b$ and $b \sim c$, then $a \sim c$ \end{itemize} Thus we can separate the five people into a few groups (possibly one group), such that people are friends within each group, but two people are enemies when they are in different groups. Here comes the calculation. Since the number of group(s) can be 1,2,3,4, or 5, we calculate for each of those cases. When there's only one group, then we only have 1 possibility that we have a group of 5 , and the total number of friendship assignments in this case is $\left(\begin{array}{l}5 \\ 5\end{array}\right)=1$; when there are two groups, we have $5=1+4=2+3$ are all possible numbers of the two groups, with a total of $\left(\begin{array}{l}5 \\ 1\end{array}\right)+\left(\begin{array}{l}5 \\ 2\end{array}\right)=15$ choices; when there are three groups, then we have $5=1+1+3=1+2+2$, with $\left(\begin{array}{l}5 \\ 3\end{array}\right)+\frac{\left(\begin{array}{l}5 \\ 1\end{array}\right)\left(\begin{array}{l}5 \\ 2\end{array}\right)}{2}=25$ possibilities; when there are four of them, then we have $5=1+1+1+2$ be its only possibility, with $\left(\begin{array}{l}5 \\ 2\end{array}\right)=10$ separations; when there are 5 groups, obviously we have 1 possibility. Hence, we have a total of $1+15+25+10+1=52$ possibilities. Alternatively, we can also solve the problem recursively. Let $B_{n}$ be the number of friendship graphs with $n$ people, and consider an arbitrary group. If this group has size $k$, then there are $\left(\begin{array}{l}n \\ k\end{array}\right)$ possible such groups, and $B_{n-k}$ friendship graphs on the remaining $n-k$ people. Therefore, we have the recursion \[ B_{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) B_{n-k} \] with the initial condition $B_{1}=1$. Calculating routinely gives $B_{5}=52$ as before. $\fbox{52}$.

Answer: 52