Two distinct squares on a chessboard are chosen, with each pair of squares equally likely to be chosen. A knight is placed on one of the squares. The expected value of the minimum number of moves it takes for the knight to reach the other square can be written as , where are positive integers and . Find .
Problem 988
Official solution
Solution:
We can do casework based on the position of the knight: corner, edge, or center. In each case, we can quickly compute all 15 distances by writing a 1 down in all squares reachable from the original square, then writing a 2 down in all blank squares reachable from a square with a 1, writing a 3 down in all blank squares reachable from a square with a 2, and so on. The resulting tables are below:
| 0 | 3 | 2 | 5 |
|---|---|---|---|
| 3 | 4 | 1 | 2 |
| 2 | 1 | 4 | 3 |
| 5 | 2 | 3 | 2 |
| 3 | 0 | 3 | 2 |
|---|---|---|---|
| 2 | 3 | 2 | 1 |
| 1 | 2 | 1 | 4 |
| 2 | 3 | 2 | 3 |
| 4 | 3 | 2 | 1 |
|---|---|---|---|
| 3 | 0 | 3 | 2 |
| 2 | 3 | 2 | 1 |
| 1 | 2 | 1 | 4 |
The expectation can be computed by weighing the sum of the distances in each of these tables by the number of squares of that type: