HMMT 十一月 2021 · 冲刺赛 · 第 22 题

HMMT November 2021 — Guts Round — Problem 22

[12] Two distinct squares on a 4 × 4 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 m it takes for the knight to reach the other squarecan be written as , where m, n are positive integers and n gcd( m, n ) = 1. Find 100 m + n . √ √

解析

[12] Two distinct squares on a 4 × 4 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 m moves it takes for the knight to reach the other squarecan be written as , where m, n are positive n integers and gcd( m, n ) = 1. Find 100 m + n . Proposed by: Jeffrey Lu Answer: 1205 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 0 3 2 4 3 2 1 3 4 1 2 2 3 2 1 3 0 3 2 2 1 4 3 1 2 1 4 2 3 2 1 5 2 3 2 2 3 2 3 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: 1 (4(2 · 1 + 5 · 2 + 4 · 3 + 2 · 4 + 2 · 5) + 8(3 · 1 + 6 · 2 + 5 · 3 + 1 · 4) + 4(4 · 1 + 5 · 2 + 4 · 3 + 2 · 4)) 16 · 15 1 = (168 + 272 + 136) 240 12 = . 5 √ √