PUMaC 2022 · 组合（A 组） · 第 1 题

PUMaC 2022 — Combinatorics (Division A) — Problem 1

In the country of PUMaC-land, there are 5 villages and 3 cities. Vedant is building roads between the 8 settlements according to the following rules: a) There is at most one road between any two settlements; b) Any city has exactly three roads connected to it; c) Any village has exactly one road connected to it; d) Any two settlements are connected by a path of roads. In how many ways can Vedant build the roads?

解析

In the country of PUMaC-land, there are 5 villages and 3 cities. Vedant is building roads between the 8 settlements according to the following rules: a) There is at most one road between any two settlements; b) Any city has exactly three roads connected to it; c) Any village has exactly one road connected to it; d) Any two settlements are connected by a path of roads. In how many ways can Vedant build the roads? Proposed by Sunay Joshi Answer: 90 If a village is connected to another village, then neither village is connected to the rest of the settlements, so this cannot be possible. Thus, every village is connected to a city. If some city is connected to three villages, then these four settlements cannot be connected to the other four, which means this is impossible. Thus, each city is connected to at most two villages, which is only possible if two cities are connected to two villages and one city is connected to one village. The only possible such configuration has the one-village city connected to both other cities. There are 3 ways to choose which city is the one-village city, then 5 ways to 4 choose which village is connected to this city. Finally, there are = 6 ways to choose the 2 two villages connected to one of the other cities. Thus, our total number of possibilities is 3 · 5 · 6 = 90.