PUMaC 2015 · 组合（A 组） · 第 6 题

PUMaC 2015 — Combinatorics (Division A) — Problem 6

[ 6 ] Every day, Heesu talks to Sally with some probability p . One day, after not talking to Sally the previous day, Heesu resolves to ask Sally out on a date. From now on, each day, if Heesu has talked to Sally each of the past four days, then Heesu will ask Sally out on a date. Heesu’s friend remarked that at this rate, it would take Heesu an expected 2800 days to finally ask m Sally out. Suppose p = , where gcd( m, n ) = 1 and m, n > 0. What is m + n ? n

解析

[ 6 ] Every day, Heesu talks to Sally with some probability p . One day, after not talking to Sally the previous day, Heesu resolves to ask Sally out on a date. From now on, each day, if Heesu has talked to Sally each of the past four days, then Heesu will ask Sally out on a date. Heesu’s friend remarked that at this rate, it would take Heesu an expected 2800 days to finally ask m Sally out. Suppose p = , where gcd( m, n ) = 1 and m, n > 0. What is m + n ? n Solution: Let E be the expected number of days it would take Heesu to ask Sally out (in terms of p ). Let E for k ∈ Z denote the expected number of days it would take given that k Heesu has talked to Sally each of the last k days but not the ( k + 1)-th day before. Then, for all k ≥ 4, E = 0. Additionally, we have: k E = 1 + (1 − p ) E + pE 0 0 1 E = 1 + (1 − p ) E + pE 1 0 2 E = 1 + (1 − p ) E + pE 2 0 3 E = 1 + (1 − p ) E + pE 3 0 4 Subtracting the equations, we then have: 1 2 3 3 = E − E = p ( E − E ) = p ( E − E ) = p ( E − E ) = p E 0 1 1 2 2 3 3 4 3 p Then, solving, we obtain: 1 1 1 1 1 1 1 1 1 1 E = , E = + , E = + + , E = + + + 3 2 1 0 4 3 4 2 3 4 2 3 4 p p p p p p p p p p Since E = E , we have: 0 1 1 1 1 2800 = 7 + 49 + 343 + 2401 = + + + 2 3 4 p p p p 3 1 So p = and m + n = 8 . 7 Author: Roy Zhao