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

英文解析

9. [ 3 ] Suppose that in every room, Mario randomly picks a door to walk through. What is the expectednumber of doors (not including Mario’s initial entrance to the first room) through which Mario willpass 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 hei
   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 , ori +1 1 1 2
   4 4 4
   E = 4 + E . We also get E = 1 + E . Solving this system of equations yields E = 20.3
   1 2 2 1 1 4