HMMT 二月 2025 · 冲刺赛 · 第 32 题
HMMT February 2025 — Guts Round — Problem 32
题目详情
- [16] In the coordinate plane, a closed lattice loop of length 2 n is a sequence of lattice points P , P , P , 0 1 2 . . . , P such that P and P are both the origin and P P = 1 for each i . A closed lattice loop of 2 n 0 2 n i i +1 length 2026 is chosen uniformly at random from all such loops. Let k be the maximum integer such that the line ℓ with equation x + y = k passes through at least one point of the loop. Compute the expected number of indices i such that 0 ≤ i ≤ 2025 and P lies on ℓ . i (A lattice point is a point with integer coordinates.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2025, February 15, 2025 — GUTS ROUND Organization Team Team ID#
解析
- [16] In the coordinate plane, a closed lattice loop of length 2 n is a sequence of lattice points P , P , 0 1 P , . . . , P such that P and P are both the origin and P P = 1 for each i . A closed lattice loop 2 2 n 0 2 n i i +1 of length 2026 is chosen uniformly at random from all such loops. Let k be the maximum integer such that the line ℓ with equation x + y = k passes through at least one point of the loop. Compute the expected number of indices i such that 0 ≤ i ≤ 2025 and P lies on ℓ . i (A lattice point is a point with integer coordinates.) Proposed by: Carlos Rodriguez, Jordan Lefkowitz 1013 Answer: 507 2 n Solution: We claim that if 2026 is replaced with 2 n , the answer is . n +1 Write the path as a sequence of U , D , L , and R moves. The possible sequences that can result are precisely those with an equal number of U ’s and D ’s, and an equal number of R ’s and L ’s. We first project this sequence onto a single dimension by converting each U and R to a 1, and each D and L to a − 1. The resulting sequence will have an equal number of 1’s and − 1’s. We claim that every such sequence of n 1’s and n − 1’s corresponds to the same number of closed lattice loops. Indeed, given such a sequence, a corresponding lattice loop can be made by replacing all 1’s with U ’s and R ’s, and all − 1’s with D ’s and L ’s, so that there are an equal number of U ’s and D ’s. Nothing in this replacement process is order-dependent, so the number of ways to create this loop does not depend on the initial sequence. We can see that each of the 1’s move the path towards ℓ and the − 1’s move the path away. Hence, we can think of the path as a one-dimensional walk, starting and ending in the same place, where the points on ℓ correspond exactly to the maxima of this one-dimensional walk. Using Catalan numbers, the probability that any given point is at the maxima is 2 n 1 1 n +1 n = , 2 n n + 1 n 2 n and thus by linearity, the expected number of i ∈ [0 , 2025] such that P is on ℓ is . Plugging in i n +1 1013 n = 1013 gives a final answer of . 507