HMMT 二月 2023 · 团队赛 · 第 10 题
HMMT February 2023 — Team Round — Problem 10
题目详情
- [90] One thousand people are in a tennis tournament where each person plays against each other person exactly once, and there are no ties. Prove that it is possible to put all the competitors in a line so that each of the 998 people who are not at an end of the line either defeated both their neighbors or lost to both their neighbors.
解析
- [90] One thousand people are in a tennis tournament where each person plays against each other person exactly once, and there are no ties. Prove that it is possible to put all the competitors in a line so that each of the 998 people who are not at an end of the line either defeated both their neighbors or lost to both their neighbors. Proposed by: Maxim Li Solution: Take the natural graph theoretic interpretation, where an edge points towards the loser of each pair, and call such a line an alternating path. Consider the longest alternating path, and suppose it doesn’t contain everyone. We will show we can make the path longer, which would be a contradiction. First, assume the path has an odd number of vertices, labeled v , . . . , v . WLOG v points towards 1 n 1 v , v points towards v , all the way up to v which points towards v (otherwise, reverse all the 2 3 2 n n − 1 edges). Also WLOG v points towards v (if not, label the vertices backwards). Let w be a vertex not 1 n in the path. Note that if v points towards w , we can make the path longer by adding w to the end. n Thus, w must point towards v . But now we can take the path w, v , v , . . . , v , which is longer n n 1 n − 1 than before, and so a contradiction. Now assume the path has an even number of vertices, labeled v , . . . , v , and WLOG v points towards 1 n 1 v again. Then v will point towards v . Since 1000 is even, there are at least 2 vertices not in the 2 n − 1 n path, say w and w . If either one points towards v , we can add it to the end of the path, so v must 1 2 n n point towards both. Similarly, they must both point towards v . But now note that if v points 1 n − 1 to either, we can make the path v , . . . , v , w , v , which is longer. Thus, w , w must both point 1 n − 1 i n 1 2 towards v . Now restrict our attention to v , . . . , v . Note that w , w both point towards both n − 1 1 n − 1 1 2 ends, so we can WLOG assume v points towards v . Also WLOG w points towards w . Then we 1 n − 1 1 2 can form the path w , w , v , v , . . . , v , which has n + 1 vertices. Thus, if the longest alternating 2 1 n − 1 1 n − 2 path does not contain every vertex, we can make it longer, which is a contradiction, so there must exist an alternating path with all 1000 vertices.