HMMT 二月 2019 · 冲刺赛 · 第 20 题

HMMT February 2019 — Guts Round — Problem 20

[ 9 ] On floor 0 of a weird-looking building, you enter an elevator that only has one button. You press the button twice and end up on floor 1. Thereafter, every time you press the button, you go up by X one floor with probability , where X is your current floor, and Y is the total number of times you Y have pressed the button thus far (not including the current one); otherwise, the elevator does nothing. th Between the third and the 100 press inclusive, what is the expected number of pairs of consecutive presses that both take you up a floor? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2019, February 16, 2019 — GUTS ROUND Organization Team Team ID#

解析

[ 9 ] On floor 0 of a weird-looking building, you enter an elevator that only has one button. You press the button twice and end up on floor 1. Thereafter, every time you press the button, you go up by X one floor with probability , where X is your current floor, and Y is the total number of times you Y have pressed the button thus far (not including the current one); otherwise, the elevator does nothing. th Between the third and the 100 press inclusive, what is the expected number of pairs of consecutive presses that both take you up a floor? Proposed by: Kevin Yang 97 Answer: 3 By induction, we can determine that after n total button presses, your current floor is uniformly distributed from 1 to n − 1: the base case n = 2 is trivial to check, and for the n + 1th press, the 1 i 1 i − 1 1 probability that you are now on floor i is (1 − ) + ( ) = for i = 1 , 2 , . . . , n , finishing the n − 1 n n − 1 n n inductive step. Hence, the probability that the ( n + 1)-th and ( n + 2)-th press both take you up a floor is ∑ n − 1 n − 1 ( n − 1) n (2 n − 1) n ( n − 1) 2 ∑ i + i + 1 i i + 1 1 i =1 6 2 · = = = . n − 1 n n + 1 ( n − 1) n ( n + 1) ( n − 1) n ( n + 1) 3 i =1 97 Since there are 100 − 3 = 97 possible pairs of consecutive presses, the expected value is . 3