HMMT 十一月 2017 · 冲刺赛 · 第 15 题

HMMT November 2017 — Guts Round — Problem 15

[ 5 ] On a 3 × 3 chessboard, each square contains a knight with probability. What is the probability 2 that there are two knights that can attack each other? (In chess, a knight can attack any piece which is two squares away from it in a particular direction and one square away in a perpendicular direction.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2017, November 11, 2017 — GUTS ROUND Organization Team Team ID#

解析

[ 5 ] On a 3 × 3 chessboard, each square contains a knight with probability. What is the probability 2 that there are two knights that can attack each other? (In chess, a knight can attack any piece which is two squares away from it in a particular direction and one square away in a perpendicular direction.) Proposed by: Yuan Yao 209 Answer: 256 Notice that a knight on the center square cannot attack any other square on the chessboard, so whether it contains a knight or not is irrelevant. For ease of reference, we label the other eight squares as follows: 0 5 2 3 X 7 6 1 4 Notice that a knight in square i attacks both square i + 1 and i − 1 (where square numbers are reduced modulo 8). We now consider the number of ways such that no two knights attack each other. • 0 knights: 1 way. • 1 knights: 8 ways. ( ) 8 • 2 knights: − 8 = 20 ways. 2 • 3 knights: 8 + 8 = 16 ways, where the two 8s represent the number of ways such that the “distances” between the knights (index-wise) are 2 , 2 , 4 and 2 , 3 , 3 respectively. • 4 knights: 2 ways. 8 Therefore, out of 2 = 256 ways, 1 + 8 + 20 + 16 + 2 = 47 of them doesn’t have a pair of attacking 256 − 47 209 knights. Thus the answer is = . 256 256