HMMT 二月 2004 · 冲刺赛 · 第 44 题

英文解析

44. Shown on your answer sheet is a 20 × 20 grid. Place as many queens as you can sothat each of them attacks at most one other queen. (A queen is a chess piece that canmove any number of squares horizontally, vertically, or diagonally.) It’s not very hard 15
    to get 20 queens, so you get no points for that, but you get 5 points for each furtherqueen beyond 20. You can mark the grid by placing a dot in each square that containsa queen.
    Solution: An elementary argument shows there cannot be more than 26 queens: wecannot have more than 2 in a row or column (or else the middle queen would attackthe other two), so if we had 27 queens, there would be at least 7 columns with morethan one queen and thus at most 13 queens that are alone in their respective columns.
    Similarly, there would be at most 13 queens that are alone in their respective rows.
    This leaves 27 − 13 − 13 = 1 queen who is not alone in her row or column, and shetherefore attacks two other queens, contradiction.
    Of course, this is not a very strong argument since it makes no use of the diagonals.
    The best possible number of queens is not known to us; the following constructiongives 23: