HMMT 二月 2025 · COMB 赛 · 第 10 题
HMMT February 2025 — COMB Round — Problem 10
题目详情
- The circumference of a circle is divided into 45 arcs, each of length 1. Initially, there are 15 snakes, each of length 1, occupying every third arc. Every second, each snake independently moves either one 1 arc left or one arc right, each with probability . If two snakes ever touch, they merge to form a single 2 snake occupying the arcs of both of the previous snakes, and the merged snake moves as one snake. Compute the expected number of seconds until there is only one snake left.
解析
- The circumference of a circle is divided into 45 arcs, each of length 1. Initially, there are 15 snakes, each of length 1, occupying every third arc. Every second, each snake independently moves either one 1 arc left or one arc right, each with probability . If two snakes ever touch, they merge to form a single 2 snake occupying the arcs of both of the previous snakes, and the merged snake moves as one snake. Compute the expected number of seconds until there is only one snake left. Proposed by: Srinivas Arun 448 Answer: 3 Solution: We solve the problem generally for n snakes and 3 n arcs. Without loss of generality, fix the two snakes A and B that will eventually form the ends of the last snake. Note that A and B must be consecutive in the initial configuration; assume B lies immediately clockwise from A . Let d be the arclength between A and B (measuring clockwise from A to B ). As long as d ̸ = 0 and d ̸ = 2 n , we know that A and B lie in different snakes and thus move independently. Therefore, we can consider d to be on a random walk starting at 2, where 1 • the probability d does not change is (if A and B move in the same direction), 2 1 • the probability d decreases by 2 is (if A moves clockwise and B moves counterclockwise), 4 1 • the probability that d increases by 2 is (if A moves counterclockwise and B moves clockwise), 4 • the random walk ends if d = 0 or d = 2 n (the snakes touch; only d = 2 n obeys our assumption). We want to find the conditional expected length of the random walk given that it ends at d = 2 n . The key idea is to directly calculate the conditional probabilities of each transition. To do this, we will repeatedly use the following well-known fact: for any random walk where moving 1 unit to the left and moving 1 unit to the right are equally likely, the probability of reaching the point b units to the right a of the starting point before reaching the point a units to the left is . a + b For any single transition, we have P (“ d moves from 2 k to 2 k − 2” | “the path ends at 2 n ”) P (“ d moves from 2 k to 2 k − 2” AND “the path starting from 2 k − 2 ends at 2 n ”) = P (“the path starting from 2 k ends at 2 n ”) 1 k − 1 ( )( ) k − 1 4 n = = , k 4 k ( ) n P (“ d moves from 2 k to 2 k + 2” | “the path ends at 2 n ”) P (“ d moves from 2 k to 2 k + 2” AND “the path starting from 2 k + 2 ends at 2 n ”) = P (“the path starting from 2 k ends at 2 n ”) 1 k +1 ( )( ) k + 1 4 n = = , k 4 k ( ) n P (“ d stays at 2 k ” | “the path ends at 2 n ”) P (“ d stays at 2 k ” AND “the path starting from 2 k ends at 2 n ”) = P (“the path starting from 2 k ends at 2 n ”) 1 k ( )( ) 1 2 n = = . k 2 ( ) n Let E denote the expected length of a walk starting at 2 k given that the walk ends at 2 n . Then, for 2 k 0 < k < n , we have k − 1 1 k + 1 E = ( E + 1) + ( E + 1) + ( E + 1) 2 k 2 k − 2 2 k 2 k +2 4 k 2 4 k k − 1 k + 1 = ⇒ E = 2 + E + E . 2 k 2 k − 2 2 k +2 2 k 2 k 2 2( k − 1) It can be shown by induction that E = E − for all k ≥ 1. Since E = 0, this implies that 2 k 2 2 n 3 2 2( n − 1) 448 E = . When n = 15, the answer is therefore . 2 3 3