PUMaC 2021 · 组合（A 组） · 第 6 题
PUMaC 2021 — Combinatorics (Division A) — Problem 6
题目详情
- Alice, Bob, and Carol are playing a game. Each turn, one of them says one of the 3 players’ names, chosen from { Alice, Bob, Carol } uniformly at random. Alice goes first, Bob goes second, Carol goes third, and they repeat in that order. Let E be the expected number of names that are have been said when, for the first time, all 3 names have been said twice. If m E = for relatively prime positive integers m and n , find m + n . (Include the last name to n be said twice in your count.)
解析
- Alice, Bob, and Carol are playing a game. Each turn, one of them says one of the 3 players’ names, chosen from { Alice, Bob, Carol } uniformly at random. Alice goes first, Bob goes second, Carol goes third, and they repeat in that order. Let E be the expected number of names that are have been said when, for the first time, all 3 names have been said twice. If m E = for relatively prime positive integers m and n , find m + n . (Include the last name to n be said twice in your count.) Proposed by: Sunay Joshi Answer: 383 Let E denote the expected number of additional names that must be said until all 3 names m,n have been said twice, starting with m names said once, n names said at least twice, and 3 − m − n names said 0 times. We know that E = 0, and we wish to find E = E . 0 , 3 0 , 0 We derive a recurrence relation for E . If a name is said for the first time on the next turn, m,n 3 − m − n then it contributes ( E + 1) to the expected value. Similarly, if one of the m names m +1 ,n 3 m already said once is said again, we get a term of ( E + 1). Finally, if one of the n m − 1 ,n +1 3 n names already said twice is said again, we get ( E + 1). Adding these up, we find the m,n 3 recurrence 3 − m − n m n E = 1 + E + E + E , m,n m +1 ,n m − 1 ,n +1 m,n 3 3 3 which simplifies to 3 − n 3 − m − n m E = E + E + 1 . m,n m +1 ,n m − 1 ,n +1 3 3 3 347 Solving the resulting system of 9 equations, we find that E = E = , and our answer is 0 , 0 36 m + n = 347 + 36 = 383. 3