← All solutions

In graph-theoretic terms, the problem asks for a minimum dominating set in a tournament. The solution is essentially just exhaustive search, and the main difficulty is to realize that it works. It is not hard to prove that a simple greedy algorithm always produces a dominating set of size at most 6. Therefore, we can start by computing the greedy solution and then trying all smaller sets of vertices (there are at most ∑_i=1⁵ C(75, i) = 18 545 215 such sets). To make it fast enough, one should use bitmasks for quickly checking whether a given set is a solution.

In fact, the largest possible answer is actually only 5, so the greedy step is not needed. But proving this is not easy and knowing it is of course not necessary to solve the problem.