HMMT 二月 2018 · 团队赛 · 第 8 题
HMMT February 2018 — Team Round — Problem 8
题目详情
- [ 60 ] Allen plays a game on a tree with 2 n vertices, each of whose vertices can be red or blue. Initially, all of the vertices of the tree are colored red. In one move, Allen is allowed to take two vertices of the same color which are connected by an edge and change both of them to the opposite color. He wins if at any time, all of the vertices of the tree are colored blue. (a) ( 20 ) Show that Allen can win if and only if the vertices can be split up into two groups V and 1 V of size n , such that each edge in the tree has one endpoint in V and one endpoint in V . 2 1 2 (b) ( 40 ) Let V = { a , . . . , a } and V = { b , . . . , b } from part (a). Let M be the minimum over all 1 1 n 2 1 n permutations σ of { 1 , . . . , n } of the quantity n ∑ d ( a , b ) , i σ ( i ) i =1 where d ( v, w ) denotes the number of edges along the shortest path between vertices v and w in the tree. Show that if Allen can win, then the minimum number of moves that it can take for Allen to win is equal to M . (A graph consists of a set of vertices and some edges between distinct pairs of vertices. It is connected if every pair of vertices are connected by some path of one or more edges. A tree is a graph which is connected, in which the number of edges is one less than the number of vertices.) e − v +1
解析
- [ 60 ] Allen plays a game on a tree with 2 n vertices, each of whose vertices can be red or blue. Initially, all of the vertices of the tree are colored red. In one move, Allen is allowed to take two vertices of the same color which are connected by an edge and change both of them to the opposite color. He wins if at any time, all of the vertices of the tree are colored blue. (a) ( 20 ) Show that Allen can win if and only if the vertices can be split up into two groups V and 1 V of size n , such that each edge in the tree has one endpoint in V and one endpoint in V . 2 1 2 (b) ( 40 ) Let V = { a , . . . , a } and V = { b , . . . , b } from part (a). Let M be the minimum over all 1 1 n 2 1 n permutations σ of { 1 , . . . , n } of the quantity n ∑ d ( a , b ) , i σ ( i ) i =1 where d ( v, w ) denotes the number of edges along the shortest path between vertices v and w in the tree. Show that if Allen can win, then the minimum number of moves that it can take for Allen to win is equal to M . (A graph consists of a set of vertices and some edges between distinct pairs of vertices. It is connected if every pair of vertices are connected by some path of one or more edges. A tree is a graph which is connected, in which the number of edges is one less than the number of vertices.) Proposed by: Kevin Sun Part (a): First we show that if we can’t split the vertices in the desired way then Allen cannot win. To do so, observe that there is a unique way to split the vertices into two groups so that all edges cross between the two groups, since trees are bipartite. Each of Allen’s moves either adds one more blue vertex to each group or removes a blue vertex from each group, so the difference in the number of blue vertices between the two groups is invariant. Both groups initially have no blue vertices, so Allen can only possibly arrive at a state where both groups have all blue vertices if both groups were initially of equal size. To show that Allen can win when the splitting is possible, we induct on n . It’s trivial for n = 1. A tree on 2 n vertices has 2 n − 1 edges, so the total degree for each of the two n -vertex groups is 2 n − 1. Therefore, at least one vertex in each group is a leaf, say L in one group and L in the other. Allen 1 2 can then flip all the vertices from L to L since there is a path of even length (in terms of number 1 2 of vertices) from one to the other, including flipping L and L , and then flip back all of the middle 1 2 vertices in the path, with the end result being that L and L are blue while all other vertices in the 1 2 tree remain red. This lets us remove L and L from consideration and apply the inductive hypothesis 1 2 on the remaining graph. Part (b): For each edge e in the graph, we can determine a minimum number of times Allen must perform an operation on the endpoints of that edge (henceforth, ”flip this edge”), as follows. Observe that removing e disconnects the graph into two components. Each component is still a tree which can be split into two groups as before, though not necessarily with an equal number of vertices. In particular, suppose that the two groups differ by d vertices. Flipping any edge other than e does not change the difference in number of blue vertices between the two groups of the component. So e must flip at least d times if Allen is to win. Let m be the minimum number of times that edge e must flip, e ′ ′ as determined in this way, and let M be the total sum of all of the m . And let T be the original tree e with every edge duplicated m times (or removed if m = 0). e e ′ Observe that any permutation σ that gives us n paths must have total length at least M for the same ′ reasons as in the above paragraph, so M ≤ M . ′ ′ ′ In fact, we will show that M = M . To show that M = M , it suffices to show that M ≥ M , which we ′ will show by finding a partitioning of T into n odd-length paths for which every vertex is the endpoint ′ of exactly one path. This will show that M is the sum of path lengths for some permutation, meaning it is at least the sum of path lengths for the optimal permutation. We do this by strong induction. ′ The base case is trivial, and if any m is 0 then we’re immediately done because we can split the T e into two smaller trees. Otherwise we repeat the argument from part (a) where we use a path between two leaves, since each group of n vertices must contain a leaf, thereby reducing the number of vertices in our tree by 2 and allowing us to use our inductive hypothesis. ′ It now suffices to show that Allen can win the game in M moves, but this is exactly the same induction ′ as in the previous paragraph. If any m is 0 then we’re immediately done by splitting T into two e smaller trees, otherwise we use the path between the two leaves to use our inductive hypothesis. e − v +1