Library / /1294 of 1394

, 2024

Combinatorics Difficulty 6.0 National Olympiad Prove it United States

Problem:

The country of HMMTLand has 8 cities. Its government decides to construct several two-way roads between pairs of distinct cities. After they finish construction, it turns out that each city can reach exactly 3 other cities via a single road, and from any pair of distinct cities, either exactly 0 or 2 other cities can be reached from both cities by a single road. Compute the number of ways HMMTLand could have constructed the roads.

Solution

Solution:

Let the cities be numbered $1,2,3,4,5,6,7,8$ . WLOG, $1$ is connected to $2,3$ , and $4$ . First suppose $2$ and $3$ are connected; then $3$ and $1$ share a second common neighbor, which must be $4$ (as $1$ is not connected to anything else). Likewise $2$ and $4$ are connected, and so $5,6,7,8$ are pairwise connected as well, so the graph consists of two disjoint copies of $K_{4}$ :

There are $\frac{1}{2}\binom{8}{4}=35$ ways to partition the $8$ vertices into two groups of $4$ , so there are $35$ such graphs.

Otherwise, none of $2,3,4$ are connected to each other. Then $2$ and $3$ must share a common neighbor, as must $3$ and $4$ , and $2$ and $4$ . If these are the same neighbor, this vertex would share all three neighbors with $1$ , so they must be pairwise distinct. The last vertex must then be connected to these three, creating a cube graph.

A cube has $48$ symmetries, so the number of such graphs is $\frac{8!}{48}=840$ .

The total is $35+840=875$ .

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.