There are towns on the island of Hibernia. Every pair of towns is either connected by a single road, or is not connected. If we consider any subset of towns, the total number of roads connecting these towns to each other is a constant. There are roads in total in Hibernia.
Find all possible values of .
Solution
Consider the more general problem with towns (the specific case for this problem is ). Let denote the (constant) number of roads connecting any subset of towns. Also, let denote the number of roads connecting town and town . Finally, for , let denote the total number of roads connected to town .
Note that . Clearly, and , where the latter sum is over all -element subsets of . The number of roads connected to at least one of the towns with number or is equal to . Thus, for any -element subset ,
Adding all these equations for every -element subset yields
which may be rewritten as .
Note that both and are divisible by , and that the only integer which can divide both and is (this latter case occurring if and only if is divisible by ). Since does not divide , in the situation of the given problem and are coprime. Hence, is a multiple of . As (with equality when all pairs of towns are connected), the only possibility is . Therefore the total number of roads on the island is .