HMMT 二月 2025 · 团队赛 · 第 4 题
HMMT February 2025 — Team Round — Problem 4
题目详情
- [35] Jerry places at most one rook in each cell of a 2025 × 2025 grid of cells. A rook attacks another rook if the two rooks are in the same row or column and there are no other rooks between them. Determine, with proof, the maximum number of rooks Jerry can place on the grid such that no rook attacks 4 other rooks.
解析
- [35] Jerry places at most one rook in each cell of a 2025 × 2025 grid of cells. A rook attacks another rook if the two rooks are in the same row or column and there are no other rooks between them. Determine, with proof, the maximum number of rooks Jerry can place on the grid such that no rook attacks 4 other rooks. Proposed by: Arul Kolla Answer: 8096 Solution 1: The answer is 2024 × 4 = 8096. More generally, for an n × n grid, the answer is 4 n − 4. Call a rook that attacks at most 3 other rooks good . We use the following observation in both parts of the solution: a rook on the border of the grid must be good. Lower Bound: Place rooks on all 4 n − 4 border cells of the grid. By the above observation, every rook is good. Upper Bound: Consider any valid placement of rooks, and assume there exists a rook that is not on the border. We can move this rook to the border via a usual rook move, since this rook is good and thus the path to one of the four border cells in its row or column must be empty. After this move, we claim the placement of rooks is still valid. Indeed: • the moved rook is now on the border, so by the observation above, it must be good; • any rook that used to attack this rook cannot attack more rooks after the move, so such rooks must still be good; • any rook attacked in the final position must be either: – opposite the direction moved, in which case it attacked the moved rook both before and after the move (so is still good), or – perpendicular to the direction moved, in which case it is a border rook and must always be good. By repeating the above process, we can always move from any good position to one where all rooks are on the border. This implies that the number of rooks in any good position is at most 4 n − 4. When n = 2024, the answer is 4 n − 4 = 8096 . Solution 2: Consider the set of all rooks which are either the leftmost or rightmost in their row, or the topmost or bottommost in their column. Note that this set must include every rook, as any rook not in this set attacks a rook in all 4 directions. Each column contributes at most 2 rooks to this set, and each row contributes at most 2 rooks. We can safely ignore the top and bottom rows in this count, as any rook in the top or bottom row is already the topmost or bottommost rook in its column. Thus the number of rooks in the set is at most 2 · (2025 + 2025 − 2) = 8096 , which can be constructed as seen before.