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

HMMT November 2009 — Team Round — Problem 11

[ 5 ] In general, if there are d doors in every room (but still only 1 correct door) and r rooms, the last of which leads into Bowser’s level, what is the expected number of doors through which Mario will pass before he reaches Bowser’s level? Page 2 of 2

解析

[ 5 ] In general, if there are d doors in every room (but still only 1 correct door) and r rooms, the last of which leads into Bowser’s level, what is the expected number of doors through which Mario will pass before he reaches Bowser’s level? r d ( d − 1) Answer: Let E be the expected number of doors through which Mario will pass in i d − 1 the future if he is currently in room i for i = 1 , 2 , . . . , r + 1 (we will set E = 0). We claim r +1 d − 1 1 d − 1 that E = 1 + E + E . This is because, as before, there is a chance of ending up in i 1 i +1 d d d 1 room 1, and a chance of ending up in room i + 1. Note that we can re-write this equation as d dE = d + ( d − 1) E + E . i 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 i as dE − 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 given i d − 1 at http://en.wikipedia.org/wiki/Recurrence_relation ). Solving for E using E = E + c and 1 1 r r r d ( d − 1) d − 1 E = 1 + E , we get E = . r 1 1 d d − 1