PUMaC 2011 · 组合（A 组） · 第 8 题
PUMaC 2011 — Combinatorics (Division A) — Problem 8
题目详情
- [ 8 ] A road company is trying to build a system of highways in a country with 21 cities. Each highway runs between two cities. A trip is a sequence of distinct cities C , . . . , C , for which 1 n there is a highway between C and C . The company wants to fulfill the following two i i +1 constraints:
解析
- This solution is based on a proof in (Walks and Paths in Trees, Boll´ abos and Tyomkyn, 2011), which also discusses a number of other extremal results about walks and paths in trees. For any tree T (a tree is an acyclic undirected graph), define P ( T ) to be the number of k -paths k (a k -path is a sequence of k +1 distinct vertices, for which there is an edge between consecutive vertices) in T . Consider any tree T with P ( T ) maximal, given that it has | E ( T ) | = 20 edges; 4 then the problem asks for the value of 2 P ( T ). 4 For any leaves v, w ∈ V ( T ), define n ( v ) to be the number of vertices of T which are of distance k k from v , which is the same as the number of k -paths containing v , and define DC ( T, v, w ) to be the tree resulting from deleting v , and attaching a leaf to the unique neighbor of w (the delete-clone operation). Thus | E ( DC ( T, v, w )) | = | E ( T ) | . First suppose v, w are leaves such that d ( v, w ) 6 = 4, so that there are no 4-paths containing both v and w , and without loss of generality suppose n ( v ) < n ( w ). Then, P ( DC ( T, v, w )) = 4 4 4 P ( T ) + n ( w ) − n ( v ) > P ( T ), contradicting the maximality of P ( T ). Hence, for any leaves 4 4 4 4 4 v, w not of distance 4 apart, then n ( v ) = n ( w ), and P ( T ) = P ( DC ( T, v, w )). 4 4 4 4 Now, we show that we can move around vertices so that all leaves are of distance 2 or 4 apart, without decreasing the number of 4-paths. If v is a leaf, let the leaf class of v be the set of all leaves adjacent to the unique neighbor of v , e.g., all leaves of distance 2 from v . Then, if ′ ′ v, w are leaves with d ( v, w ) 6 = 2 , 4, recursively define T = T , T = DC ( T , v, w ) where w 0 n +1 n is a leaf in the leaf class of w ; this merges the leaf classes of v and w . Hence, the number of leaf classes is a decreasing invariant in that if T is a tree with P ( T ) maximal and a minimal 4 number of leaf classes, then any leaves are of distance 2 or 4 apart. (It is easy to see this argument generalizes to k -paths instead of 4-paths.) Let a star S centered at v be the graph obtained by attaching p leaves to v . If the leaves of p T are either distance 2 or 4 apart, then T can be constructed from a star S centered at v , m each of whose leaves v is replaced by another star S centered at v (so each v has p + 1 i p i i i i ∑ neighbors). Then, we find that P ( T ) = p p . For any s, t , then we can write 4 i j i<j ∑ ∑ P ( T ) = p p + ( p + p ) p + p p , 4 s t s t i i j i 6 = s,t i<j i,j 6 = s,t 4 which (say by AM-GM) for any fixed value of p + p is maximized when p , p are as close s t s t to each other as possible. Hence, all of the p ’s are within one of each other, so the tree T is i uniquely determined by m . Trying these possible values ( m = 2 , 3 , . . . ), we see that P ( T ) is 4 ( ) 4 2 maximized when m = 4, and the answer is 2 P ( T ) = 2 · × 4 = 192 . 4 2 5