HMMT 十一月 2021 · 团队赛 · 第 5 题

HMMT November 2021 — Team Round — Problem 5

[40] How many ways are there to place 31 knights in the cells of an 8 × 8 unit grid so that no two attack one another? √ (A knight attacks another knight if the distance between the centers of their cells is exactly 5.)

解析

[40] How many ways are there to place 31 knights in the cells of an 8 × 8 unit grid so that no two attack one another? √ (A knight attacks another knight if the distance between the centers of their cells is exactly 5.) Proposed by: Frederick Zhao Answer: 68 Solution: Consider coloring the squares of the chessboard so that 32 are black and 32 are white, and no two squares of the same color share a side. Then a knight in a square of one color only attacks squares of the opposite color. Any arrangement of knights in which all 31 are placed on the same color therefore works: there are 64 such arrangements (one for each square, in which that square is empty and the others of the same color are occupied). Also, if a knight is placed in a corner, it only attacks two squares. Therefore, for each corner, it is possible to place a knight in one corner and in all squares of theopposite color except the two attacked by the corner night. This gives 68 total arrangements. one can prove that no others are possible.