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

HMMT November 2015 — THM Round — Problem 8

Consider an 8 × 8 grid of squares. A rook is placed in the lower left corner, and every minute it moves to a square in the same row or column with equal probability (the rook must move; i.e. it cannot stay in the same square). What is the expected number of minutes until the rook reaches the upper right corner?

解析

Consider an 8 × 8 grid of squares. A rook is placed in the lower left corner, and every minute it moves to a square in the same row or column with equal probability (the rook must move; i.e. it cannot stay in the same square). What is the expected number of minutes until the rook reaches the upper right corner? 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 top or right edges be E , and let the expected number of minutes it will take the rook to reach the upper e right corner from any other square be E . Note that this is justified because the expected time from c any square on the top or right edges is the same, as is the expected time from any other square (this is because swapping any two rows or columns doesn’t affect the movement of the rook). This gives us two 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