HMMT 二月 2003 · 冲刺赛 · 第 37 题

英文解析

37. A quagga is an extinct chess piece whose move is like a knight’s, but much longer: itcan move 6 squares in any direction (up, down, left, or right) and then 5 squares in a perpendicular direction. Find the number of ways to place 51 quaggas on an 8 × 8
    chessboard in such a way that no quagga attacks another. (Since quaggas are naturallybelligerent creatures, a quagga is considered to attack quaggas on any squares it canmove to, as well as any other quaggas on the same square.)
    Solution: 68
    Represent the 64 squares of the board as vertices of a graph, and connect two verticesby an edge if a quagga can move from one to the other. The resulting graph consists of
    4 paths of length 5 and 4 paths of length 3 (given by the four rotations of the two pathsshown, next page), and 32 isolated vertices. Each path of length 5 can accommodateat most 3 nonattacking quaggas in a unique way (the first, middle, and last vertices),
    and each path of length 3 can accommodate at most 2 nonattacking quaggas in aunique way; thus, the maximum total number of nonattacking quaggas we can have is
    4 · 3 + 4 · 2 + 32 = 52. For 51 quaggas to fit, then, just one component of the graphmust contain one less quagga than its maximum.
    ( )
    If this component is a path of length 5, there are − 4 = 6 ways to place the two 5
    quaggas on nonadjacent vertices, and then all the other locations are forced; the 4 such 2
    paths then give us 4 · 6 = 24 possibilities this way. If it is a path of length 3, there are
    3 ways to place one quagga, and the rest of the board is forced, so we have 4 · 3 = 12
    possibilities here. Finally, if it is one of the 32 isolated vertices, we simply leave thissquare empty, and the rest of the board is forced, so we have 32 possibilities here. Sothe total is 24 + 12 + 32 = 68 different arrangements.