Solution to Week 5 Bonus

This post originally appeared on the Brilliant blog on 9/16/2012.

Bonus Challenge: There are 20 people on the board of directors of a publicly listed company. Each pair of people are either friends or enemies with each other. Every person has exactly 6 enemies on the board. If every group of 3 directors form a committee, what is the total number of committees that are formed by all friends or all enemies?

Key Technique: Double Counting

Solution: Let $A, B, C$ and $D$ be the number of committees that have 3 pairs of friends, 2 pairs of friends, 1 pair of friends and no pair of friends, respectively. Thus, the total number of committees is equal to ${20 \choose 3} = A + B + C + D$.

For any person $i$, along with 2 others $j$ and $k$, we will call this set $FE$ if $i$ is friends with one and enemies with the other. Since every member has exactly 13 friends and 6 enemies, thus by the rule of product, we have $|FE| = 20 \cdot 13 \cdot 6 = 1560$. Consider the committees: committees with 3 pairs of friends will contribute 0 to the $FE$ count, committees with 2 pairs of friends will contribute 2 to the $FE$ count, committees with 1 pairs of friends will contribute 2 to the $FE$ count, committees with 0 pairs of friends will contribute 0 to the $FE$ count. Hence, we get that $2B+2C = FE \Rightarrow B+C=780$. Thus, the total number of committees with all of them being friends or enemies is equal to $A+D = 1140 - 780 = 360$.

Answer: 360

Note: We may naturally complete this solution by looking at the sets $FF$ and $EE$ in which $i$ is friends (enemies respectively) with both two others, $j$ and $k$. This gives 2 more equations, for a total of 4. However, the 4 equations are not linearly independent, so we can not solve for the individual values of $A, B, C$ and $D$.