HMMT 十一月 2015 · THM 赛 · 第 8 题

英文解析

8. Consider an 8 × 8 grid of squares. A rook is placed in the lower left corner, and every minute it movesto a square in the same row or column with equal probability (the rook must move; i.e. it cannot stayin the same square). What is the expected number of minutes until the rook reaches the upper rightcorner?
   Proposed by: Alexander Katz
   Answer: 70
   Let the expected number of minutes it will take the rook to reach the upper right corner from the topor right edges be E , and let the expected number of minutes it will take the rook to reach the upperright corner from any other square be E . Note that this is justified because the expected time fromecany square on the top or right edges is the same, as is the expected time from any other square (thisis because swapping any two rows or columns doesn’t affect the movement of the rook). This gives ustwo linear equations:
   2 12
   E = ( E + 1) + ( E + 1)
   c e c
   14 14
   1 6 7
   E = (1) + ( E + 1) + ( E + 1)
   e e c
   14 14 14
   which gives the solution E = 63 , E = 70 .
   e c