HMMT 二月 2024 · COMB 赛 · 第 5 题

HMMT February 2024 — COMB Round — Problem 5

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.

解析

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. Proposed by: Derek Liu Answer: 875 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 1 2 5 6 4 3 8 7 ( ) 8 1 There are = 35 ways to partition the 8 vertices into two groups of 4 , so there are 35 such graphs. 2 4 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. 5 4 1 3 8 6 2 7 8! A cube has 48 symmetries, so the number of such graphs is = 840 . 48 The total is 35 + 840 = 875 .