HMMT 十一月 2025 · 冲刺赛 · 第 21 题
HMMT November 2025 — Guts Round — Problem 21
题目详情
- [11] Sarunyu starts at a vertex of a regular 7-gon. At each step, he chooses an unvisited vertex uniformly at random and walks to it along a straight line. He continues until all vertices are visited, and then walks back to his starting vertex along a straight line. A self-intersection occurs when two of his steps cross strictly inside the 7-gon. Compute the expected number of self-intersections in Sarunyu’s walk. © 2025 HMMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2025, November 08, 2025 — GUTS ROUND Organization Team Team ID#
解析
- [11] Sarunyu starts at a vertex of a regular 7-gon. At each step, he chooses an unvisited vertex uniformly at random and walks to it along a straight line. He continues until all vertices are visited, and then walks back to his starting vertex along a straight line. A self-intersection occurs when two of his steps cross strictly inside the 7-gon. Compute the expected number of self-intersections in Sarunyu’s walk. Proposed by: Sebastian Attlan 14 Answer: 3 Solution: Any intersection of two diagonals can be defined by the 4 points that they correspond to. Label the vertices of the 7-gon as A through A in cyclic order. For each group of 4 points 1 7 A , A , A , A , with 1 ≤ i < j < k < l ≤ 7, we compute the probability they are traversed with a i j k l self-intersection. A self-intersection occurs when Sarunyu’s walk visits these four vertices out of cyclic order. In other words, his path goes through A and A consecutively (in either order) and through A and A consec- i k j l utively (in either order). Fix these 4 vertices and assume (without loss of generality) that Sarunyu’s starting point is not among them. There are 6! = 720 possible paths for the remaining 6 vertices in the walk. To count the paths that contain this intersection, we treat A A and A A as blocks for 4! i k j l 2 2 ways to arrange the vertices and 2 ways to orient the blocks. This gives us 4! · 2 = 96 paths. Thus, 96 2 the probability any set of 4 vertices gives an intersection is = . Applying linearity of expectation 720 15 and summing over all choices of ( i, j, k, l ), the total expectation is 2 7 14 · = . 15 4 3