1
$\begingroup$

This is a problem from HMMT 2015.

On an $8\times8$ chessboard, a rook starts at the lower left corner. Each minute, it moves to a square in the same row or same column with equal probability (however it cannot stay at the same square). What is the expected number of minutes until the rook reaches the upper right corner?

I saw a solution that stated the expected minutes it takes the rook from any square in the top row or any square in the right column (besides the upper right corner) to reach the upper right corner is equal. Additionally, they said that the expected minutes it takes for the rook to reach the upper right corner from any other square was equal. So basically if we number the grids on the coordinate grid, with $(1,1)$ being the lower left corner and $(8,8)$ being the upper right corner, the expected minutes it takes the rook from any of the squares $(8,1),(8,2)\cdots (8,7),(1,8),(2,8),\cdots(7,8)$ to reach $(8,8)$ is equal. Also, the expected number of minutes it takes the rook from any of the squares $(x,y), 1\leq x\leq 7, 1\leq y\leq 7$ to reach $(8,8)$ is equal as well.

They also mention that this is due to the fact that "swapping any two rows or columns doesn’t affect the movement of the rook" Can someone explain why this logic is true?

Thanks!

$\endgroup$
3
$\begingroup$

To visualize the symmetry in question, consider two starting squares $A$ and $B$, and suppose that neither of them shares a row or a column with the winning square. Then consider the permutation of the rows which transposes the rows of $A$ and $B$ (if they differ) and fixes all others, and the same for the columns. Applying these permutations to the winning paths from $A$ gets you the winning paths from $B$. Similarly if both starting squares share a row (or a column) with the winning square. The final case (where one shares a row and the other shares a column with the winning square) reduces to the second via the overall symmetry of the board (replace row moves with column moves).

Thus we only need to consider two cases: where the starting square is in the same row or column as the desired square, and where it is not. Let $E_1$ be the expected number of moves it takes in the first case, $E_2$ the expected time in the second. The answer we want is $E_2$ but we'll need to work with both.

Take the first case. With probability $\frac 1{14}$ you win on the first move, with probability $\frac 6{14}$ you stay in case I, and with probability $\frac {7}{14}$ you move to case 2. Thus we get the recursion: $$E_1=\frac 1{14}(1)+\frac {6}{14}(1+E_1)+\frac 7{14}(1+E_2)$$ $$8E_1-7E_2=14$$

Similarly, if we start in case two we get the recursion $$E_2=\frac {2}{14}(1+E_1)+\frac {12}{14}(1+E_2)$$ $$E_2-E_1=7$$

This system is easily solved to yield $E_1=63$, $E_2=70$

$\endgroup$
  • $\begingroup$ Thanks for the solution! I still have one question though, can you explain why we only need to consider two cases? Why is the expected number of minutes it takes from a square in the top or right row equal, and why is the expected number of minutes it takes from any other square (besides the top right) also equal? $\endgroup$ – Max Dec 5 '15 at 21:19
  • 1
    $\begingroup$ I tried to explain that in the first paragraph (granted, I probably could have done a better job). Idea: take two points which share neither row nor column with winning square. Look at the map which fixes all rows (resp. columns) other than the ones that contain one or both of our points and which permutes the rows (resp. columns) of those two. Apply that map to the winning paths from one point, and you'll get the winning paths from the other. Similarly if both are in the winning row or both in the winning column. The symmetry of the board handles the last case. $\endgroup$ – lulu Dec 5 '15 at 21:27
0
$\begingroup$

This could be framed as an absorbing Markov chain problem. There are 63 transient states and one absorbing one. The transition matrix is large but sparse. This looks to me to be a numerical analysis project, tho you might be able to abstract out an analytical solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.