HMMT 二月 2011 · 冲刺赛 · 第 26 题

英文解析

26. [ 14 ] In how many ways can 13 bishops be placed on an 8 × 8 chessboard such that (i) a bishop is placedon the second square in the second row, (ii) at most one bishop is placed on each square, (iii) no bishopis placed on the same diagonal as another bishop, and (iv) every diagonal contains a bishop? (For thepurposes of this problem, consider all diagonals of the chessboard to be diagonals, not just the maindiagonals).
    Answer: 1152
    We color the squares of the chessboard white and black such that B2 (the second square in the secondrow) is black. Note that at most 7 bishops can go on the white squares, and if there is a bishop on b 2,
    at most 5 more can be on the white squares. So of the other 12 bishops, 7 go on white squares and 5
    go on black squares.
    Consider the long diagonal on the white squares, and the 6 white diagonals parallel to it. Of the 7
    bishops placed on the white squares, exactly one must go on each of these diagonals (this also proves
    Guts Roundthat at most 7 can go on the white squares). Of these diagonals there is 1 of length 8, and 2 of length
    2,4, and 6. There are 2 ways to place 2 bishops on the diagonals of length 2, then 2 ways to place 2
    bishops on the diagonals of length 4, then 2 ways to place 2 bishops on the diagonals of length 2, thenthe long diagonal bishop can go on either corner. So there are 16 ways to place 7 bishops on the whitesquares.
    Now we can divide the black squares of the board into the 6 diagonals parallel to the long whitediagonal, and the long black diagonal. The bishop on b 2 accounts for two of these diagonals. We areleft with a diagonal of length 3, and two diagonals of length 5,7. There are 3 ways to pick the bishopon the diagonal of length 3, 6 ways to pick two bishop for the diagonals of length 5, and 6 ways to pickthe bishop on the diagonals of length 7. So there are 72 ways to pick 5 other bishops for the blacksquares. So the answer is 72 · 16 = 1152.