Irish Mathematical Olympiad

Consider the more general problem with $n$ towns (the specific case for this problem is $n = 100$). Let $K$ denote the (constant) number of roads connecting any subset of $n-2$ towns. Also, let $c_{i,j} \in \{0,1\}$ denote the number of roads connecting town $i$ and town $j$. Finally, for $i = 1, 2, \dots, n$, let $d_i$ denote the total number of roads connected to town $i$.

Note that $N \le n(n-1)/2$. Clearly, $\sum d_i = 2N$ and $\sum c_{i,j} = N$, where the latter sum is over all $2$-element subsets $\{i,j\}$ of $\{1, 2, \dots, n\}$. The number of roads connected to at least one of the towns with number $i$ or $j$ is equal to $d_i + d_j - c_{i,j}$. Thus, for any $2$-element subset $\{i,j\} \subset \{1, 2, \dots, n\}$,
$$K = N - d_i - d_j + c_{i,j}.$$
Adding all these equations for every $2$-element subset $\{i,j\}$ yields
$$\binom{n}{2}K = \binom{n}{2}N - 2(n-1)N + N$$
which may be rewritten as $n(n-1)K = (n-2)(n-3)N$.

Note that both $n(n-1)$ and $(n-2)(n-3)$ are divisible by $2$, and that the only integer $k > 2$ which can divide both $n(n-1)$ and $(n-2)(n-3)$ is $3$ (this latter case occurring if and only if $n$ is divisible by $3$). Since $3$ does not divide $n = 100$, in the situation of the given problem $n(n-1)/2$ and $(n-2)(n-3)/2$ are coprime. Hence, $N$ is a multiple of $n(n-1)/2$. As $N \le n(n-1)/2$ (with equality when all pairs of towns are connected), the only possibility is $N = n(n-1)/2$. Therefore the total number of roads on the island is $50 \cdot 99 = 4950$.