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

HMMT February 2004 — Guts Round — Problem 44

Shown on your answer sheet is a 20 × 20 grid. Place as many queens as you can so that each of them attacks at most one other queen. (A queen is a chess piece that can move any number of squares horizontally, vertically, or diagonally.) It’s not very hard to get 20 queens, so you get no points for that, but you get 5 points for each further queen beyond 20. You can mark the grid by placing a dot in each square that contains a queen.

解析

Shown on your answer sheet is a 20 × 20 grid. Place as many queens as you can so that each of them attacks at most one other queen. (A queen is a chess piece that can 15 move any number of squares horizontally, vertically, or diagonally.) It’s not very hard to get 20 queens, so you get no points for that, but you get 5 points for each further queen beyond 20. You can mark the grid by placing a dot in each square that contains a queen. Solution: An elementary argument shows there cannot be more than 26 queens: we cannot have more than 2 in a row or column (or else the middle queen would attack the other two), so if we had 27 queens, there would be at least 7 columns with more than 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 she therefore 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 construction gives 23: