HMMT 十一月 2009 · 团队赛 · 第 11 题

英文解析

11. [ 5 ] In general, if there are d doors in every room (but still only 1 correct door) and r rooms, the last ofwhich leads into Bowser’s level, what is the expected number of doors through which Mario will passbefore he reaches Bowser’s level?
    d ( d − 1)r
    Answer: Let E be the expected number of doors through which Mario will pass inid − 1
    the future if he is currently in room i for i = 1 , 2 , . . . , r + 1 (we will set E = 0). We claimr +1
    d − 1 1 d − 1
    that E = 1 + E + E . This is because, as before, there is a chance of ending up ini 1 i +1
    d d droom 1, and a chance of ending up in room i + 1. Note that we can re-write this equation as 1
    d e = d + ( d − 1) E + E .di 1 i +1
    We can solve this system of equation as follows: let E = E + c . Then we can re-write each equation
    1 i ias d e − d · c = d + ( d − 1) E + E − c , so c = d · c + d , and c = 0. We can then see that
    1 i 1 1 i +1 i +1 i 1
    i − 1
    d − 1
    c = d (either by finding the pattern or by using more advanced techniques, such as those givenid − 1
    at http://en.wikipedia.org/wiki/Recurrence_relation ). Solving for E using E = E + c and
    1 1 r rrd ( d − 1)
    d − 1
    E = 1 + E , we get E = .
    r 1 1
    d d − 1