HMMT 十一月 2022 · 团队赛 · 第 10 题
HMMT November 2022 — Team Round — Problem 10
题目详情
- [60] There is a unit circle that starts out painted white. Every second, you choose uniformly at random an arc of arclength 1 of the circle and paint it a new color. You use a new color each time, and new paint covers up old paint. Let c be the expected number of colors visible after n seconds. Compute n lim c . n →∞ n
解析
- [60] There is a unit circle that starts out painted white. Every second, you choose uniformly at random an arc of arclength 1 of the circle and paint it a new color. You use a new color each time, and new paint covers up old paint. Let c be the expected number of colors visible after n seconds. Compute n lim c . n →∞ n Proposed by: Gabriel Wu Answer: 4 π Solution 1: Notice that colors always appear in contiguous arcs on the circle (i.e. there’s never a color that appears in two disconnected arcs). So the number of distinct visible colors is equal to the number of radii that serve as boundaries between colors. Each time we place a new color, we create 2 1 more of these radii, but all of the previous radii have a p = chance of being covered up. 2 π 1 It is well-known that, given an event that occurs with probability p , it takes an expected trials for p it to happen – this means that any given radii has an expected lifespan of 2 π before it gets covered up (i.e. it remains visible for 2 π turns on average). Thus, over the course of n ≫ 1 turns there are 2 n 4 πn total radii created, each lasting an average of 2 π turns, so there are = 4 π radii visible on average n each turn. A more rigorous way to see this is the two radii created on the most recent turn have a probability 1 of being exposed; the two radii created last turn each have a probability 1 − p of being exposed; the 2 two radii created two turns ago each have a probability (1 − p ) of being exposed, and so on. Thus, on turn n , the expected number of exposed radii is 2 n − 1 2(1 + (1 − p ) + (1 − p ) + · · · + (1 − p ) ) . 2 This geometric series converges to as n grows. p Solution 2: Notice that colors always appear in contiguous arcs on the circle (i.e. there’s never a color that appears in two disconnected arcs). So the number of distinct visible colors is equal to the number of radii that serve as boundaries between colors. Each time we place a new color, we create 2 more of these radii. However, if the expected number of colors after turn n is constant, we must expect to remove 2 of these radii each turn. This is only possible when there are 4 π total radii, since 1 we expect to remove of them each time. 2 π Solution 3: Consider the probability that the k -th last added arc is visible. Suppose there are j arcs after the k -th last arc that partially covers this arc. Then the probability that the k -th last arc is j +1 still visible is , since this is equivalent to randomly choosing j positions within the k -th last arc to j 2 j place an arc in, then randomly choosing a direction, and there are 2 ways to choose directions and 2 j + 1 of them are good. The probability that any arc partially covers the k -th last arc is . Putting 2 π everything together, the probability that the k -th last arc is visible is k − 1 j k − 1 − j X j + 1 k − 1 2 2 · · · 1 − j 2 j 2 π 2 π j =0 so the answer is n k − 1 j k − 1 − j X X j + 1 k − 1 2 2 1 + · · · 1 − j 2 j 2 π 2 π k =2 j =0 (as the last arc is definitely visible). We can write this as n k − 1 j k − 1 − j X X k − 1 1 2 1 + ( j + 1) · · · 1 − . j 2 π 2 π k =2 j =0 Now, k − 1 j k − 1 − j k − 1 X k − 1 1 2 1 2 1 · · · 1 − = + 1 − j 2 π 2 π 2 π 2 π j =0 k − 1 k − 2 by binomial theorem. We can write j · = ( k − 1) , so j j − 1 k − 1 k − 1 j k − 1 − j j k − 1 − j X X k − 1 1 2 k − 2 1 2 j · · · 1 − = ( k − 1) · · 1 − j 2 π 2 π j − 1 2 π 2 π j =0 j =1 k − 2 j +1 k − 2 − j X k − 2 1 2 = ( k − 1) · · 1 − j 2 π 2 π j =0 k − 2 k − 1 1 2 = · + 1 − . 2 π 2 π 2 π Therefore the answer is n k − 2 X 1 k − 1 1 1 + 1 − + 1 − 2 π 2 π 2 π k =2 which is an arithmetic sequence times a geometric sequence. Standard techniques simplify this to 4 π . Solution 4: We solve for the lifespan of an arc. Let f ( x ) represent the expected number of turns 1 an arc of length 2 πx will remain visible. Our final answer will be to calculate f ( ) Then we get the 2 π recurrence Z x 2 π − 1 f ( x ) = 1 + ( − x ) f ( x ) + 2 f ( x ) dx 2 π 0 2 π − 1 The 1 term comes from counting the fact that the arc is visible during the current turn. The ( − 2 π 2 π − 1 x ) f ( x ) term comes from the fact that there is a − x chance that the next arc will not intersect the 2 π current arc, in which case the current arc would get an extra f ( x ) turns to live. The integral comes from the fact that we want to take the average of f ( y ) for y ∼ [0 , x ], which corresponds to the next r arc covering up 2 π ( x − y ) of the current one. If we differentiate both sides, we end up with a differential equation. Solve it via separation. We end 1 2 up with f ( x ) = 4 π x + 2 π . Plugging in x = gets us 4 π . 2 π x 1 In general, the answer is f ( x ) = + , where we are placing arcs of length 2 πk . 2 k k