PUMaC 2023 · 组合（A 组） · 第 7 题
PUMaC 2023 — Combinatorics (Division A) — Problem 7
题目详情
- A utility company is building a network to send electricity to fifty houses, with addresses 0 , 1 , 2 , . . . , 49. The power center only connects directly to house 0, so electricity reaches all other houses through a system of wires that connects specific pairs of houses. To save money, the company only lays wires between as few pairs of distinct houses as possible; additionally, two houses with addresses a and b can only have a wire between them if at least one of the following three conditions is met: • 10 divides both a and b . 1 b a • ≡ (mod 5). 10 10 b a • ≡ (mod 5). 10 10 Letting N be the number of distinct ways such a wire system can be configured so that every house receives electricity, find the remainder when N is divided by 1000.
解析
- A utility company is building a network to send electricity to fifty houses, with addresses 0 , 1 , 2 , . . . , 49. The power center only connects directly to house 0, so electricity reaches all other houses through a system of wires that connects specific pairs of houses. To save money, the company only lays wires between as few pairs of distinct houses as possible; additionally, two houses with addresses a and b can only have a wire between them if at least one of the following three conditions is met: • 10 divides both a and b . b a • ≡ (mod 5). 10 10 b a • ≡ (mod 5). 10 10 Letting N be the number of distinct ways such a wire system can be configured so that every house receives electricity, find the remainder when N is divided by 1000. Proposed by Austen Mazenko Answer: 810 Interpreting the network as a graph G , with houses as vertices and wires as edges, we see that the conditions reduce to the graph being comprised of five K cliques and one K 11 5 clique. Specifically, the groups of houses { 0 , ..., 10 } , { 10 , ..., 20 } , { 20 , ..., 30 } , { 30 , ..., 40 } , and { 40 , ..., 49 , 0 } are all fully connected within themselves forming K cliques, and the vertices 11 { 0 , 10 , 20 , 30 , 40 } form a K clique. Now, a connected subgraph with a minimal number of 5 edges, which is precisely what any valid configuration of the wire network is, is by definition just a spanning tree of the graph. Thus, we seek the number of spanning trees. Call the vertices 0 , 10 , 20 , 30 , 40 connectors , because any path in a spanning tree between two vertices in different K cliques must include a connector. Let C be an auxiliary K graph with vertices 11 5 that are phantom copies of the connectors. Recall that on a tree, there is a unique shortest path between any two vertices; the crucial observation is that any spanning tree T on G can be associated with a spanning tree f ( T ) on C in which two connectors are adjacent if the shortest path between those connectors on T doesn’t pass through another connector. To count the number of spanning trees on G , we will split into casework based on which spanning tree on C they correspond to (namely, based on the image of the map f taking spanning trees on G to spanning trees on C ). Call two connectors near if they are in a K 11 clique together, and far otherwise (e.g. 0 is near 10 and 40 and far from 20 and 30). Note that two far connectors will share an edge in T iff they do in f ( T ). Next, if two near connectors share an edge in f ( T ), then the shortest path in T connecting them lies in the K containing 11 both of them. Moreover, because these connectors silo off this K from the rest of G , we 11 9 see that T forms a spanning tree on this K ; the number of ways this can happen is 11 by 11 Cayley’s formula. Finally, if two near connectors don’t share an edge in f ( T ), then there can be no path between them in the K containing both of them. However, every vertex in this 11 K must be path-connected to one of these connectors via T , so the restriction of T to this 11 K looks like two disjoint spanning trees, one for each of the two connectors. We claim that 11 the number of ways to choose two disjoint spanning trees on K rooted at two fixed vertices 11 8 v , v (the connectors) is 2 · 11 . Note that every such pair of disjoint spanning trees can be 1 2 uniquely associated with a single spanning tree on K by adding the edge v v . Thus, it’s 11 1 2 equivalent to counting the number of spanning trees on K containing a fixed edge. Now, if 11 9 we pick a spanning tree at random, by Cayley’s formula there are 11 to pick from, and by 10 2 symmetry the probability a given edge is in the spanning tree is = (the number of edges 11 11 ( ) 2 4 2 9 8 in each spanning tree divided by the number of edges in K ). Hence, there are · 11 = 2 · 11 11 11 ways to pick two disjoint spanning trees rooted at two fixed vertices, as claimed. Putting this all together, for a given spanning tree on C , the number of spanning trees T of 9 a 8 5 − a G that map to it will be (11 ) · (2 · 11 ) , where a is the number of edges between near connectors in the spanning tree on C . Doing casework on the spanning trees of C ≃ K , we 5 see that a = 4 in 5 of them, a = 3 in 2 · 5 + 4 · 5 = 30, a = 2 in 4 · 5 + 7 · 5 = 55, a = 1 in 30, and a = 0 in 5 of them. In conclusion, the total number of configurations is 36 8 27 2 16 18 3 24 9 4 32 5 40 N = 5 · 11 · 2 · 11 + 30 · 11 · 2 · 11 + 55 · 11 · 2 · 11 + 30 · 11 · 2 · 11 + 5 · 2 · 11 , and taking modulo 1000 gives 410 + 720 + 240 + 280 + 160 = 810.