HMMT 十一月 2021 · 冲刺赛 · 第 16 题

HMMT November 2021 — Guts Round — Problem 16

[10] A counter begins at 0. Then, every second, the counter either increases by 1 or resets back to 0 with m equal probability. The expected value of the counter after ten seconds can be written as , where m, n n are positive integers and gcd( m, n ) = 1. Find 100 m + n . ∼ ∼ ∼ ∼ ∼ ∼

解析

[10] A counter begins at 0. Then, every second, the counter either increases by 1 or resets back to m 0 with equal probability. The expected value of the counter after ten seconds can be written as , n where m, n are positive integers and gcd( m, n ) = 1. Find 100 m + n . Proposed by: Sean Li Answer: 103324 Solution: The probability that the counter is equal to k corresponds to the last k seconds all being − k − 1 increases by 1 and the second before that being a reset to 0 , which happens with probability 2 . The only contradiction to this is when k = 10 and the counter gets there by only counting 1’s. Therefore, the expected value is simply the sum of probabilities times the counter, which is ( ) ( ) 9 9 9 ∑ ∑ ∑ 10 k 1 1 1 1 1 1 1 1 1023

= + + + + ... + = + + ... + = . 10 k +1 10 k +1 10 k +1 10 10 2 2 2 2 2 2 2 2 4 2 1024 k =1 k =1 k =2 ∼ ∼ ∼ ∼ ∼ ∼