HMMT 二月 2026 · 冲刺赛 · 第 26 题
HMMT February 2026 — Guts Round — Problem 26
题目详情
- [14] Marin is taking a random walk on a line. For each integer n ranging from 1 to 10 , inclusive and th in order, Marin takes a step of length F either left or right with equal probability, where F is the n n n Fibonacci number. Compute Marin’s expected distance from his starting point. (The Fibonacci numbers are defined by F = F = 1 and the recurrence F = F + F for all n ≥ 3 .) 1 2 n n − 1 n − 2
解析
- [14] Marin is taking a random walk on a line. For each integer n ranging from 1 to 10 , inclusive and in order, Marin takes a step of length F either left or right with equal probability, where F is the n n th n Fibonacci number. Compute Marin’s expected distance from his starting point. (The Fibonacci numbers are defined by F = F = 1 and the recurrence F = F + F for all 1 2 n n − 1 n − 2 n ≥ 3 .) Proposed by: Derek Liu 3741 Answer: 64 Solution: Let d denote the expected distance after n steps. We will derive a recurrence for d . n n th Observe that after n − 1 steps, if Bob is x ≤ F away from his starting position, his n step makes n this distance either F + x or F − x , with the average being F . If x > F , the two possible distances n n n n are F + x and x − F , with average x instead. Thus, d is the expected value of max( F , x ) . n n n n th th We claim that if x > F , then the ( n − 2) and ( n − 1) steps must be in the same direction. Indeed, n otherwise the distance is upper-bounded by F − F + F + · · · + F = F + ( F − 1) < F . n − 1 n − 2 n − 3 1 n − 3 n − 1 n th th The ( n − 2) and ( n − 1) steps are in the same direction with probability 1 / 2 . Given that this is the case, the expected value of | x − F | is d , as the last two steps combined cover a distance of n n − 3 F . Note that x − F is just as likely to be some value y as it is to be − y , so the expected value of n n max( x, F ) in this case is n 1 1 F + max( x − F , 0) = F + E [ | x − F | ] = F + d . n n n n n n − 3 2 2 Recall that x > F with probability 1 / 2 , so n ( ) 1 1 1 1 d = ( F ) + F + d = F + d . n n n n − 3 n n − 3 2 2 2 4 ©2026 HMMT We conclude that 1 d = F + d 10 10 7 4 1 1 = F + F + d 10 7 4 2 4 4 1 1 1 = F + F + F + d 10 7 4 1 2 3 4 4 4 13 3 1 = 55 + + + 4 16 64 3741 = . 64