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

HMMT November 2009 — Team Round — Problem 9

[ 3 ] Suppose that in every room, Mario randomly picks a door to walk through. What is the expected number of doors (not including Mario’s initial entrance to the first room) through which Mario will pass before he reaches Bowser’s level?

解析

[ 3 ] Suppose that in every room, Mario randomly picks a door to walk through. What is the expected number of doors (not including Mario’s initial entrance to the first room) through which Mario will pass before he reaches Bowser’s level? Answer: 20 Let E be the expected number of doors through which Mario will pass in the future if he i 3 1 is currently in room i for i = 1 , 2 , 3 (we will set E = 0). We claim that E = 1 + E + E . Indeed, 3 i 1 i +1 4 4 the 1 at the beginning comes from the fact that we need to pass through a door to leave the room, the 3 3 1 E comes from the fact that there is a chance of ending up in room 1, and the E corresponds 1 i +1 4 4 4 1 3 1 to the fact that there is a chance of ending up in E . Using this, we get E = 1 + E + E , or i +1 1 1 2 4 4 4 3 E = 4 + E . We also get E = 1 + E . Solving this system of equations yields E = 20. 1 2 2 1 1 4