Maths Olympiad Prep

Library / /654 of 740

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Consider an 8×88 \times 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?

Solution

Solution:

Let the expected number of minutes it will take the rook to reach the upper right corner from the top or right edges be EeE_{e}, and let the expected number of minutes it will take the rook to reach the upper right corner from any other square be EcE_{c}. Note that this is justified because the expected time from 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:
Ec=214(Ee+1)+1214(Ec+1)Ee=114(1)+614(Ee+1)+714(Ec+1) \begin{gathered} E_{c} = \frac{2}{14}\left(E_{e} + 1\right) + \frac{12}{14}\left(E_{c} + 1\right) \\ E_{e} = \frac{1}{14}(1) + \frac{6}{14}\left(E_{e} + 1\right) + \frac{7}{14}\left(E_{c} + 1\right) \end{gathered}
which gives the solution Ee=63E_{e} = 63, Ec=70E_{c} = 70.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.