Problem 07

Problem 07

The planet Xzorg is inhabited by n green creatures. The laws on Xzorg determine that every creature can have at most 3 friends (friendship is symmetric and denoted by ~). This is carefully exploited: every two creatures that are not friends, have at least one friend in common. Find the largest possible value of n. Hint: apply double counting on S = {(a,b,c) | a~b~c}.

Solution

On one hand, since every creature has at most 3 friends, every creature is the b of at most 6 triples in S. Hence, |S| ≤ 6n. On the other hand, every creature is the a of at least n-4 triples of S (since all creatures, except for a and its at most 3 friends, have a common friend with a). Hence, |S| ≥ n(n-4). Together, this yields n(n-4) ≤ |S| ≤ 6n, which yields n ≤ 10.

A nice drawing of the Xzorgs in their optimal position.

To show that this is actually the maximum, we need to find an example for n = 10. If n = 10, we need equality in both inequalities above, which means that every creature has exactly three friends, and that every two non-partners have exactly one friend in common. With these two stronger rules, finding a structure is suddenly a lot easier, e.g. the one depicted on the right.

Remarks

It is a nice way to show that double counting can be used for more than the standard examples, without needing involved theory or inequalities. Also, it is another example where a purely theoretical proof can help in the practical construction of an optimal example. Also, note that the optimal solution is equivalent to the Petersen graph (but graph theory is for a follow-up course here).