HMMT 十一月 2014 · 冲刺赛 · 第 30 题

HMMT November 2014 — Guts Round — Problem 30

[ 15 ] Suppose we keep rolling a fair 2014-sided die (whose faces are labelled 1 , 2 , . . . , 2014) until we obtain a value less than or equal to the previous roll. Let E be the expected number of times we roll the die. Find the nearest integer to 100 E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT NOVEMBER 2014, 15 NOVEMBER 2014 — GUTS ROUND Organization Team Team ID#

解析

[ 15 ] Suppose we keep rolling a fair 2014-sided die (whose faces are labelled 1 , 2 , . . . , 2014) until we obtain a value less than or equal to the previous roll. Let E be the expected number of times we roll the die. Find the nearest integer to 100 E . Answer: 272 Let n = 2014. Let p denote the probability the sequence has length at least k . We k observe that ( ) n k p = k k n since every sequence of k rolls can be sorted in exactly one way. Now the answer is ( ) n ∑ 1 p = 1 + . k n k ≥ 0 As n → ∞ , this approaches e . Indeed, one can check from here that the answer is 272. Guts Round