Maths Olympiad Prep

Library / /290 of 462

Combinatorics Difficulty 6.1 National Olympiad Prove it Ireland

There are 100100 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 9898 towns, the total number of roads connecting these towns to each other is a constant. There are NN roads in total in Hibernia.
Find all possible values of NN.

Solution

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

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.